Четвертое занятие по С++: массивы

Привет! Сегодня настало время сделать еще один большой шаг вперед — узнать, что же такое массивы. Ты семимильными шагами приближаешься к безграничным возможностям создавать все, что тебе захочется! Итак, вперед!

Массивы или принцип белки.

Жила была белка. Каждый год она на зиму запасала много орехов. Чтобы их хранить, она постоянно арендовала у медведя на складе кучу маленьких коробок, в каждую из которых помещался всего один орех. Причем все коробки по разному назывались по-разному и стояли в разных частях склада, поэтому каждую весну приходилось бегать по всему лестному складу выискивая свои коробки. Сначала белка называла свои коробки просто: a,b,c,d…

Но время шло, белка влюбилась и вышла замуж. У нее появились маленькие бельчата, которые радостно резвились на деревьях и ломали все на своем пути. Как и все дети, в будущем планирующие стать программистами . Бельчата росли, крепчали, постепенно изучали матан и лесную экономическую теорию. Надо же как то считать орехи.

Вскоре семья стала совсем большой: мама, папа, и пятеро здоровенных голодных белок. Потребность в орехах выросла во много раз, причем собирать их существам, в совершенстве владеющим численными методами, проблем не составляло, а вот хранить их стало накладно. Дело в том, что коробки теперь назывались совсем страшно и заполнять заказы, в которых надо было указывать названия более 500 коробок стало совсем скучно: adfbrfg,dfnfunru,wdnwndwund,gurgurnr….

Тогда один самый умный бельчонок, только что закончивший НИУ ВШЭ, сообразил, что у медведя место надо арендовать целыми полками, а не отдельными коробками. Действительно, тогда можно просто назвать имя полки, а все остальные элементы просто называть цифрами. Так гораздо проще, ведь в заказе можно просто указать, что нам нужна полка с именем nuts c 500 коробками на ней.

Медведь, конечно же, не отказался от столь интересного предложения и даже включил выделение полок в свой список услуг, а белки жили долго и счастливо!

По сабжу…

Причем тут белка??? Ответ прост, сейчас речь шла про массив: когда данных в программе становится много, то определять очень большое количество переменных становится неудобным. Если ты со мной не согласен — попробуй определить 100 переменных и не запутаться что где лежит.

Для подобных задач были придуманы массивы:

Массив — множество однотипных переменных, стоящих в памяти на соседних местах. Такие переменные называются элементами массива и к ним можно обращаться по номеру.

Массив можно определить в программе вот так:

Обрати внимание: в статических массивах (а говорим мы именно о них) при определении размер нельзя задавать переменной!

int mas[34]; //так можно

const int N = 10; //это константа, значение константы в процессе работы программы изменять нельзя
int mas1[N];     //так можно
int mas2[N + 2]; //и так можно!

int a = 10;
int mas3[a]; //так нельзя!

int b;
cin >> b;
int mas3[b]; //так тем более нельзя!!!

Вот так массив выглядит в памяти:

Как ты видишь, mas на картинке — массив из семи элементов. У каждого из стоящих рядом элементов есть номер, начинающийся нуля. Этот номер называется индексом. Индексы начинаются с нуля. Первый элемент имеет номер ноль. НОЛЬ! =)

Элементы массива нумеруются с нуля!

Что бы стало понятно, как использовать массивы, давай рассмотрим какой нибудь пример:

int nuts[3]; //просим выделить на массив из трех элементов
nuts[0] = 45; //кладем что то в него
nuts[1] = -5;
nuts[2] = 3; 
//mas[3] не существует, т.к размер массива 3! 
  // Исользуем элементы массива, как обычные переменнные.
nuts[2] = nuts[2] + nuts[0] + nuts[1];
cout << nuts[2]; //выведет 43

 

Как видишь с элементами массива можно работать точно также, как и с переменными, просто кроме названия массива нужно указывать номер (индекс) нужного нам элемента. И еще раз:

Элементы массива нумеруются с нуля! В массиве из 5 элементов есть элементы с номерами от 0 до 4 включительно!

Почему так важно то, что нумерация идет с нуля? Что, если обратиться к несуществующему элементу, произойдет светопреставление?

Об этом нам повествует фильм «Ирония судьбы», где главный герой на полном серьезе отправился в несуществующий элемент массива, думаю что пользуется своей памятью. Я думаю все знают чем это закончилось =) Шутка.

