Уроки 44 - 46
§22. Алгоритмы обработки массивов
Содержание урока
Сумма значений элементов массива
Подсчёт элементов массива, удовлетворяющих условию
Поиск максимального элемента в массиве
Практическая работа № 22 «Алгоритмы обработки массивов»
Практическая работа № 23 «Сумма значений элементов массива»
Практическая работа № 24 «Подсчёт элементов массива по условию»
Практическая работа № 25 «Поиск максимального элемента»
Поиск максимального элемента в массиве
Представьте себе, что вы по очереди заходите в N комнат, в каждой из которых лежит арбуз. Вес арбузов такой, что вы можете унести только один арбуз. Возвращаться в ту комнату, где вы уже побывали, нельзя. Как выбрать самый большой арбуз?
Итак, вы вошли в первую комнату. По-видимому, нужно забрать лежащий в ней арбуз. Действительно, вдруг он самый большой? А вернуться сюда вы уже не сможете. С этим первым арбузом вы идёте во вторую комнату и сравниваете, какой арбуз больше — тот, который у вас в руках или новый. Если новый больше, берёте его, а старый оставляете во второй комнате. Теперь в любом случае у вас в руках оказывается самый большой арбуз из первых двух комнат. Действуя так же и в остальных комнатах, вы гарантированно выберете самый большой арбуз из всех.
На этой идее основан и поиск максимального элемента в массиве 1). Для хранения значения максимального элемента выделим в памяти целочисленную переменную М. Будем в цикле просматривать все элементы массива один за другим. Если значение очередного элемента массива больше, чем максимальное из предыдущих (находящееся в переменной М), запомним новое значение максимального элемента в М.
1)Этот пример хорошо объясняет принцип поиска максимального элемента, но нужно учитывать, что, в отличие от предметов (арбузов), данные не исчезают в том месте, откуда они были скопированы.
Чего не хватает в этом фрагменте программы?
нц для i от 1 до N for i:= 1 to N do
если A[i]>M то if A[i]>M then
M:=A[i] M:=A[i];
все write(M);
КЦ
вывод M
Остаётся решить, каково должно быть начальное значение М.
Предположим, что вначале переменной М мы будем присваивать значение 0. Всегда ли это будет правильно?
Во-первых, можно записать в переменную М значение, заведомо меньшее, чем значение любого из элементов массива. Например, если в массиве записаны натуральные числа, можно записать в М ноль.
Во-вторых, если содержимое массива неизвестно, можно сразу записать в М значение А[1] (сразу взять первый арбуз), а цикл перебора начать со второго элемента:
М:=А[1] М:=А[1];
нц для i от 2 до N for i:=2 to N do
если A[i]>M то if A[i]>M then
M:=A[i] M:=A[i];
все write(M);
кц
вывод M
Будет ли в этой задаче ошибкой цикл, начинающий перебор с первого элемента?
Викентий решил написать первый оператор в предыдущем фрагменте так:
М:=А[N] М:=А[N];
Закончите программу Викентия.
Кирилл решил написать первый оператор в предыдущем фрагменте так:
M:=A[div(N,2)] M:=A[N div 2];
Закончите программу Кирилла.
Теперь найдём номер максимального элемента. Казалось бы, нужно ввести еще одну переменную nМах для хранения номера, сначала записать в нее 1 (считаем первый элемент максимальным) и затем, когда найдём новый максимальный элемент, запоминать его номер в переменной nМах:
М:=А[1]; nМах:= 1 М:=А[1]; nМах:=1;
нц для i от 2 до N for i:=2 to N do
если A[i]>M то if A[i]>M then begin
M:=A[i] M:=A[i];
nMax:=i nMax:=i
все end;
кц write ('A[', nMax, ']=', M) ;
вывод 'A[', nMax, ']=', M
Однако это не самый лучший вариант. Одна из переменных в этой программе лишняя.
Можно ли, зная значение максимального элемента массива М, сразу (без перебора!) найти его номер? Если да, то как?
Можно ли, зная номер максимального элемента массива nМах, сразу (без перебора!) найти его значение? Если да, то как?
По номеру элемента i можно всегда определить его значение, оно равно А[i]. Поэтому достаточно хранить только номер максимального элемента nМах, тогда его значение равно А[nМах]:
nМах:=1 nМах:=1;
нц для i от 2 до N for i:=2 to N do
если A[i]>A[nМах] то if A[i]>A[nМах] then
nMax:=i nMax:=i;
все write('A[', nMax, ']=',
кц A[nMax])
вывод 'A[', nMax, ']=', A[nMax]
Более сложная задача — найти максимальное значение не всех элементов массива, а только тех, которые удовлетворяют некоторому условию. Если вернуться к примеру с поиском арбуза: в некоторых комнатах лежат не арбузы, а дыни, но нужно найти именно самый большой арбуз. Это значит, что мы выбираем новый элемент, если он: а) подходит нам по условию отбора и б) больше, чем максимальный, найденный до этого.
Рассмотрим конкретную задачу: найти максимальный из отрицательных элементов массива.
Запишите в тетради для этой задачи условие обновления максимального значения в переменной М.
Самое сложное — определить, каким должно быть начальное значение М.
Предположим, что мы сначала записали в переменную М значение какого-либо элемента массива. Когда такой приём может дать неверный результат?
Выполните ручную прокрутку следующей программы:
М:=А[1] М:=А[1];
нц для i от 2 до N for i:=2 to N do
если A[i]<0 и A[i]>M то if (A[i]<0) and
M:=A[i] (A[i]>M)
все then
кц M:=A[i];
вывод M write(M);
для двух массивов (рис. 3.10).
Рис. 3.10
Удалось ли найти максимальный отрицательный элемент в первом случае? Во втором?
Итак, если первый элемент массива положительный (нам не подходит!), он оказывается больше всех подходящих элементов, и программа выводит его как результат. Но этот результат неверный! Есть два способа исправить программу.
Первый вариант: можно сначала найти первый отрицательный элемент, записать его в переменную М, а потом перебирать в цикле все оставшиеся.
Второй вариант проще — мы будем заменять значение М в том случае, если очередной элемент A[i] — отрицательный, а значение М — неотрицательное. Например, так:
М:=А[1] М:=А[1];
нц для i от 2 до N for i:=2 to N do
если A[i]<0 то if A[i]<0 then
если M>=0 или A[i]>M то if (M>=0) or (A[i]>M)
M:=A[i] then
все M:=A[i];
все write(M);
кц
вывод M
При каких значениях A[i] и М условия М>0 и A[i]>М во вложенном условном операторе могут выполниться одновременно?
Выделите все случаи, при которых в этой программе будет изменяться значение М.
Следующая страница 
Выводы. Интеллект-карта
Cкачать материалы урока
