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

Табулирование функции

Дана f(x) на [a; b], разбитая на N частей.

Выдать таблицу значений в точках разбиения.

var a, b: real;

var N: integer;

read(a, b, N);

 

assert(N <> 0);

assert(b > a);

var h := (b - a) / N;

var x:real:=h;

Дальнейшее решение с помощью for:

for var i := 0 to N do

begin

writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));

x += h;

end;

Дальнейшее решение с помощью while:

var eps := h / 2;

while x < (b + eps) do

begin

writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));

x += h;

end;

Замечание. Вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при представлении вещественного числа в памяти, называется ошибкой округления.

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

Вывод. Вещественные числа нельзя сравнивать на равенство, можно только на больше/меньше.

Рекуррентные соотношения

Говорят, что последовательность данных

x₁, x₂, x₃,..., x_n

является рекуррентной, если

x_{k + 1} = f( x_k ), k = 1, 2, 3...

Вывод степеней двойки

var x := 1;

for var i := 1 to 10 do

begin

writeln(x);

x *= 2;

end;

Последовательность Фибоначчи

var a := 1;

var b := 1;

write(a, ' ', b, ' ');

for var i := 3 to 20 do

begin

c := a + b;

write(c, ' ');

a := b;

b := c;

end;

Вычисление НОД (алгоритм Евклида)

var a, b: integer;

read(a, b);

assert((a > 0) and (b > 0));

repeat

c := a mod b;

a := b;

b := c;

until c = 0;

writeln(a);

Суммирование рядов (конечных и бесконечных)

• 

Найдем рекуррентную связь между a_i:

x₁ = a

x_i = x_i-1 * a / i, i = 2, 3..

read(a, n);

x := a;

s := x;

for var i := 2 to n do

begin

x *= a / i;

s += x;

end;

• 

Для вычисления суммы бесконечного ряда в простейшем случае используют следующий метод:

задается некоторый малый eps и сумма вычисляется, пока

assert((a > 0) and (a < 1));

i := 1;

s := 0;

y := -a;

repeat

s += y / i;

i += 1;

y *= -a;

until abs(y / i) < eps;

Нахождение max в последовательности чисел

max := - real.MaxValue; // или max := real.MinValue;

for var i := 1 to n do

begin

read(x);

if x > max then

max := x;

end;

Разложение целого числа на простые множители

Будем делить x на p, начиная с p = 2. Если делится нацело, то p — множитель, если не делится, то увеличиваем p на 1, пока x <> 1.

read(x);

p := 2;

repeat

if x mod p = 0 then

begin

write(p, ' ');

x := x div p;

end

else

p += 1;

until x = 1;

Операторы break и continue

break — оператор досрочного завершения цикла.

continue — оператор досрочного завершения текущей итерации цикла.

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

Поиск заданного значения среди введенных

Решение 1. С использованием оператора break

var exists: boolean := false;

for var i:=1 to n do

begin

read(x);

if x = k then

begin

exists := true;

break;

end;

end;

Решение 2.

var i := 1;

var exists: boolean:= false;

repeat

read(x);

if x = k then

exists := true;

i += 1;

until (i > n) or exists;

Обработка последовательности, завершающейся нулем

Вводятся числа. Конец ввода — ноль. Найти сумму и произведение положительных чисел.

s := 0;

p := 1;

while True do

begin

read(x);

if x = 0 then

break;

if x < 0 then

continue; //фильтр

s += x;

p *= x;

end;

Вычисление значения многочлена. Схема Горнера

Необходимо вычислить если

a₀...a_n известны

x дано

Решение 1.

var p := 1.0;

var s := 0.0;

for var i := 0 to n do

begin

read(a);

s += p * a;

p *= x;

end;

Это решение использует 2(n + 1) умножений.

Однако есть и другое решение — схема Горнера. Оно основана на том, что

Решение 2.

read(a);

var res: real := a;

for var i:=1 to n do

begin

read(a);

res *= x;

res += a;

end;

Итого — всего n умножений.