Если серьезно, то программа в которой мы выходим за границы отведенной нам памяти может вести себя абсолютно непредсказуемо, в зависимости от никому непонятных условий (снова undefined behaviour!). Возможно три варианта: либо в процессе работы программы мы получаем ошибку access violation — доступ к чужой памяти, либо вообще непонятную ошибку, например, на операторе вывода в 100 строках от ошибки (во время работы, а не компиляции), а возможен вариант, когда все работает, как ни в чем не бывало, только программа берет откуда-то непонятные числа и выдает непредсказуемые ответы. От чего это зависит, известно только Ипполиту, но эти варианты для одной и той же программы могут чередоваться. А возможен вариант, когда мы залезем в область памяти windows, что-нибудь там поменяем,  и система зависнет. Вероятность, конечно, крайне мала, но….

Такие ошибки очень трудно искать, поэтому лучше с самого начала следить за тем, к каким элементам мы обращаемся. Как видишь, чем больше ты знаешь, тем больше ответственность =)

Заполнение и вывод с циклов.

Тебе не показалось, что мы просто все усложнили? Мало того, что теперь помимо названия надо писать цифры, так еще и какие то проблемы с памятью? Вся прелесть массивов, что их очень быстро и удобно использовать с циклами.

Допустим, нам нужно ввести и запомнить 100 чисел. Без проблем!

int mas[100];

for (int i = 0; i < 100; ++i) 
  cin >> mas[i]; //0 - первый индекс, 99 последний

Все!

Старыми методами нам бы пришлось писать что-то вроде этого:

int a; 
cin >> a;
int b;
cin >> b;
int c;
cin >> c;
//...

Как видишь, новый способ гораздо компактней =).

Теперь поставим задачку по-сложнее: нужно ввести 100 чисел, заменить каждое, кроме двух последних, на сумму двух следующих. Как видишь, такую задачку вообще не решить известными тебе методами. А с массивами все будет относительно быстро:

const int N = 100;
int numbers[N];

//сначала вводим массив с клавиатуры
for (int i = 0; i < N; ++i)
  cin >> numbers[i];

//производим замену
for (int i = 0; i < N-2; ++i)
  numbers[i] = numbers[i+1] + numbers[i+2]; //98, т.к. без двух последних

//красиво выводим обратно
for (int i = 0; i < N; ++i ) 
  cout << numbers[i] << " ";

Кстати, обрати внимание на использование нами константы N. Знаешь, зачем? Чтобы можно было изменить количество чисел в массиве, просто изменив значение N. Для каждого неизменяющегося «волшебного числа» навроде размера массива лучше определять константу, чтобы потом программу было легко изменять. Да и выглядит это понятнее.

(*) Еще немного о стиле.

Вообще, среди программистов принято давать некоторым переменным стандартные имена, чтобы незнакомые программы и алгоритмы было проще читать. Например, переменные счетчиков цикла принято называть i, j, k (а если у вас более трех вложенных циклов, это сигнал, что вы делаете что-то не так =)) где i — сокращение от iteration (повторение), а j и k — просто следующие за i буквы алфавита. Некоторые числа, значение которых надо вычислить, обычно называются x, y, z (по аналогии с алгеброй). Цифры, вводимые пользователем, обычно называют a, b, c и.т.д. А константы обычно называют N, M и.т.д. Возможно, сперва это покажется странным и неудобным, но со временем очень привыкаешь так писать… Да и чужой код понять проще. Если я встречаю переменную с именем i, я начинаю думать, что это счетчик.

Вообще подбор правильных имен — это целое искусство =). Я считаю, что для имен с большой областью видимости — глобальных переменных, констант, функций и.т.п. следует выбирать осмысленные имена, так чтобы было понятно что это. С другой стороны, если переменная используется только в небольшом участке кода, логичнее дать ей короткое простое имя. О функциях вы прочитаете в следующем уроке.

Мистер неожиданность…

Итак, последнее на сегодня: что если мне лень вводить много много цифр, и я хочу чтобы компьютер сам что-нибудь придумывал. Компьютер не умеет придумывать, зато он умеет генерировать случайные числа, для этого используется функция rand(). Как ей пользоваться?

#include <iostream> //куда же без него?)
#include <stdlib.h> //rand() лежит тут

using namespace std;

