Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
§ 62. Массивы Что такое массив Основное предназначение современных компьютеров – обработка большого количества данных. При этом надо как-то обращаться к каждой из тысяч (или даже миллионов) ячеек сданными. Очень сложно дать каждой ячейке собственное имя и при этом не запутаться. Из этой ситуации выходят так дают имя не ячейке, а группе ячеек, в которой каждая ячейка имеет собственный номер. Такая область памяти называется массивом. Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер. Для работы с массивами нужно, в первую очередь, научиться • выделять память нужного размера под массив • записывать данные в нужную ячейку • читать данные из ячейки массива. Чтобы использовать массив, надо его объявить – определить тип массива (тип входящих в него элементов, выделить место в памяти и присвоить имя. Имена массивов строятся по тем же правилам, что и имена переменных. В языках C и C++ массивы объявляются почти также, как и обычные переменные, только после имени массива в квадратных скобках указывают количество элементов int A[ 5 ]; double V[ 8 ]; bool L[ 10 ]; char S[ 80 ]; Задачи и задания Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 35 Индексы элементов массива всегда начинаются с нуля. Если, например, в массиве A пять элементов, то последний элемент будет иметь индекс 4. Для того, чтобы обратиться к элементу массива, нужно записать имя массива ив квадратных скобках индекс нужного элемента, например, A[3]. Индексом может быть не только число, но значение целой переменной или арифметического выражения целого типа. В этом примере массив заполняется квадратами первых натуральных чисел main() { const int N = 10 ; int A[N]; int i; for ( i = 0 ; i < N; i++ ) A[i] = i*i; } При объявлении границ индексов массивов можно использовать константы – постоянные величины, имеющие имя. В приведенном примере с помощью ключевого слова const объявлена целочисленная ( int) константа N, равная 10. Константы обычно вводятся выше блока объявления переменных. Использование констант очень удобно, потому что при изменении размера массива в программе нужно поменять только одно число – значение этой константы. Далее во всех примерах мы будем считать, что в программе объявлен целочисленный массив, состоящий их N элементов (с индексами от 0 до N-1), а также целочисленная переменная i, которая будет обозначать индекс элемента массива. Чтобы ввести такой массив или вывести его на экран, нужно использовать цикл, то есть вводи вывод массива выполняется поэлементно for ( i = 0 ; i < N; i++ ) { printf ( "A[%d]=" , i ); scanf ( "%d" , &A[i] ); } for ( i = 0 ; i < N; i++ ) printf ( "%d " , A[i] ); for ( i = 0 ; i < N; i++ ) { cout << "A[" << i << "]=" ; cin >> A[i]; } for ( i = 0 ; i < N; i++ ) cout << A[i] << " " ; В этом примере перед вводом очередного элемента массива на экран выводится подсказка. Например, при вводе го элемента будет выведено « A[3]=». После вывода каждого элемента ставится пробел, иначе все значения сольются в одну строку. В учебных примерах массивы часто заполняют случайными числами for ( i = 0 ; i < N; i++ ) { A[i] = irand ( 20 , 100 ); printf ( "%d " , A[i] ); } for ( i = 0 ; i < N; i++ ) { A[i] = irand ( 20 , 100 ); cout << A[i] << " " ; } Здесь использована функция irand, которая возвращает псевдослучайное целое число в заданном диапазоне. Такой функции нет в стандартной библиотеке языка C, но её легко написать вспомните материал § 56): int irand ( int a, int b ) { return a + rand()% (b - a + 1 ); } Напомним, что для работы сдатчиком случайных чисел в языке C нужно подключить с помощью директивы include заголовочный файла в языке C++ – файл cstdlib. Перебор элементов Перебор элементов состоит в том, что мы в цикле просматриваем все элементы массива и, если нужно, выполняем с каждым из них некоторую операцию. Для этого удобнее всего использовать цикл с переменной, которая изменяется от минимального до максимального индекса. Поскольку мы будем работать с массивом, элементы которого имеют индексы от 0 до N-1, цикл выглядит так Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 36 22.10.2015 for ( i = 0 ; i < N; i++ ) { ... } Здесь вместо многоточия можно добавлять операторы, работающие с элементом A[i]. Во многих задачах нужно найти в массиве все элементы, удовлетворяющие заданному условию, и как-то их обработать. Простейшая из таких задач – подсчёт нужных элементов. Для решения этой задачи нужно ввести переменную-счётчик, начальное значение которой равно нулю. Далее в цикле (от 0 до N-1) просматриваем все элементы массива. Если для очередного элемента выполняется заданное условие, то увеличиваем счётчик на 1. На псевдокоде этот алгоритм выглядит так счётчик = 0 ; for ( i = 0 ; i < N; i++ ) if ( условие выполняется для A[i] ) счётчик ++; Предположим, что в массиве A записаны данные о росте игроков баскетбольной команды. Найдем количество игроков, рост которых больше 180 см, но меньше 190 см. В следующей программе используется переменная-счётчик count: count = 0 ; for ( i = 0 ; i < N; i++ ) if ( 180 < A[i] && A[i] < 190 ) count ++; Теперь усложним задачу требуется найти средний рост этих игроков. Для этого нужно дополнительно в отдельной переменной складывать все нужные значения, а после завершения цикла разделить эту сумму на количество. Начальное значение переменной sum, в которой накапливается сумма, тоже должно быть равно нулю. count = 0 ; sum = 0 ; for ( i = 0 ; i < N; i++ ) if ( 180 < A[i] && A[i] < 190 ) { count ++; sum += A[i]; } printf ( "%f" , (float)sum / count ); Обратите внимание, что в последней строке для того, чтобы получить вещественный (а не округленный целочисленный) результат деления, значение переменной sum преобразовано к вещественному числу с помощью записи (float)sum. 1. Что такое массив Зачем нужны массивы 2. Зачем нужно объявлять массивы 3. Как объявляются массивы 4. Как выдумаете, почему элементы массива расположены в памяти рядом 5. Как обращаются к элементу массива 6. Может ли нумерация элементов массива в языках C и С+ начинаться нес, ас другого числа. Почему размер массива лучше вводить как константу, а не число 8. Как ввести массив и вывести его на экран 9. Как заполнить массив случайными числами в диапазоне от 100 до 200? 1. Заполните массив элементами арифметической прогрессии. Её первый элемент и разность нужно ввести с клавиатуры. 2. Заполните массив степенями числа 2 (от 2 1 до 2 N ). Задачи и задания ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 37 22.10.2015 3. Заполните массив первыми числами Фибоначчи. 4. Заполните массив из N элементов случайными целыми числами в диапазоне 1..N так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку. 5. Постройте случайную перестановку чисел от 1 до N так, чтобы первое число обязательно было равно 5. 6. Заполните массив случайными числами в диапазоне 20..100 и подсчитайте отдельно число чётных и нечётных элементов. 7. Заполните массив случайными числами в диапазоне 1000.2000 и подсчитайте число элементов, у которых вторая с конца цифра – чётная. 8. Заполните массив случайными числами в диапазоне 0..100 и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50. § 63. Алгоритмы обработки массивов Поиск в массиве Требуется найти в массиве элемент, равный значению переменной X, или сообщить, что его там нет. Алгоритм решения сводится к просмотру всех элементов массива с первого до последнего. Как только найден элемент, равный X, нужно выйти из цикла и вывести результат. Напрашивается такой алгоритм i = 0 ; while ( A[i] != X ) i ++; printf ( "A[%d]=%d" , i, X ); Он хорошо работает, если нужный элемент в массиве есть, однако приведет к ошибке, если такого элемента нет – получится зацикливание и выход заграницы массива. Поэтому в условие нужно добавить еще одно ограничение i< N. Если после окончания цикла это условие нарушено, значит поиск был неудачным – элемента нет i = 0 ; while ( i < N && A[i] != X ) i ++; if ( i < N ) printf ( "A[%d]=%d" , i, X ); else printf ( Не нашли ); Отметим одну тонкость. В сложном условии i < N и A[i]!= X первым должно проверяться именно отношение i < N. Если первая часть условия, соединенного с помощью операции И, ложно, то вторая часть, как правило, не вычисляется – уже понятно, что всё условие ложно. Заметим, что если i >= N, при проверке условия A[i] != X происходит выход заграницы массива, то есть к обращению к ячейке памяти за пределами массива. Возможен ещё один поход к решению этой задачи используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение. nX = -1 ; for ( i = 0 ; i < N; i++ ) if ( A[i] == X ) { nX = i; break ; } if ( nX >= 0 ) printf ( "A[%d]=%d" , nX, X ); else 10 Во многих современных языках программирования (например, в C, C++, Python, Javascript, PHP) такое поведение гарантировано стандартом. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 38 22.10.2015 printf ( Не нашли ); Для хранения номера найденного элемента вводим переменную nX, сначала записываем вне значение –1 (или любое другое число вне диапазона от 0 до N-1, то есть неправильный номер элемента. Для выхода из цикла используется оператор break. Если значение переменной nX осталось равным –1 (не изменилось входе выполнения цикла, тов массиве нет элемента, равного X. Максимальный элемент Найдем в массиве максимальный элемент. Для его хранения выделим целочисленную переменную. Будем в цикле просматривать все элементы массива один за другим. Если очередной элемент массива больше, чем максимальный из предыдущих (находящийся в переменной M), запомним новое значение максимального элемента в M. Остается решить, каково должно быть начальное значение M. Во-первых, можно записать туда значение, заведомо меньшее, чем любой из элементов массива. Например, если в массиве записаны натуральные числа, можно записать в M ноль или отрицательное число. Если содержимое массива неизвестно, можно сразу записать в M значение A[0], а цикл перебора начать сто есть со второго по счёту элемента M = A[ 0 ]; for ( i = 1 ; i < N; i++ ) if ( A[i] > M ) M = A[i]; printf ( "%d" , M ); Теперь предположим, что нужно найти не только значение, но и номер максимального элемента. Казалось бы, нужно ввести еще одну переменную nMax для хранения номера, сначала записать в нее 0 (считаем элемент A[0] максимальными затем, когда нашли новый максимальный элемент, запоминать его номер в переменной nMax: M = A[ 0 ]; nMax = 0 ; for ( i = 1 ; i < N; i++ ) if ( A[i] > M ) { M = A[i]; nMax = i; } printf ( "A[%d]=%d" , nMax, M ); Однако это не самый лучший вариант. Дело в том, что по номеру элемента можно всегда определить его значение. Поэтому достаточно хранить только номер максимального элемента. Если этот номер равен nMax, то значение максимального элемента равно A[nMax]: nMax = 0 ; for ( i = 1 ; i < N; i++ ) if ( A[i] > A[nMax] ) nMax = i; printf ( "A[%d]=%d" , nMax, A[nMax] ); Реверс массива Реверс массива – это перестановка его элементов в обратном порядке первый элемент становится последним, а последний – первым. Из рисунка следует, что й элемент меняется местами см, й – см и т.д. Сумма индексов элементов, участвующих в обмене, для всех пар равна N-1, поэтому элемент с номером i должен меняться местами см элементом. Кажется, что можно написать такой цикл сделать для i от 0 до N- 1 поменять местами A[i] и A[N- 1 -i] 1 2 N-1 N 7 12 5 34 40 23 1 2 N-1 N 23 40 34 5 12 7 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 39 однако это неверно. Посмотрим, что получится для массива из четырёх элементов Как видите, массив вернулся в исходное состояние реверс выполнен дважды. Поэтому нужно остановить цикл на середине массива сделать для i от 0 до N/ 2 поменять местами A[i] и A[N-1-i] Для обмена используется вспомогательная целая переменная c: for ( i = 0 ; i < (N/ 2 ); i++ ) { c = A[i]; A[i] = A[N- 1 -i]; A[N- 1 -i] = c; } Сдвиг элементов массива При удалении и вставке элементов необходимо выполнять сдвиг части или всех элементов массива в ту или другую сторону. Массив часто рисуют в виде таблицы, где первый элемент расположен слева. Поэтому сдвиг влево – это перемещение всех элементов на одну ячейку, при котором переходит на место A[0], A[2] – на место A[1] и т.д. Последний элемент остается на своем месте, поскольку новое значение для него взять неоткуда – массив кончился. Алгоритм выглядит так for ( i = 0 ; i < N- 1 ; i++ ) A[i] = A[i+1]; Обратите внимание, что цикл заканчивается при i=N-2 (а не N-1), чтобы не было выхода заграницы массива, то есть обращения к несуществующему элементу A[N]. При таком сдвиге первый элемент пропадает, а последний – дублируется. Можно старое значение первого элемента записать на место последнего. Такой сдвиг называется циклическим см. § 28). Предварительно (до начала цикла) первый элемент нужно запомнить во вспомогательной переменной, а после завершения цикла записать его в последнюю ячейку массива c = A[ 0 ]; for ( i = 0 ; i < N- 1 ; i++ ) A[i] = A[i+ 1 ]; A[N- 1 ] = c; Отбор нужных элементов Требуется отобрать все элементы массива A, удовлетворяющие некоторому условию, в массив. Очевидное решение для i от 0 до N- 1 если условие выполняется для A[i] то B[i] = A[i]; На самом деле это решение плохое, потому что нужные элементы в массиве B оказываются расположены вразброс, на тех местах, где они стояли в массиве A. Поэтому работать с таким массивом очень неудобно. На рисунке изображен случай, когда отбираются чётные элементы 0 1 N-2 N-1 7 12 5 34 40 23 0 1 N-2 N-1 12 5 34 40 23 23 0 1 2 3 7 12 40 23 A[0]↔A[3] 23 12 40 7 A[1]↔A[2] 23 40 12 7 A[2]↔A[1] 23 12 40 7 A[3]↔A[0] 7 12 40 23 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 40 Хочется, чтобы все отобранные элементы стояли вначале массива B: Для этого вводят переменную-счётчик count, в которой считают количество найденных элементов. Сначала её значение равно нулю. Когда очередной элемент найден, счётчик содержит номер первой свободной ячейки массива B, вне записывается найденное значение, а затем значение счётчика увеличивается на 1. Программа, отбирающая все чётные элементы, выглядит так count = 0 ; for ( i = 0 ; i < N; i++ ) if ( A[i] % 2 == 0 ) { B[count] = A[i]; count ++; } Нужно помнить, что только первые count элементов массива B рабочие, остальные содержат неизвестные данные. Например, вот так можно вывести найденные элементы на экран for ( i = 0 ; i < count ; i++ ) printf ( "%d " , B[i] ); Если вместо массива B использовать тот же массив A, где находятся исходные числа, то все нужные элементы будут сгруппированы вначале, а их количество записано в переменной count: 1. Почему при поиске индекса максимального элемента ненужно хранить само значение максимального элемента 2. Что такое реверс массива 3. Как выдумаете, какую ошибку чаще всего делают начинающие, программируя реверс массива. Как выдумаете, какие проблемы (и ошибки) могут возникнуть при циклическом сдвиге массива вправо 5. Что произойдет с массивом при выполнении следующего фрагмента программы for ( i = 0 ; i 1 ; i++ ) A[i+1] = A[i]; 6. Как (при использовании приведенного алгоритма поиска) определить, что элемент не найден. Что такое выход заграницы массива Почему он может быть опасен 8. Опишите очевидный алгоритм отбора части элементов одного массива в другой массив. Почему его не используют A 12 5 34 11 23 46 A 12 34 46 11 23 46 count A 12 5 34 11 23 46 B 12 34 46 ? ? ? count ? Контрольные вопросы A 12 5 34 11 23 46 B 12 ? 34 ? ? 46 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 41 22.10.2015 1. Напишите программу, которая находит максимальный и минимальный из чётных положительных элементов массива. Если в массиве нет чётных положительных элементов, нужно вывести сообщение об этом. 2. Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение. 3. Найдите за один проход по массиву три его различных элемента, которые меньше всех остальных (три минимума. 4. Заполните массив случайными числами в диапазоне 10..12 и найдите длину самой длинной последовательности стоящих рядом одинаковых элементов. 5. Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры. 6. Заполните массив случайными числами и переставьте соседние элементы, поменяв 1-ый элемент сом, й – см и т.д. 7. Заполните массив из чётного количество элементов случайными числами и выполните реверс отдельно для ой и ой половин массива. 8. Заполните массив случайными числами и выполните реверс для части массива между элементами с индексами K и M (включая эти элементы. 9. Напишите программу для выполнения циклического сдвига массива вправо на 4 элемента. 10. Найдите в массиве все простые числа и скопируйте их в новый массив. 11. Найдите в массиве все числа Фибоначчи и скопируйте их в новый массив. |