Алгоритмы и их свойства (стр. 9 )

§7. Циклические алгоритмы

Рассмотрим пример: «Вычислить длины 25 концентрических окружностей с центрами в начале координат и целочисленными радиусами от 1 до 25». Эту задачу можно решить, используя линейный алгоритм, в котором 25 раз повторятся следующие действия:

а) получить радиус окружности: R1 = 1, Rn+1 = Rn + 1;

б) вычислить длину окружности: Ln = 2pRn;

в) сообщить результат.

Очевидно, что алгоритм получится довольно длинным. Возникает вопрос: «Нельзя ли заменить 25 повторяющихся последовательностей действий одной конструкцией?». Решить этот вопрос позволяет циклический алгоритм (цикл).

Циклический алгоритм (цикл) – алгоритм, в котором некоторая последовательность команд повторяется несколько раз.

Составной частью циклического алгоритма могут быть линейный или разветвляющийся алгоритмы.

Примеры:

1) заучивание стихотворения;

2) круговорот воды в природе;

3) составление таблицы умножения.

Графически циклический алгоритм реализуется одноименной структурой – цикл.

Последовательность повторяющихся действий называется телом цикла.

Циклические алгоритмы делятся на два типа:

1)  циклы с параметром;

2)  циклы с условием.

§7.1. Циклы с параметром

Цикл с параметром – цикл, окончание которого определяется сравнением параметра цикла с наперед заданным числом.

В цикле с параметром заранее известно число повторений, поэтому его еще называют арифметический цикл или цикл со счетчиком.

Блок-схема

Псевдокод НЦ для <УП> от <НЗ> до <КЗ> шаг <Ш> <ТЕЛО ЦИКЛА> КЦ <УП> - управляющая переменная (параметр цикла) <НЗ> - начальное значение <КЗ> - конечное значение <Ш> - шаг изменения параметра цикла (может быть равен 1 или -1) <УП>, <НЗ> и <КЗ> должны иметь тип INTEGER

Запись на Паскале

1 вариант FOR <УП> := <НЗ> ТО <КЗ> DO <ТЕЛО ЦИКЛА>;

2 вариант FOR <УП> := <НЗ> DOWNТО <КЗ> DO <ТЕЛО ЦИКЛА>;

Выполнение арифметического цикла:

1 вариант

1) В начале выполнения цикла значение переменной <УП> устанавливается равным <НЗ>.

2) Если значение <УП> меньше или равно <КЗ>, выполняется тело цикла, значение <УП> увеличивается на 1

3) Если значение <УП> стало больше <КЗ>, то цикл завершается, иначе переход к п.2

2 вариант

1) В начале выполнения цикла значение переменной <УП> устанавливается равным <НЗ>.

2) Если значение <УП> больше или равно <КЗ>, выполняется тело цикла, значение <УП> уменьшается на 1

3) Если значение <УП> стало меньше <КЗ>, то цикл завершается, иначе переход к п.2

Таким образом,

в 1 варианте значение УП должно увеличиваться, и оператор цикла будет выполняться при НЗ<=КЗ (завершение при УП > КЗ) во 2 варианте значение УП должно уменьшаться, и оператор цикла будет выполняться при НЗ>=КЗ (завершение при УП < КЗ) если НЗ=КЗ, то цикл будет выполнен один раз во всех других случаях оператор цикла выполняться не будет.

Если тело цикла содержит более одного оператора необходимо использовать составной оператор.

Рассмотрим план решения задачи о концентрических окружностях.

1) Математическая модель

R1 = 1, Rn+1 = Rn + 1;

Ln = 2pRn;

2) Словесный алгоритм

а) НЦ для R от 1 до 25

вычислить длину окружности

вывести результат

КЦ

б) конец

3) таблица величин

r	радиус окружности	промежуточная (УП)
pi	p	константа
l	длина окружности	результат

4) Блок-схема

5) Программа

Program okruzh;

uses crt;

var r: integer;

l: real;

Begin

clrscr;

for r := 1 to 25 do

begin

l:=2*pi*r;

writeln(‘длина окружности радиуса’,r,’равна ‘,l:5:2);

end;

End.

Рассмотренный пример демонстрирует важную особенность оператора арифметического цикла в языке Паскаль: значение управляющей переменной нельзя изменять в теле цикла.

Типовые задачи на использование арифметического цикла.

Пример 1. Вычисление суммы ряда.

Ряд – сумма определенного числа слагаемых:

Program summa;

uses crt;

var n, s: integer;

Begin

clrscr;

s:=0;

for n:=1 to 50 do s:=s+sqr(n);

writeln(‘Сумма ряда равна ‘,s);

End.

Задание. Как изменится программа, если N принимает значения от 1 до K?

Пример 2. Вычисление факториала числа (N!)