int main()
{
    int mas[300];
    for ( int i = 0; i < 300; ++i )
    {
        mas[i] = rand() % 100; // кладем в i-ый случайное число из диапазона 0-99 включительно 
    }
    //что то делаем

}

Итак, в этом примере мы заполнили 300 элементов массива случайными числами. А теперь давай напишем простенькую консольную игрушку: надо угадать загаданное число от 1 до 10:

#include <iostream> //куда же без него?)
#include <stdlib.h> //rand() лежит тут

using namespace std;

int main () {
   int a = -1, secret = rand() % 10 + 1, i = 0; //диапазон 0-9 + 1 - это диапазон [1;10].
   cout << "guess the number between 1 and 10:";
   for( i = 0; a != secret; ++i ) {
      cin >> a;
      if (a > secret) cout << "higher, try again:";
      if (a < secret) cout << "lower, try again:";
   }
   cout << "Cool! You win!!!" << endl;
   cout << "N of tries" << i;
}

Квадратичные алгоритмы сортировки массивов

Во многих задачах появляется необходимость отсортировать массив по возрастанию или убыванию. Например, если на нужно вывести n максимальных чисел или отсортировать названия в словаре по алфавиту (об этом будет чуть позже). Мы рассмотрим два алгоритма, которые наиболее просты для понимая: пузырек и выборка.

В пузырьковой сортировке мы проходим по всем элементам массива начиная с первого и если элемент больше предыдущего — меняем их местами. Этот процесс мы будем повторять до тех пор, пока массив не будет полностью отсортирован (ни одной замены за проход). Визуально алгоритм продемонстрирован вот здесь.

Почему пузырьковая сортировка (bubble-sort)? Можно представить что элементы массива — это пузырьки, более маленькие всплывают вверх, а большие опускаются вниз.

Реализация алгоритма может выглядеть вот так:

int mas[10];
for (int i=0; i<10; i++) cin>>mas[i];

bool a; //в этой переменной мы будем запоминать, была ли замена в последней проходе
do
{
   a = false; //предполагаем что замен не будет
   for (int i=1; i<10; i++) //проходим по всем элементам начиная с первого (не нулевого)
   {
      if (mas[i-1]>mas[i]) //если предыдущий больше текущего
      {
          int c = mas[i-1]; //меняем местами
          mas[i-1] = mas[i];
          mas[i] = c; 
          a=true; //говорим что была замена
      }
   }

}
while (a!=false); //все это, пока элементы не встанут на свои места

Другой алгоритм сортировки называется простой выборкой. Смысл в том, что мы находим максимальный элемент среди всех элементов массива и ставим его на первое место. Затем ищем максимум среди все кроме первого и ставим на второе… И так далее, пока не дойдем до последнего.

int mas[10];
for (int i=0; i<10; i++) cin>>mas[i];

for (int i=0; i<=8; i++) //будем работать, пока не дойдем до предпоследнего элемента
{
    int max = mas[i]; //начинаем искать максимальный
    int index = i; //нам также понадобится индекс максимального элемента
    for (int j=i+1; j<10; j++) //ищем максимальный среди всех начиная от следующего за текущим
    {
        if (mas[j]>max) //если элемент больше max, запоминаем его номер и значение
        {
            index = j;
            max = mas[j];
        }
    }
    int c = mas[i]; //меняем местами i-ый и максимальный
    mas[i] = mas[index];
    mas[index] = c;
}

Почему эти алгоритмы называются квадратичными? Рассмотрим пузырьковую сортировку. В худшем случае мы пройдем по N элементам N раз (т.к. у нас цикл в цикле). То есть на 10 элементов у нас 100, а значит 10 в квадрате операций — отсюда и название. Позже мы рассмотрим более быстрые алгоритмы сортировки.

Задачи для самостоятельного решения:

2.1.1
a) Заполнить массив из 20 элементов числами от 0 до 19. (3 балла)

б) Заполнить массив из 20 элементов числами от 19 до 0. (3 балла)

2.1.2 Вывести значения всех элементов массива. (3 балла)

2.1.3 Вывести все нечетные элементы массива. (5 баллов)

2.1.4 Найти сумму всех элементов массива. (5 баллов)

2.1.5 Вводятся N чисел. Вывести на экран максимальное и минимальное числа. (5 баллов)

2.3.1 Проверить правильность расстановки открывающих и закрывающих скобок ‘(‘ и ‘)’. (10 баллов)

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *