Программирование. Обработка массивов - Обработка информации - ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ

Конспект

Введение

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

Мы знаем, что для повторения одинаковых действий в программировании специально придумали циклы. Однако, при хранении данных в отдельных переменных использовать цикл не получится — нужно каждый раз обращаться к разным переменным, и в цикл это не оформить.

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

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

При использовании массивов имеется некоторое количество типовых операций, которые осуществляются с массивом и его элементами. Большинству программ, использующих массивы, необходимо для выполнения задачи, как правило, какое-то количество этих операций. Мы рассмотрим их далее. При написании программы, обрабатывающей массив, достаточно просто выбрать из списка нужный набор фрагментов программы, и составить их друг за другом.

Описание массива

Любые переменные, включая массивы, должны быть описаны в программе в разделе описания переменных var. При описании массива следует указывать: имя новой переменной (массива), диапазон значений индексов элемента массива и тип данных, который хранится в элементах массива.

Пример

Здесь описан массив с именем А, состоящий из 10-ти элементов, пронумерованных числами от 1 до 10. В элементах массива хранятся целые числа. Обратите внимание, слова array(переводится как массив) и of (переводится как из) являются ключевыми словами языка программирования Паскаль.

Повторимся: при описании массива нужно указать:

- имя массива (правила записи имени массива такие же, как для имён переменных);

- символ “:” (как и при описании переменных, между именем/именами описываемых переменных и именем их типа данных необходимо ставить двоеточие);

- ключевое слово “array” (массив);

- в квадратных скобках два числа — начальное и конечное значение индексов, которыми будут нумероваться элементы массива. Между этими значениями должно быть написано “. .” (две точки). Как правило, в качестве начального значения индекса используют число 1, а в качестве конечного значения индекса используют требуемое количество элементов массива;

- ключевое слово “of” (из);

- имя типа данных, который будут иметь все элементы этого массива. В справочнике разбирается только тип данных integer.

Задание начальных значений элементов массива

Перед тем как массив можно будет использовать/обрабатывать, элементы массива должны получить значения. Как и для одиночных переменных, эти значения могут быть присвоены оператором присваивания или введены с клавиатуры. Однако, в отличие от отдельных переменных, элементов массива много.

Если способ задания значения для каждого элемента одинаковый, почти всегда можно использовать для этого цикл for, перебирающий индексы элементов массива от первого до последнего.

Обнуление всех элементов массива.

Перебираем все элементы массива и в каждый кладём ноль:

Обратите внимание — эта строка (for i := 1 to 10 do), перебирающая все элементы массива от первого индекса до последнего — будет использоваться практически во всех алгоритмах, обрабатывающих массив.

Ввод массива с клавиатуры.

Как и выше, требуется перебрать индексы всех элементов массива и ввести каждый с клавиатуры:

Задание элементов массива определённой последовательностью.

Заполним элементы массива последовательностью степеней числа 10 от нулевой до 9-й. Используем для этого вспомогательную переменную, в которой будем последовательно получать значение очередного элемента.

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

Заметим, что это решение, менее понятно только начинающим программировать.

Вывод массива на экран

Под термином “вывод массива на экран” понимается, вывод на экран всех элементов массива. В Паскале нельзя написать “writeln(A)”, чтобы все значения массива вывелись на экран. Как и в предыдущих случаях, требуется перебрать по очереди индексы всех элементов массива и вывести каждый на экран:

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

По окончании цикла ставим переход на следующую строку, чтобы последующие выводы программы на экран происходили с новой строки и не путались, попадая в конец строки, в который мы вывели массив.

Ещё раз обратите внимание! Программа должна выполнять именно то, что написано. Например, можно вывести на экран требуемые числа, просто запустив цикл от 10 до 1 в обратном порядке. Или заполнить массив числами от 1 до 10, а потом вывести элементы массива на экран в обратном порядке. Первое и второе решения — неверные. Программа должна заполнить массив указанными числами, а потом вывести результирующий массив в прямом порядке.

