урок 05.02.25
тема: Типовые алгоритмы обработки массивов
2.2.4. Вычисление суммы элементов массива
Пример. В некотором населённом пункте я домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта количества жителей населённого пункта.
Исходные данные (количество жильцов) здесь представлены с помощью одномерного массива а, содержащего n элементов: a[1] — количество жильцов дома 1, а[2] — количество жильцов дома 2, ..., а[n] — количество жильцов дома n. В общем случае a[i] — количество жильцов дома n, где i принимает целочисленные значения от 1 до n (кратко обозначим это в блок-схеме как 
). Результат работы алгоритма обозначен через s.
Суммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых:
1) определяется ячейка памяти (переменная s), в которой будет последовательно накапливаться результат суммирования;
2) переменной s присваивается начальное значение 0 — число, не влияющее на результат сложения;
3) для каждого элемента массива из переменной s считывается её текущее значение и складывается со значением элемента массива; полученный результат присваивается переменной s.
Описанный процесс наглядно можно изобразить так:
Запишем соответствующую программу на языке Паскаль.
Сравните программы n_2 и n_3. Выделите в них общие блоки. Обратите внимание на различия.
Каким образом в программе n_3 уточнена информация, представленная в примере о домах населённого пункта?
2.2.5. Последовательный поиск в массиве
В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.
Можно выделить следующие типовые задачи поиска:
1) найти наибольший (наименьший) элемент массива;
2) найти элемент массива, значение которого равно заданному значению.
Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.
Рассмотрим подробно решение задач первого типа: нахождение наибольшего (наименьшего) элемента.
Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
1) возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;
2) возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и запишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;
3) повторим действия, описанные в п. 2, для всех оставшихся карточек в стопке.
В итоге на доске будет записано самое большое значение элемента просмотренного массива.
В программировании при обосновании корректности циклических алгоритмов используется понятие инварианта цикла.
Инвариант цикла — логическое выражение (условие), зависящее от переменных, изменяющихся в теле цикла; оно истинно непосредственно перед началом выполнения цикла и после каждого прохода тела цикла.
Условие «записанное на доске число — самое большое из всех просмотренных до сих пор» является инвариантом цикла для рассмотренного алгоритма.
Так как доступ к значению элемента массива осуществляется по его индексу, при организации поиска наибольшего элемента в одномерном массиве можно искать его индекс. Обозначим искомый индекс imax. Тогда описанный выше алгоритм в сформированном нами массиве а на языке Паскаль можно записать так:
Если в массиве несколько элементов, значения которых равны максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы в ней находился последний из максимальных элементов. Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива?
Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
• k — индекс элемента массива такой, что a[k] = х, где х — заданное число;
• сообщение о том, что искомого элемента в массиве не обнаружено.
Программа поиска в сформированном нами массиве а значения, равного х, может выглядеть так:
В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдёт последний из них.
Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующий фрагмент программы:
Здесь выполнение алгоритма будет прервано в одном из двух случаев: 1) в массиве найден первый из элементов, равный заданному; 2) все элементы массива просмотрены.
Запишите полный текст программы и выполните её на компьютере.
Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.
Определите, количество каких элементов подсчитывается с помощью следующего фрагмента программы.
Если требуется определить сумму значений элементов, удовлетворяющих некоторому условию, то вводят переменную, к значению которой прибавляют значение найденного элемента массива.
Определите, какому условию удовлетворяют элементы массива, значения которых суммируются с помощью следующего фрагмента программы.
Запишите полные тексты двух последних программ и выполните их на компьютере.
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Какими слайдами вы могли бы дополнить презентацию?
2. Может ли массив одновременно содержать целые и вещественные значения?
3. Для чего необходимо описание массива?
4. Что вы можете сказать о массиве, сформированном следующим образом?
а) for i:=l to 10 do a[i]:=random(101)-50;
б) for i:=l to 20 do a[i]:=i;
в) for i:=l to 5 do a[i]:=2*i-l;
5. Напишите программу, которая вычисляет среднюю за неделю температуру воздуха. Исходные данные вводятся с клавиатуры.
6. Дан массив из десяти целых чисел. Напишите программу подсчёта количества элементов этого массива, имеющих максимальное значение.