Циклические алгоритмы и программы
Циклом называется многократно повторяющийся фрагмент
алгоритма или программы. Те действия, которые повторяются, называ-
ются телом цикла (ТЦ).
В программировании различают три типа циклов:
1) с предусловием («пока»);
2) с постусловием («до»);
3) с параметром («для»).
Первые два типа циклов объединяют в одну группу, называемую
циклами «по условию», или циклами, число повторений которых не из-
вестно перед началом выполнения цикла, а определяется истинностью
(ложностью) некоторого условия. Переменная, от значения которой
зависит истинность условия (следовательно, и окончания цикла) называ-
ется управляющей переменной цикла. Третий тип цикла называют цик-
лом с заранее известным числом повторений – количество повторений
определено в законе изменения управляющей переменной, которая но-
сит специальное название – параметр. Параметр изменяется в заданном
диапазоне с определенным шагом.
Рассмотрим блок-схемы циклов каждого типа, обобщенный
формат их записи на языке Паскаль и алгоритмы их работы.
1) цикл с предусловием («пока»);
Циклические алгоритмы и программы
Циклом называется многократно повторяющийся фрагмент
алгоритма или программы. Те действия, которые повторяются, называ-
ются телом цикла (ТЦ).
В программировании различают три типа циклов:
1) с предусловием («пока»);
2) с постусловием («до»);
3) с параметром («для»).
Первые два типа циклов объединяют в одну группу, называемую
циклами «по условию», или циклами, число повторений которых не из-
вестно перед началом выполнения цикла, а определяется истинностью
(ложностью) некоторого условия. Переменная, от значения которой
зависит истинность условия (следовательно, и окончания цикла) называ-
ется управляющей переменной цикла. Третий тип цикла называют цик-
лом с заранее известным числом повторений – количество повторений
определено в законе изменения управляющей переменной, которая но-
сит специальное название – параметр. Параметр изменяется в заданном
диапазоне с определенным шагом.
Рассмотрим блок-схемы циклов каждого типа, обобщенный
формат их записи на языке Паскаль и алгоритмы их работы.
1) цикл с предусловием («пока»);
При выполнении цикла «пока» сначала вычисляется значение бу-
левского выражения. Если оно принимает значение True , то выполняет-
ся тело цикла и снова вычисляется значение булевского выражения. Ес-
ли оно принимает значение False, то цикл заканчивается. То есть тело
цикла повторяется до тех пор, пока булевское выражение истинно.
Как только оно станет ложно – цикл закончится.
Возможна такая ситуация, что тело цикла не выполнится ни ра-
зу, а именно, в том случае, если булевское выражение сразу примет зна-
чение False.
В теле цикла и булевском выражении присутствует переменная,
называемая управляющей переменной цикла. Перед началом цикла ей
задается некоторое значение – начальное присваивание, а в теле цикла
обязательно должен быть оператор, изменяющий значение управ-
ляющей переменной по некоторому закону. Обычно этот оператор –
последний в теле цикла. Если значение управляющей переменной не
изменять, то возникает ситуация зацикливания – тело цикла будет по-
вторяться бесконечное число раз, так как не будет изменяться значение
зависящего от этой переменной булевского выражения, определяющего
условие продолжения (окончания) цикла.
Поэтому на начальных этапах изучения программирования для
уменьшения количества ошибок в составлении циклических программ с
методической точки зрения целесообразно выделить еще два блока, об-
разующих этот цикл:
1. блок начальных присваиваний (НП);
2. блок изменения управляющей переменной цикла (ИП);
С учетом этого в самом общем виде структура цикла пока на языке
блок-схем и соответственно Паскале для вычислительных алгоритмов
представляется следующим образом:
Анализ задач на составление алгоритмов с циклом «пока» це-
лесообразно проводить по схеме:
1. Определить действия, образующие тело цикла (ТЦ) и выделить
в них изменяющуюся переменную.
2. Проанализировать блоки начальных присваиваний (НП) и из-
менения управляющей переменной (ИП).
3. Записать условие продолжения (У) и условие окончания цикла.
При выполнении цикла «до» сначала выполняется тело цикла,
а потом вычисляется значение булевского выражения. Если значение
булевского выражения ложно, то снова выполняется тело цикла, если
истинно – то цикл заканчивается. То есть тело цикла повторяется до
тех пор, пока булевское выражение ложно. Как только оно станет ис-
тинным – цикл закончится.
В отличии от цикла «пока» в этом цикле тело цикла выполняется
хотя бы один раз всегда. Еще одно отличие – цикл «пока » повторяется
до тех пор, пока условие истинно, а цикл «до» - пока условие ложно.
То есть в цикле «пока» после ключевого слова while записывается
условие продолжения цикла, а в цикле «до» после ключевого слова
until записывается условие окончания цикла. В остальном эти циклы
схожи.
3) цикл с параметром («для»)
Следует заметить, что цикл с параметром в разных языках програм-
мирования реализован по-разному. В языке Паскаль накладываются до-
вольно-таки жесткие ограничения на переменную-параметр цикла и шаг
его изменения. Поэтому здесь мы рассмотрим сначала общую форму
цикла «для» на языке блок-схем и алгоритм его работы, а особенности
его реализации в языке Паскаль будут рассмотрены в следующем пара-
графе.
Напомним, что вытянутый шестиугольник на языке блок-схем
означает блок модификации параметра.
Здесь
ТЦ - тело цикла;
<параметр> - это переменная, изменяющаяся на некотором интервале
(диапазоне) по заданному закону (играет роль управляющей переменной
для этого типа цикла);
НЗ и КЗ - начальное и конечное значения диапазона изменения
параметра, причем начальное значение может быть как меньше
конечного, так и больше;
Ш – шаг изменения параметра, может быть как положительным, так и
отрицательным.
Алгоритм выполнения цикла "для":
Обозначим p-параметр
p:= НЗ;
p внутри отрезка [НЗ, КЗ] ?
если "да", то к п.3, если "нет", то конец
3. выполняется ТЦ
4.
p:= p+шаг;
5.
К п.2;
1.
2.
цикла;
Замечания
1) Следует обратить внимание на связь между значениями пара-
метра и количеством повторений тела цикла
51
n :=целая часть(abs(КЗ - НЗ))/шаг+1.
2) В блоке модификации (изменения) параметра цикла по сути дела
объединены блоки НП, ИП и У циклов с потсусловием и пред-
условием (автоматически реализуется механизм изменения
управляющей переменной и работы цикла). Поэтому существует
правило: в теле цикла параметр цикла изменять нельзя!
Реализация циклических алгоритмов в языке Паскаль.
Примеры.
Рассмотрим более подробно реализацию каждого из типов цик-
лов в языке Паскаль (теоретически и на примерах).
Цикл с параметром («для»)
Цикл с параметром в Паскале имеет две формы:
for <параметр>:= <НЗ> to <КЗ> do <ТЦ>;
for <параметр>:= <НЗ> downto <КЗ> do <ТЦ>;
Здесь <ТЦ> (тело цикла) – простой или составной оператор. Если
он составной, то нужно не забывать ставить операторные скобки begin-
end;
<параметр> - это переменная любого простого скалярного типа,
кроме вещественного;
<НЗ> и <КЗ> - начальное и конечное значения диапазона измене-
ния параметра, причем начальное значение может быть как меньше ко-
нечного, так и больше:
to - используется, если НЗ< КЗ,
downto – используется, если НЗ> КЗ.
Соответственно, при использовании служебного слова to при каж-
дом следующем повторении цикла параметр изменяется по закону:
<параметр>:= succ(<параметр>);
При использовании downto – по закону:
<параметр>:= pred(<параметр>).
Очевидно, что в том случае, когда параметром цикла является перемен-
ная целого типа, значение параметра изменяется либо с шагом +1 (to),
либо -1 (downto), то есть параметр выступает в качестве счетчика числа
повторений цикла.
Таким образом, тело цикла выполняется столько раз, сколько значе-
ний элементов соответствующего параметру типа лежат в диапазоне (на
отрезке) <НЗ> - <КЗ>.
1)
2)
52
Пример 1. Составить программу, последовательно выводящую на экран
малые буквы латинского алфавита: сначала от начала к концу алфавита,
а потом – наоборот:
Program cikl_param;
var c:char; {c-параметр цикла}
Begin
Writeln(‘латинский алфавит по возрастанию’);
For c:=’a’to ‘z’ do write(c:2);{отводим 2 позиции на символ, чтобы
между буквами был пробел}
Writeln;{переводим строку}
Writeln(‘латинский алфавит по убыванию’);
For c:=’z’ downto ‘a’ do write(c:2);
Writeln
end.
Протокол работы программы:
Пример 2. Составить программу построения таблицы значений функции
y = sin( x) на отрезке [ a, b ] с шагом h .
В данном примере требуется вычислить и вывести на экран значе-
ния функции y = sin( x ) при x=a, a+h, a+2h и т.д.. То есть независимая
переменная х изменяется от НЗ=а до КЗ=b с некоторым шагом h . Эту
переменную можно было бы взять в качестве параметра, если бы она
была целого типа и шаг был бы равен +1 или -1. В общем же случае х –
переменная вещественного типа и шаг отличен от 1. Однако можно под-
считать количество точек N в таблице – определить, сколько шагов дли-
ной h укладывается на отрезке [a,b] и добавить 1 (точек на 1 больше,
учитывая крайние две):
N=trunc((b-a)/n) + 1;
(здесь функция trunс выделяет целую часть в том случае, когда длина
отрезка не кратна величине шага).
53
Для решения задачи будем использовать цикл с параметром i –
счетчиком количества узловых точек таблицы, изменяющимся от 1 до N.
До начала цикла зададим x начальное значение а (x:=a) и после каждого
повторения тела цикла будем увеличивать значение х на шаг, то есть
изменять по закону: х:=х+h.
Значения переменных a,b,h вводим с клавиатуры.
Program tab_func;
var x,y,a,b,h : real; i,n : integer;
begin
write(‘введите границы отрезка и шаг: ’);
readln(a,b,h);
n:= trunc((b-a)/h) + 1;
x:=a;{начальное присваивание}
for i:=1 to n do
begin {начало тела цикла}
y:=sin(x);{вычисление функции}
writeln(x:6:2, y:6:2);{вывод на экран}
x:=x+h; {изменение значения х}
end;{конец цикла}
end.
Протокол работы программы:
Циклы с предусловием («пока») и постусловием («до»)
Как отмечено выше, в том случае, когда некоторую последователь-
ность действий надо повторять до тех пор, пока истинно (или ложно)
54
некоторое условие, используются циклы типа «пока» или «до». При этом
заранее не известно, сколько повторений будет выполнено.
Цикл «пока» в языке Паскаль имеет следующий формат:
while <булевское выражение> do <ТЦ>;
здесь
<ТЦ>- тело цикла – простой или составной оператор (в случае со-
ставного не забывайте использовать операторные скобки).
Пример1. Вычислить сумму S=1+2+3+4+... . Вычисления прекра-
тить, как только значение S станет больше заданного числа х (х вводится
с клавиатуры). Дополнительно определить, сколько слагаемых просум-
мировано.
Согласно рассмотренной в предыдущем параграфе схеме, анализ
циклических алгоритмов следует начинать с выяснения того, какие дей-
ствия необходимо повторять, то есть какие действия образуют тело цик-
ла. Данная задача относится к обширному классу типовых задач
программирования – задач на вычисление сумм (произведений). При
вычислении сумм в теле цикла всегда к значению суммы добавляется
одно (очередное) слагаемое с помощью присваивания вида
S:=S+<слагаемое>. Для конкретной суммы обычно это слагаемое явля-
ется выражением, зависящим от значения некоторой переменной вели-
чины. Поэтому следует записать тело цикла и продумать, как будет из-
меняться участвующая в теле цикла независимая переменная величина
при каждом новом повторении цикла.
В нашей задаче к сумме добавляется сначала 1, потом 2, потом - 3 и
т.д., то есть в общем виде – переменная k, которая при каждом повторе-
нии цикла увеличивается на 1. То есть тело цикла имеет вид S:=S+k. До
начала цикла следует выполнить начальное присваивание k:=1, а перед
каждым новым повторением цикла изменять ее по закону k:=k+1. Усло-
вие окончания цикла: S>x, а соответственно условие продолжения -
S<=x (взаимно противоположное условие):
Program pr1_cikl_poka;
Var x,S,k : integer;
Begin
Write(‘введите x ‘); readln(x);
S:=0;{сумму всегда обнуляем перед циклом}
k:=1; {первое слагаемое}
while S<=x do
begin
S:=S+k;
55
k:=k+1
end;
writeln(‘сумма = ‘,S, ‘число слагаемых ‘,k-1);
end.
Замечание: Обратите внимание, что значение k по окончании цикла на
единицу больше, чем число просуммированных слагаемых. Можно было
значению k до начала цикла присвоить 0, тогда в теле цикла сначала бы
надо было увеличивать k на единицу, а потом добавлять его к сумме.
По окончании цикла число слагаемых было бы равно k (самостоятельно
составьте этот вариант программы).
Пример 2. Составить программу, подсчитывающую сумму цифр
некоторого натурального числа N.
Количество цифр в числе неизвестно, поэтому в теле цикла мы бу-
дем выполнять следующие действия:
1) выделять из числа крайнюю правую цифру при помощи опера-
ции c:=N mod 10;
2) добавлять её к сумме: S:=S+c;
3) «отбрасывать»
эту
цифру
при
помощи
оператора
N:=N div 10.
Продолжать этот процесс будем до тех пор, пока число N не станет рав-
ным 0.
Таким образом, необходимо организовать цикл «пока», условием
продолжения которого является ненулевое значение числа N, то есть
условие N<>0 ( условие окончания – N=0).
Program sum_cifr;
Var N:longint; c,s:byte;
Begin
Write(‘Введите число ’);
Readln(N);
S:=0;{начальное присваивание для суммы}
While N<>0 do
Begin
C:=N mod 10;
S:=s+c;
N:=N div 10
End;
Writeln(‘сумма цифр равна ’,s)
End.
56
Теперь рассмотрим второй цикл – с постусловием («до»).
Напомним, что цикл «до» в языке Паскаль имеет следующий формат:
repeat
<тело цикла>
until <булевское выражение>;
здесь ключевое слово repeat переводится – повторять, until-до:
Тело цикла повторяется до тех пор, пока булевское выражение
ложно. Как только оно станет истинным – цикл закончится. В отли-
чии от цикла «пока» в этом цикле тело цикла выполняется хотя бы один
раз всегда. В цикле «пока» после ключевого слова while записывается
условие продолжения цикла, а в цикле «до» после ключевого слова until
записывается условие окончания цикла.
Пример 3. В качестве примера проиллюстрируем, как рассмотрен-
ный выше пример 1 реализуется с помощью цикла «до», внося по ходу
программы операторы-комментарии:
Program pr1_cikl_do;
Var x,S,k : integer;
Begin
Write(‘введите x ‘); readln(x);
S:=0;{сумму всегда обнуляем перед циклом}
k:=0; {подготовка слагаемых}
repeat {начинаем цикл}
k:=k+1;{увеличиваем слагаемое на 1}
S:=S+k;{добавляем к сумме}
until S>x ;{условие окончания цикла}
writeln(‘сумма = ‘,S, ‘ число слагаемых ‘,k);
end.
Замечание: Ключевые слова repeat-until играют роль операторных ско-
бок для тела цикла.
Пример 4. Дано действительное число х. Составить программу, вычис-
ляющую произведение:
P=x*(x+0.2)*(x+0.4)*(x+0.6)*...*(x+1.8)*(x+2)
Для накапливания (вычисления) произведений в теле цикла в общем
случае используем оператор вида:
P:=P*<очередной сомножитель>
В данном примере: P:=P*(x+a), где a – переменная величина, которая
для первого сомножителя равна 0, для второго – 0.2, для третьего – 0.4 и
т.д.. То есть она изменяется по закону: а:=а+0.2, конечное значение рав-
57
но 2. Начальные присваивания: для произведения P:=1, для управляю-
щей переменной а:=0. Условие окончания цикла: a>2.
program proizv_cikl_do;
Var a,P,x: real;
begin
Write(‘введите x=’); readln(x);
P:=1; a:=0;
Repeat
P:=P*(x+a);
a:=a+0.2
until a>2;
writeln(P, a)
end.