Факториалом натурального числа N называется произведение N первых натуральных чисел, например 5! = 1×2×3×4×5=120

Program factorial;

uses crt;

var n, i: integer;

p: longint;

Begin

clrscr;

write(‘Факториал какого числа будем искать’);readln(n);

p:=1;

for i:=1 to n do p:=p*i;

writeln(n,’!= ‘, p);

End.

Значение факториала – быстро увеличивающаяся величина, поэтому его значение (p) задано как длинное целое.

Пример 3. Табулирование функции.

Табулирование – составление значений функции на данном отрезке [a, b] с заданным шагом h.

«Выполнить табулирование функции y = x2 + 5 на отрезке [-5, 5] с шагом 0.5»

В этой задаче начальное значение цикла равно 0, конечное значение определяется по формуле:

Program tabul;

uses crt;

var i, n: integer;

a, b,h, x,y: real;

Begin

clrscr;

write(‘Введите границы отрезка и шаг’);readln(a, b,h)

x:=a; n:=trunc((b-a)/h);

writeln(‘Табулирование функции y = x^2 + 5’);

writeln(‘----------------‘);

writeln(‘ x y ’);

writeln(‘----------------‘);

for i:=0 to n do

begin

y:=sqr(x)+5;

writeln(‘ ’,x:4:1,‘ ’,y:5:2);

x:=x+h;

end;

writeln(‘----------------‘);

End.

Кроме линейных в тело цикла могут входить и разветвляющиеся алгоритмы.

Пример 4. Простое число.

Натуральное число n является простым, если оно не имеет делителей от 2 до . Для решения этой задачи будет использована специальная переменная f, которая называется флажок, принимающая два значения 0 – флажок опущен (нет делителей) или 1 – флажок поднят (есть хотя бы один делитель). Составим программу, определяющую, является ли данное число простым:

Program prostoe;

uses crt;

var i, n,f: integer;

Begin

clrscr;

write(‘Введите натуральное число’); readln(n);

f:=0; {опускаем флажок}

for i:=2 to n div 2 do if n mod i=0 then f:=1;

if f = 0 then writeln(‘Число’,n,’является простым’)

else writeln(‘Число’,n,’не является простым’);

End.

Циклический алгоритм сам может быть телом цикла, в этом случае говорят о вложенных циклах.

Пример 5. Совершенные числа

Совершенным называется натуральное число равное сумме всех своих положительных делителей, кроме самого себя, например число 28 = 1 + 2 + 4 + 7 + 14

«Найти среди первых 500 чисел совершенные» (6, 28, 496)

Program sovershennoe;

uses crt;

var i, k,j: integer;

Begin

clrscr;

writeln(‘Совершенные числа от 1 до 500:’);

for i:=2 to 500 do

begin

k:=0;

for j:=1 to i–1 do if i mod j=0 then k:=k+j;

if k=i then writeln(i);

end;

End.

Вопросы:

Какой алгоритм называется циклическим? Приведите примеры циклических алгоритмов. Что такое тело цикла? Какой цикл называется арифметическим? Как графически реализуется арифметический цикл? Какой оператор используется для записи арифметического цикла на языке Паскаль? Какие варианты записи имеет оператор арифметического цикла, в чем их отличие? Как «работает» арифметический цикл? Какая информация записывается после служебных слов for, to (downto) и do в операторе цикла? Чему равен параметр цикла при выходе из него:
а) в 1-м варианте, б) во 2-м варианте? Сколько раз выполниться цикл, если <НЗ> = <КЗ>? Можно ли менять значение управляющей переменной в теле цикла? Что необходимо использовать, если тело цикла содержит несколько команд? Приведите примеры типовых задач с использованием арифметического цикла. Может ли в тело цикла входить оператор перехода по условию (с примером)? Как называется цикл, входящий в тело другого цикла (пример)?

Задания

1. Что будет выведено на экран после выполнения фрагментов программ (воспользоваться трассировочными таблицами):

а) b:= 0; for a:=1 to 10 do b:=b+2; write(b);	б) y:= 0; for x:=3 to 15 do y:=y + x; write(y);	в) n:=0; for i:=10 downto 0 do begin m:=i-2; n:=n+m; end; writeln(n);	г) b:= 0; for a:=5 to 5 do b:=b + 10; writeln(b);
д) for i:=12 downto 4 do begin x:=2*i; writeln(i, x); end;	е) p:=0; for i:=1 to 7 do p:=p*i; writeln(p);	ж) s:= 0; for i:=1 to 25 do if i mod 5 = 0 then s:= s + i; writeln(s);	з) for i:=2 to 3 do for j:=1 to 9 do writeln(i,’*’,j,’=’, i*j);

2. По приведенным блок-схемам составить программы и получить результаты.