Лекция 3. Массивы и матрицы. Итерационные циклы. (Воробьева И.А. - Информатика. Язык Паскаль)

1Воробьева И.А. «Информатика. Язык Паскаль»4. МАССИВЫ И ИТЕРАЦИОННЫЕ ЦИКЛЫ В ПАСКАЛЕ4.1. Итерационные циклы в ПаскалеИтерационный цикл – это цикл, в котором заранее не известночисло повторений тела цикла. Выход из итерационного циклаосуществляется при выполнении заданного условия. Выделяют два видаитерационных циклов – цикл с предусловием и цикл с постусловием.Цикл с предусловием проверяет условие ДО выполнения тела цикла.В Паскале это «условие выполнения цикла»:1) проверка условия → 2) тело цикла.Цикл с постусловием проверяет условие ПОСЛЕ выполнения цикла.В Паскале это «условие завершения цикла»:1) шаг цикла → 2)проверка условия.ЦИКЛ С ПРЕДУСЛОВИЕМЦИКЛ С ПОСТУСЛОВИЕМТЕЛО ЦИКЛАПРОВЕРКАУСЛОВИЯНетДаПРОВЕРКАУСЛОВИЯДаТЕЛО ЦИКЛАНетМожет ни разу не выполниться Один раз выполнится всегдаУсловие = TRUE → выполнитьУсловие = TRUE → завершить12Воробьева И.А. «Информатика. Язык Паскаль»Замечание 4.1.

Цикл с постусловием в других языках, например в языкеСи, проверяет не условие завершения цикла, а условие продолженияцикла. Все зависит от реализации конструкции, принятой в конкретномязыке. Поэтому, основным отличием итерационных циклов является: ДОили ПОСЛЕ выполнения тела цикла проверяется условие.Конструкции итерационных циклов в Паскале.ЦИКЛ С ПРЕДУСЛОВИЕМWHILE условие DO<операция >;i:=6;While i <=5 Dowrite(‘Не выполнится’);i:=5;While i <=5 Dowrite(‘выполняетсябесконечно’);WHILE условие DObegin<операция 1>;<операция 2>;…<операция N>;end;ЦИКЛ С ПОСТУСЛОВИЕМREPEAT<операция >;UNTIL условиеi:=6;Repeatwrite(‘выполняетсябесконечно’);Until i <=5i:=5;Repeatwrite(‘Один раз выполнится’);Until i <=5REPEAT<операция 1>;<операция 2>;…<операция N>;UNTIL условиеВАЖНО! Циклу Repeat..Until ненужны операторные скобкиBegin..End.23Воробьева И.А.

«Информатика. Язык Паскаль»4.2. Связь между параметрическим и итерационным цикламиПараметрический цикл можно реализовать с помощью конструкции«цикла с предусловием» — While..Do и «цикла с постусловием» —Repeat..Until. Нет никакого смысла в простом переписываниипараметрического цикла с помощью итерационного, так как конструкцияFOR была создана как раз для облегчения синтаксического чтения кода1программы в определенных видах циклов.

Однако знать о взаимосвязиполезно. Например, в языке Паскаль замена FOR на WHILE или REPEATвозникает в следующих случаях: если нужно изменить шаг параметрического цикла, который жесткорегламентирован в FOR, как «±1»; если нужно обеспечить досрочный выход из параметрического циклапри определенных условиях; если нужно взять под собственный контроль счетчик цикла, бытьуверенным в его значении после цикла, иметь возможность изменятьего содержимое не только на стандартный шаг приращения, а покакой-то более сложной логике.Замечание 4.2. По последнему пункту напомним, что в языке Паскальзначения счетчика конструкции FOR хоть и не зпрещено напрямуюизменять самостоятельно в теле цикла, однако поведение программногокода после этого никак не регламентировано.

Тоже самое касается изначения счетчика после завершения цикла FOR, например в кодеi:= -10;For i:=1 to 5 dowrite (‘Счетчик i используем, но не меняем. i= ‘, i:4);Z:= i;// не определено – Z будет равно: -10, 5 или 6.Замечание 4.3. Конечно, досрочный выход можно обеспечить и явнымGoto или скрытыми, что уже не так зазорно, операторами Goto, такими какBreak, Continue. Некоторые же, не зная, как правильно «готовить кошек»,умудряются использовать даже Exit и Halt «на ровном месте». Однако в1Так называемое понятие «компьютерный сахар».34Воробьева И.А. «Информатика.

Язык Паскаль»первой лекции мы уже обсудили почему не будем пока использоватьтакой подход в простейших программах.Замечание 4.4. Обратите внимание, что в инструкции While..Do требуютсяоператорные скобки begin-end для выполнения нескольких операторов втеле цикла, а в инструкции Repeat..Until этого не требуется, так как словаRepeat и Until одновременно сами являются операторными скобками.Рассмотрим реализацию всех трех конструкций циклов на примерезадачи суммирования элементов c четными индексами в одномерноммассиве A(n).ПАРАМЕТРИЧЕСКИЙ ЦИКЛЦИКЛ С ПРЕДУСЛОВИЕМA(n)A(n)Sum = 0i=1Sum=0i=1; +1; ni≤nНЕТНЕТДАi mod 2 =0НЕТДАSum = Sum + A[i]i mod 2 =0ДАSum = Sum + A[i]Suminc( i )Sumконецконец… // ввод n и массива ASum:= 0;for i:=1 to n doif i mod 2 = 0 thenSum:=Sum+A[i];write(‘Sum=’, Sum:6);……// ввод n и массива ASum:= 0;i:=1;while i <= n dobeginif i mod 2 = 0 thenSum:=Sum+A[i];inc(i):end;45Воробьева И.А.