Подсчёт количества элементов массива

Посчитаем количество нечётных элементов массива. Для этого заведём переменную-счётчик. Перед циклом обнулим эту переменную. В цикле будем перебирать по очереди все элементы массива и проверять текущий элемент массива на нечётность. Если условие выполняется — увеличиваем счётчик на 1.

Вычисление суммы положительных элементов массива

Как и в случае с подсчётом количества элементов, создадим переменную для подсчёта суммы нужных элементов. Перед циклом не забудем присвоить ей начальное значение — ноль. В цикле переберём по очереди все элементы массива и проверим их на положительность. Если условие выполняется, добавляем значение проверенного элемента к сумме.

Нахождение максимального элемента массива

Как и при обработке последовательностей чисел, поиск максимального элемента массива выполняется по той же технологии. Создаётся переменная, предназначенная для хранения текущего значения максимального элемента массива. В качестве начального значения для этой переменной выбирается либо значение первого элемента массива, либо значение, выходящее за допустимый диапазон значений элементов массива.

После этого перебираются все оставшиеся элементы массива.

Каждый из них сравнивается с текущим значением максимума. Если текущий элемент оказывается больше, то текущее значение максимума меняется.

Рассмотрим основные реализации этой технологии.

1. Диапазон значений элементов не задан. Ищем максимум среди всех элементов. Начальное значение максимума — первый элемент массива:

2. Диапазон значений задан (например, -1000... +1000). Ищем максимум среди чётных элементов. Начальное значение максимума — выходящее за диапазон число (-1001):

max := -1001;

3. При поиске максимума в массиве иногда требуется найти не значение максимального элемента, а номер максимального элемента. Если такую задачу нужно решать для последовательности чисел, то придётся хранить оба значения — и номер максимума, и значение максимума. Но в массиве достаточно хранить только номер, потому что зная номер элемента массива, всегда можно получить значение этого элемента, написав “А[номер]”.

Ещё одна особенность при поиске номера максимального элемента — таких максимальных элементов в массиве может быть несколько. Поэтому в задаче должно быть отдельно сказано, что либо все элементы массива различные, либо при наличии нескольких максимальных элементов нужно найти, например, наименьший номер максимального элемента.

Найдём наименьший номер минимального элемента массива (используем для хранения этого номера переменную imax):

4. Если нужно найти номер максимального элемента массива с условием, то решение усложняется, потому что нельзя использовать обращение к текущему максимальному элементу как “А [imax]”, пока imax не будет хранить номер элемента массива, удовлетворяющего условию.

В этом случае удобнее не экономить на одной переменной, а хранить как номер максимального элемента, так и его значение.

Пример.

Найдём наименьший номер максимального нечётного элемента массива. Известно, что значения всех элементов массива лежат в диапазоне -1000...+1000.

Задание значений элементов массива числами, не связанными закономерностью

Если массив надо заполнить числами, которые никак друг с другом не связаны, то всегда можно написать столько операторов присваивания, сколько имеется элементов массива.

Допустим, требуется заполнить массив числами: 8, -102, 0, 754, 25, 71, 333, 94, 7, 19:

Разбор типовых задач

В таблице Dat представлены данные о количестве голосов, поданных за 10 исполнителей народных песен (Dat [1] — количество голосов, поданных за первого исполнителя; Dat [2] — за второго и т. д.). Определите, какое число будет напечатано в результате работы следующей программы.

Текст программы приведён на трёх языках программирования.

Алгоритмический язык	Бейсик
Паскаль

Решение

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

Оператор	Условие	Переменные		Пояснения
		m	k
