Моделирование цикла for с помощью цикла while

for x:=x1 to x2 do
оператор

эквивалентно

x:=x1;
while x<=x2 do
begin
оператор
x:=x+1;
end;

Моделирование цикла repeat с помощью цикла while

repeat
S
until B;

эквивалентно

S;
while not B do
S;

Зацикливание

repeat
write(i);
until False;

или

while True do
write(i);

Примеры использования циклов

Пример 1. Сумма n чисел.

s:=0;
for i:=1 to n do
s:=s+xi

Пример 2. Произведение n чисел.

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

Пример 3. n!!=n*(n-2)*(n-4)*...*2 (или 1)

p:=1;
x:=n;
while x>=2 do
begin
p:=p*x;
x:=x-2;
end;

Пример 4. Сколько нечетных среди 10 введенных.

c:=0;
for i:=1 to n do
begin
read(x);
if x mod 2 <> 0 then
c:=c+1;
// if Odd(x) then Inc(c); // вариант
end;

Пример 5. Защита от неверного ввода.

repeat
write('Введите x (>0): ');
readln(x);
if x<=0 then
writeln('Неверный ввод');
until x>0;

Пример 6. Табулирование функции f(x) на отрезке [a,b] в точках, разбивающих [a,b] на N частей.

assert(N>0);
h:=(b-a)/N;
x:=a;
for i:=0 to N do
begin
writeln(x:5:2, f(x):10:4);
x:=x+h;
end;

Пример 7. Вывод 10 первых степеней двойки.

x:=10;
for i:=1 to 10 do
begin
writeln(i:2,x:5);
x:=x*2;
end;

Пример 8. Вывод всех двузначных чисел, кратных 5.

x:=1;
while x<100 do
begin
write(x:3);
x:=x+5;
end;

Пример 9. Вывести n первых чисел Фибоначчи. Числа Фибоначчи определяются следующим образом:

a:=1;
b:=1;
write(1,' ',1,' ');
for i:=3 to n do
begin
c:=a+b;
write(c,' ');
a:=b;
b:=c;
end;

Пример 10. Найти сумму цифр целого положительного числа.

read(m);
S:=0;
while m>0 do
begin
S:=S + m mod 10;
m:=m div 10;
end;

Пример 11. Найти НОД (А,В), где А,В - целые положительные.

Алгоритм Евклида: НОД (А,В) = НОД (В, А mod B); НОД (А,0)=А

read(A,B);
repeat
C:=A mod B;
A:=B;
B:=C
until C=0;
NOD:=A;

Замечание. Доказательство того, что цикл завершится: С уменьшается на каждом шаге, оставаясь >=0.

Пример 12. Найти max из N введенных чисел.

Алгоритм 1. max:= первое введенное

read(x);
max:=x;
// Инвариант I: max = максимальное из всех введенных
for i:=2 to N do
begin
read(x);
if max:=x then
max:=x
// I выполняется
end;

Алгоритм 2. max:= самое маленькое число (-MaxInt или -MaxDouble)

for i:=1 to N do
...

Пример 13. Разложение числа на простые множители.

Алгоритм на псевдокоде

цикл
если х делится на i, то
{
вывод i
x:=x/i
}
иначе увеличить i на 1
до х=1

Алгоритм на Паскале

read(x);
assert(x>1);
i:=2;
repeat
if x mod i = 0 then
begin
write(i,' ');
x:=x div i;
end
else Inc(i);
until x=1;

Пример 14. Даны a₀,..., a_n, x Вычислить значение многочлена f(x)=a₀xⁿ+a₁x^n-1+...+a_n в точке x.

Схема Горнера: f(x)=(...((a₀x+a₁)x+a₂)x+a₃...)x+a_n

read(x);
S:=0;
for i:=0 to n do
begin
read(a);
S:=S*x+a;
end;

n+1 операций "+" и n+1 операций "* "

Примеры на суммирование рядов

Если x_i = f(x_i-1), то

x:=x0;
S:=x;
for i:=2 to n do
begin
x:=f(x);
S:=S+x
end;

Пример 15. Вычислить сумму

x:=1;
S:=x;
for i:=2 to n do
begin
x:=x*y/i;
S:=S+x;
end;

Если существует предел суммы

Пример 16. Знакопеременный ряд

x_i = x_i-1 + 0.1
z_i=(-1)ⁱ
z_i=-z_i-1

z:=1;
s:=0;
x:=1; // эта часть может меняться
for i:=0 to n do
begin
s:=s+z*x;
x:=x+0.1; // эта часть может меняться
z:=-z;
end;

Пример 17. Вычислить сумму

x_i=x_i-1*y*(i-1)/i - неэффективно.

Лучше p_i=yⁱ, p_i=p_i-1*y

Код программы.

for i:=0 to n do
begin
p:=p*y;
s:=s+p/i;
end;

Пример 18. Метод половинного деления

Задача. Дана непрерывная на [a,b] функция f(x),имеющая на [a,b] ровно один корень (т.е. f(a)*f(b)<=0). Найти его с точностью eps.

Алгоритм.

fa:=f(a);
fb:=f(b);
while b-a>eps do
begin x:=(b+a)/2;
fx:=f(x);
if fa*fx<=0 then // корень расположен на (a,x]
begin
b:=x;
fb:=fx
end
else
begin
a:=x;
fa:=fx
end;
end;
writeln('корень=', (b+a)/2);

Процедуры break и continue

Задача. Есть ли среди введенных 10 чисел число К?

Решение. Способ 1.

flag:=false;
for i:=1 to 10 do
begin
read(x);
if x=k then
flag:=True
end;
write(flag);

Недостаток: после того как flag получит значение True, он уже не поменяется, поэтому дальнейшее выполнение цикла бесполезно.

Для решения подобных проблем используются специальные процедуры, меняющие порядок выполнения операторов: break и continue.

Вызов процедуры break завершает цикл досрочно.

Вызов процедуры continue досрочно завершает текущую итерацию цикла.

Процедуры break и continue могут вызываться только в цикле.

Мнение автора. Позволю себе заметить, что решение назвать break и continue процедурами мне не нравится. В C, Java это - операторы, как и goto. И правильно: обычная процедура не может менять порядок выполнения операторов: это удел синтаксических конструкций (операторов).

Решение. Способ 2.

flag:=false;
for i:=1 to 10 do
begin
read(x);
if x=k then
begin
flag:=True;
break;
end;
end;
write(flag);

Приведем другие примеры использования процедур break и continue.

Пример 1. Является ли число N простым?

IsSimple:=True;
for i:=2 to round(sqrt(N)) do
if N mod i=0 then
begin
IsSimple:=false;
break;
end;

Пример 2. Вводятся ненулевые числа, конец ввода - 0. Найти сумму и произведение положительных.

S:=0;
P:=1;
repeat
read(x);
if x=0 then break;
if x<0 then continue;
S:=S+x;
P:=P*x;
until False;

Всегда можно обойтись без break или continue, введя дополнительные логические переменные.

while B do
begin
S1
if B1 then break
S2
end;

Так выглядит программа без break:

B1:=false;
while B and not B1 do
begin
S1;
if not B1 then
S2
end;

Вложенные циклы

Цикл, вызываемый в другом цикле, называется вложенным.

Задача. Вывести таблицу значений А^k, где А=2..10.

Метод окаймления

"Заморозим" А и составим алгоритм при фиксированном А.

for A:=2 to 10 do
begin
p:=1;
for i:=1 to k do
p:=p*A;
writeln(p);
end.

Разморозим А и окаймим данный участок цикла по А от 2 до 10.

Задача. Вывести все простые числа от 100 до 999.