«Информатика. Язык Паскаль»write(‘Sum=’, Sum:6);…Как видим, простое переписывание параметрического цикла витерационный цикл не дет ничего, кроме усложнения кода, однакоценность итерационного цикла в большей гибкости. Перепишем решениезадачи, чуть хитрее.ЦИКЛ С ПРЕДУСЛОВИЕМЦИКЛ С ПОСТУСЛОВИЕМA(n)ДАA(n)ДАn<2 НЕТSum = 0i=2i≤nn<2 НЕТSum = 0i=2НЕТSum = Sum + A[i]i=i+2ДАSum = Sum + A[i]i>ni=i+2‘Err_N’Sum‘Err_N’mНЕТДАSumконецконец… // ввод n и массива Aif n < 2 thenwrite(‘Ошибка размерности ’, n)else beginSum:= 0;i:= 2;while i <= n do beginSum:=Sum+A[i];i:= i+2;end;write(‘Sum=’, Sum:6);…// ввод n и массива Aif n < 2 thenwrite(‘Ошибка размерности ’, n)else beginSum:= 0;i:= 2;repeatSum:=Sum+A[i];i:= i+2;until i > n;write(‘Sum=’, Sum:6);56Воробьева И.А.

«Информатика. Язык Паскаль»end;…end;…Число строк кода стало даже больше, так как нам пришлосьпроверять, что размерность n не меньше двух. Но сам код сталэффективней с точки зрения, так называемой сложности алгоритма –оценки объема вычислений, зависящих от размера входных данных.В нашем случае размер входных данных – это длина массива. Новыйалгоритм делает в два раза меньше шагов, чем предыдущие, так какпросматривает не все, а только четные элементы. На самом деле, в науке,называемой теорией сложности алгоритмов, уменьшение числа шаговвдвое – практически неразличимо, но при построении алгоритма решениязадачи принято всегда придерживаться оптимального способа, если этоне влияет на какие-то иные характеристики в сторону ухудшения.Замечание 4.5.

Как правило, «иной характеристикой» является объемпамяти (особенно оперативной памяти компьютера), который потребуеталгоритм для своей работы. Вся оптимизация решений задач крутитсявокруг двух основных характеристик: скорости выполнения и объематребуемой памяти.Мы рассмотрели использование итерационного цикла дляизменения шага в диапазоне изменения счетчиков, сокращаябесполезный перебор и лишние проверки в массиве.

При необходимости,мы могли бы изменять шаг непосредственно в процессе просмотрамассива, например в задаче: «если в массиве встретится равный нулюэлемент с четным индексом, подсчитать суммы всех элементовмассива, стоящих после него». Приведем упрощенный фрагмент кодарешения этой задачи, без альтернативного решения. Вопрос: каким ономожет быть?VARn, i, step: byte;Sum: real;// размерность, индекс, шаг индекса// значение суммы элементов67Воробьева И.А.

«Информатика. Язык Паскаль»A: array[1..10] of real;BEGIN…// массив// ввод n (от 1 до 10) и массива A из вещественных чиселif n < 2 thenwrite(‘Ошибка размерности ’, n)else beginSum:= 0;// начальное значение суммыi:= 2;// начальное значение индексаstep:=2;// начальное значение шага индексаwhile i <= n do beginif step = 1 thenSum:= Sum+A[i]elseif A[i] = 0 thenstep:= 1;i:= i + step;end;write(‘Sum=’, Sum:6);end;…END.4.3. Досрочный выход из итерационного цикла.

Метод флажка«Условие» в инструкциях While..Do и Repeat..Until может быть какпростым, так и сложным – это переменные, константы или выражениялогического типа boolean.При решении задач с досрочным выходом из циклов используютсложное условие контроля счетчика и флага. Флаг – это, как правило,логическая переменная, которая свидетельствует о наличии илиотсутствии искомого признака.78Воробьева И.А. «Информатика. Язык Паскаль»Типичные задачиформулировкам:поискапризнакасводятсякдвумосновнымЗадача 1. найти хотя бы один элемент, удовлетворяющийусловию (вариации: первый, последний элемент);Задача 2.

проверить, что все элементы удовлетворяют условию.Этиформулировкивзаимозаменяемыивзаимообратны.Действительно, «проверить, что есть хотя бы один отрицательный(<0) элемент» обратно по смыслу «проверить, что все элементынеотрицательны (≥ 0)».Часто формулировки явно не выделены именно такими фразами, новсе равно решение сводится либо к поиску решения задачи 1, либо задачи2.Пример 4.1. «Проверить, что массив упорядочен по возрастанию» – это,по сути, или найти первую неупорядоченную пару (задача 1) илипроверить, что все элементы упорядочены (задача 2).Какой вопрос по уточнению задачи должен возникнуть2?Пример 4.2.