m:= 0;		0		Переменная m получает начальное значение, равное нулю.
for k:=1 to 10 do	1≤10? Да		1	Начальное значение счётчика цикла
if Dat [k]>m then	16>0? Да			В этот момент k = 1. Обращаемся к элементу Dat [k], то есть Dat [1]. Элемент Dat [1] равен 16.
m:= Dat [k]		16		Меняем переменную m
for k:=1 to 10 do	2≤10? Да		2	Значение счётчика цикла равно 2
if Dat [k]>m then	20>16? Да			В этот момент k = 2. Обращаемся к элементу Dat [k], то есть Dat [2]. Элемент Dat [2] равен 20.
m:= Dat [k]		20		Меняем переменную m
for k:=1 to 10 do	3≤10? Да		3	Значение счётчика цикла равно 3
if Dat [k]>m then	20>20? Нет			В этот момент k = 3. Обращаемся к элементу Dat [k], то есть Dat [3]. Элемент Dat [3] равен 20. Значение m не меняется.
for k:=1 to 10 do	4≤10? Да		4	Значение счётчика цикла равно 4
if Dat [k]>m then	41>20? Да			В этот момент k = 4. Обращаемся к элементу Dat [k], то есть Dat [4]. Элемент Dat [4] равен 41.
m:=Dat[k]		41		Меняем переменную m
for k:=1 to 10 do	5≤10? Да		5	Значение счётчика цикла равно 5
if Dat [k]>m then	14>41? Нет			В этот момент k = 5. Обращаемся к элементу Dat [k], то есть Dat [5]. Элемент Dat [5] равен 14. Значение m не меняется.
for k:=1 to 10 do	6≤10? Да		6	Значение счётчика цикла равно 6
if Dat [k]>m then	21>41? Нет			В этот момент k = 6. Обращаемся к элементу Dat [k], то есть Dat [6]. Элемент Dat [6] равен 21. Значение m не меняется.
for k:=1 to 10 do	7≤10? Да		7	Значение счётчика цикла равно 7
if Dat [k]>m then	28>41? Нет			В этот момент k = 7. Обращаемся к элементу Dat [k], то есть Dat [7]. Элемент Dat [7] равен 28. Значение m не меняется.
for k:=1 to 10 do	8≤10? Да		8	Значение счётчика цикла равно 8
if Dat [k]>m then	12>41? Нет			В этот момент к = 8. Обращаемся к элементу Dat [k], то есть Dat [8]. Элемент Dat [8] равен 12. Значение m не меняется.
for k:=1 to 10 do	9≤10? Да		9	Значение счётчика цикла равно 9
if Dat [k]>m then	15>41? Нет			В этот момент k = 9. Обращаемся к элементу Dat [k], то есть Dat [9]. Элемент Dat [9] равен 15. Значение m не меняется.
for k:=1 to 10 do	10≤10? Да		10	Значение счётчика цикла равно 10
if Dat [k]>m then	35>41? Нет			В этот момент k = 10. Обращаемся к элементу Dat [k], то есть Dat [10]. Элемент Dat [10] равен 35. Значение m не меняется.
for k:=1 to 10 do	11≤10? Нет		11	Значение счётчика цикла равно 11. Цикл заканчивается.
writeln(m);				На экран выводится значение переменной m — 41

Ответ: 41.

Другой вариант решения задачи

Анализируем предлагаемую программу и видим, что приведённый алгоритм совпадает с уже знаковым нам алгоритмом нахождения максимального элемента массива. Среди значений элементов массива находим наибольшее значение. Это 41.

Ответ: 41.

Второй метод решения хорош только в том случае, когда приведённая в условии программа совпадает, с точностью до обозначений, с известным нам алгоритмом. Если же программа в условии содержит хоть какие-то, пусть даже на первый взгляд незначительные отличия, пользоваться таким методом опасно. Легко может оказаться, что это небольшое отличие в корне изменит результат работы программы. Например, на приведённых в условии данных.

Метод выполнения трассировки программы кажется нам гораздо надежнее и предпочтительнее.

Если вы хорошо умеете делать подробную трассировку и желаете сэкономить время, воспользуйтесь краткой трассировкой, без выписывания выполняемой команды и проверяемого условия. Просто заносите в столбцы таблицы изменяющиеся значения переменных.