Основы программирования — Осенний семестр; Михалкович С.С.; 2008; III — различия между версиями

Версия 12:58, 4 июня 2009

Циклы

Циклы с предусловием (while) и постусловием (repeat)

<xh4> Синтаксис цикла while </xh4>

while <условие> do   <— заголовок цикла
  <оператор>   <— тело цикла

<условие>::= <логическое выражение>

<xh4> Семантика цикла while </xh4>

<xh4> Синтаксис цикла repeat </xh4>

repeat
  <операторы>
until <условие>

<xh4> Семантика цикла repeat </xh4>

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

Зацикливание происходит, если:

• условие цикла с предусловием всегда истинно

Пример.

while true do
  <оператор>

• условие цикла с постусловием всегда ложно

Пример.

repeat
  <операторы>
until false

Итерация — однократное повторение тела цикла.

<xh4> Отличия между циклами while и repeat </xh4> while

тело может не выполниться ни разу

repeat

тело выполнится хотя бы один раз

<xh4> Примеры </xh4> Пример 1. Сумма нечетных двузначных чисел

С использованием while

s := 0; 
x := 11;
while x < 100 do
begin
  s += x;
  x += 2;
end;

С использованием repeat

s := 0; x := 11;
repeat
  s += x;
  x += 2;
until x = 99;

Пример 2. Факториал

С использованием repeat

var n: integer;
read(n);
var x := n;
var p := 1;

repeat
  p *= x;
  x -= 1;
until x = 1;

С использованием while

var n: integer;
read(n);
var x := n;
var p := 1;

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

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

repeat             Op
  Op       ——>     while not A do
until A;           begin
                     Op
                   end;

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

while A do         if A then
  Op         ——>     repeat
                       Op
                     until not A

Оператор цикла с параметром (for)

<xh4> Синтаксис </xh4>

<заголовок цикла>
  <тело цикла>

<заголовок цикла> ::= for <переменная>:=<выражение1> <направление> <выражение2> do
<тело цикла> ::= <оператор> 
<направление> ::= to | downto

<xh4> Семантика </xh4>

var b := <выражение1>;
var e := <выражение2>;
  <переменная> := b;
 
while <переменная> <> e do
begin
  <оператор>
  <получить следующее значение переменной>
  <переменная> += 1; | <переменная> -= 1;
end;

<получить следующее значение переменной> ::= <переменная> += 1; | <переменная> -= 1;

<xh4> Ограничения: </xh4>

• выражения 1 и 2 должны быть совместимы по присваиванию с переменной
• переменная должна иметь порядковый тип (такой же, как и в case — целый, символьный или перечислимый)
• переменная цикла for не должна меняться внутри цикла for
• переменная цикла for должна быть описана в той же п/п, где используется цикл

Дополнительные возможности PascalABC.NET

Возможно описание переменной цикла в его заголовке:

for [var] i: integer := 1 to 5 do
  <оператор>

Возможно автоопределение типа при описании:

for var i := 1 to 5 do
  <оператор>

Переменная цикла, описанная в заголовке цикла, определена только внутри цикла.
Замечание. Значение переменной цикла после завершения цикла не определено. Именно поэтому рекомендуется описывать переменную цикла в заголовке цикла.

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

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

</xh4>Дана 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;

Дальнейшее решение с помощью 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;

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

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

<xh4> Рекуррентные соотношения </xh4> Говорят, что последовательность данных

x1, x2, x3,..., xn

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

xk + 1 = f( xk ), k = 1, 2, 3...

<xh4> Вывод степеней двойки </xh4>

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

<xh4> Последовательность Фибоначчи </xh4> <math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math>

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;

<xh4> Вычисление НОД (алгоритм Евклида) </xh4> <math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod x_k\end{cases}</math>

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);

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

• <math>\sum_{i=1}^n \frac{a^i}{i!}</math>

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

x1 = a
xi = xi-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;

• <math>\sum_{i=1}^\infty (-1)^i\frac{a^i}{i}</math>

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

задается некоторый малый eps и сумма <math>\sum_{i=1}^\infty x_i</math> вычисляется, пока <math>|x_i| >\ eps</math>

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;

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

max := - real.MaxValue; // или max := real.MinValue;
for var i := 1 to n do
begin
  read(x);
  if x > max then
    max := x;
end;

<xh4> Разложение целого числа на простые множители </xh4> Будем делить 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 — оператор досрочного завершения текущей итерации цикла.

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

<xh4> Поиск заданного значения среди введенных </xh4> Решение 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;

<xh4> Обработка последовательности, завершающейся нулем </xh4> Вводятся числа. Конец ввода — ноль.
Найти сумму и произведение положительных чисел.

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;

<xh4> Вычисление значения многочлена. Схема Горнера </xh4> Необходимо вычислить <math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math> если

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) умножений.

Однако есть и другое решение — схема Горнера. Оно основана на том, что
<math>\ a_0x^2 + a_1x + a_2 = ((a_0)x + a_1)x + a_2</math>

Решение 2.

read(a);
var res: real := a;
for var i:=1 to n do
begin
  read(a);
  res *= x;
  res += a;
end;

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

<xh4> Поиск нуля функции на отрезке </xh4> Требуется найти корень уравнения f( x ) = 0

• на отрезке [a; b]
• с заданной точностью eps
• f(x) непрерывна на этом отрезке
• имеет на нем ровно 1 корень, т.е. f(a ) * f( b ) < 0

Эта задача решается методом половинного деления.

assert(b > a);
var fa := f(a);
var fb := f(b);
assert(fa * fb < 0);

while b - a > eps do
begib
  var x := (b + a) / 2;
  var fx := f(x);
  if fx * fa > 0 then
  begin
    a := x;
    fa := fx;
  end
  else
    b := x;
end;

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

Метод последовательной детализации

Задача. Вывести все простые числа <= n

writeln(2);
x := 3;
while x <= n do
begin
  Если число x — простое, то
    writeln(x);
  x += 2;
end;

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

Задача. Вывести A^k, A = 2..10

Метод окаймления заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "размораживая" некоторый параметр.

Итак, пусть A — фиксировано( "заморожено" ).

var p := 1.0;
for var i:=1 to k do
  p *= A;
write(p);

Теперь размораживаем A:

for A:=2 to 10 do
begin
  ...
end;

Переборные задачи

Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.

Задача. Дано равенство: a² + b² = c², a,b,c — целые
Вывести все такие тройки (a, b, c), что: a<=100, b<=1000, c<=1000;

Решение.

for var a:=1 to 1000 do
for var b:=1 to 1000 do
for var c:=1 to 1000 do
  if a*a + b*b = c*c then
    writeln(a, b, c);

Однако, ясно, что

a2 + b2 = c2 <=> b2 + a2 = c2

Кроме того, c можно вычислять.

Оптимизация.

for var a:=1 to 1000 do
  for var b:=1 to a-1 do
  begin
    var c := round(sqrt(a*a + b*b));
    if a*a + b*b = c*c then
    begin
      writeln(a, b, c);
      writeln(b, a, c);
    end;
  end;

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