Организация циклических алгоритмов с неизвестным заранее числом повторений

Содержание |  Назад  |  Вперед

При решение различных вычислительных и прочих задач часто возникает необходимость организовать циклическое выполнение тех или иных операций, а количество повторений при этом оказывается неизвестно. Такие циклические процессы часто называют итерационными (от латинского iteratio - повторение). Большинство численных (приближенных) методов решения многих математических задач являются итерационными: вычисления проводятся до тех пор, пока не будет достигнута заданная точность, при этом заранее не известно сколько необходимо для этого совершить циклических операций. Аналогичная задача возникает при вычислении приближенных значений математических функций путем нахождения частичной суммы соответствующего ряда Тейлора. Здесь количество суммируемых членов ряда также заранее не известно, и определяется требуемой точностью вычислений. В программирования необходимость реализации таких алгоритмов возникает очень и очень часто. Ниже будут рассмотрены различные примеры.

ПРИМЕР 1.
Необходимо составить программу, вычисляющую приближенное значение функции exp(x) [ex] с заданной точностью e. Функция exp(x) может быть представлена бесконечным рядом

eq1-v1.gif (1336 bytes)

Для вычисления значения функции exp(x) с точность e необходимо просуммировать все члены ряда, которые по модулю превышают заданную точность, т.е. e. Следовательно, необходимо организовать циклический процесс для вычисления суммы и закончить его, когда выполнится условие

.

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

.

Это ровным счетом одно и тоже, различна только логика рассуждения. А различная логика может быть легко реализована различными логическими (условными) операторами, что и будет показано ниже.

При взгляде на приведенную выше формулу может возникнуть мысль о необходимости написания отдельной подпрограммы (процедуры или функции) для вычисления факториала. Даже возведение в степень может показаться проблематичным, учитывая отсутствие в Паскале соответствующей функции. Но поскольку "нормальные герои всегда идут в обход" стоит немного повнимательней приглядеться к этой формуле. В этом случае можно заметить (а можно, конечно, и не заметить), что соседние члены ряда (обозначим их как Cn и Cn+1) связаны между собой соотношением

,      где n = 0, 1, 2, ...,   причем C0 = 1.

Используя это соотношение можно последовательно вычислить все члены ряда. Заметьте, что при этом не возникает необходимости в выполнении в явном виде операций вычисления факториала и возведения в степень. И это здорово! Рассмотренное свойство степенных рядов позволяет организовывать чрезвычайно простые и очень эффективные (в смысле оптимизации скорости вычислений) алгоритмы вычисления их частичных сумм.

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

Ниже приведены две программы, реализующие вычисление приближенного значения функции exp(x) в соответствии с разной логикой (см.выше). В первом случае для организации цикла c пост-условием использован оператор REPEAT...UNTIL, а во-втором - оператор WHILE, реализующий циклический процесс с пред-условием. Для наглядности также приведены алгоритмы в виде блок-схем.

Обратите внимание, что в программах активно используется операция переприсваивания.

PROGRAM Exponenta_1;
USES CRT;
VAR
  x, S, Cn, eps : Real;
              n : Integer;
BEGIN
  ClrScr;
  Writeln('EXP(x) как ряд Тейлора.');
  Write('Введите значение х: ');
  Readln(x);
  Write('Введите точность вычислений: ');
  Readln(eps);
  S := 0;
  n := 0;
  Cn := 1;
  REPEAT
   S := S+Cn;
   n := n+1;
   Cn := Cn*x/n;
  UNTIL abs(Cn)<eps;
  Writeln('Значение функции: ', S);
  Writeln('Количество членов ряда: ', n);
  Readln
END.
wpe3.jpg (8882 bytes)

PROGRAM Exponenta_2;
USES CRT;
VAR
  x, S, Cn, eps : Real;
              n : Integer;
BEGIN
  ClrScr;
  Writeln('EXP(x) как ряд Тейлора.');
  Write('Введите значение х: ');
  Readln(x);
  Write('Введите точность вычислений: ');
  Readln(eps);
  S := 1;
  n := 1;
  Cn := x;
  WHILE abs(Cn)>eps DO begin
    S := S+Cn;
    n := n+1;
    Cn := Cn*x/n;
  end; {while}
  Writeln('Значение функции: ', S);
  Writeln('Количество членов ряда: ', n);
  Readln
END.
wpe2.jpg (9652 bytes)

ПРИМЕР 2.
При организации ввода данных с клавиатуры хорошая программа непременно должна обеспечивать контроль за введенной информацией и не допускать ввода некорректных данных. Пусть, например, необходимо запросить ввод числа X в диапазоне от 0 до 100. Если пользователь ввел число, которое не принадлежит этому диапазону, программа должна сообщить об ошибке и повторно запросить ввод числа. И так до тех пор, пока пользователь не введет правильное число. Здесь на лицо циклический процесс с неизвестным заранее числом повторений, который завершается при выполнении определенного условия, а именно   . Для его реализации лучше всего подходит оператор REPEAT...UNTIL.

PROGRAM CheckInputData;
USES CRT;
VAR
  x : Real;
BEGIN
  ClrScr;

  REPEAT
    Write('Введите число в интервале от 0 до 100: ');
    Read(x);
    if not((x>=0)and(x<=100))
      then writeln('Ошибка при вводе числа!');
  UNTIL (x>=0)and(x<=100);
  ...
  ...
END.

ПРИМЕР 3.
Составим программу, реализующую следующую игровую ситуацию: компьютер "загадывает" случайное целое число в некотором интервале, скажем от 0 до 100, а игроку нужно его угадать. Число попыток не ограничено.

PROGRAM GuessNumber;
USES CRT;
CONST
   max = 100;
VAR
   xn,                {загаданное число}
   n,                 {введенное число}
   attempt : Integer; {кол-во попыток}
BEGIN
  ClrScr;

  Randomize;
  xn := Random(max);
  Writeln('Я загадал целое число от 0 до ',max,'. Угадай его!');
  attempt := 0;
  REPEAT
    Inc(attempt);

   
Write('Попытка ',attempt,' : ');
    Readln(n);   

    if (x<0)or(x>max) then begin
                             writeln('Будь внимательней, дружок!');
                             continue
                           end;
    if x<xn then writeln('Малова-то будет!');
    if x>xn then writeln('Перебор!');
  UNTIL n=xn;
  writeln('Молодец! Угадал(а)!');
  ReadLn
END
.

Компьютер "загадывает" число с помощью функции Random(m), которая возвращает случайное целое число в интервале от 0 до m. Это число помещается в переменную xn. Далее организуется цикл в котором: 1) кол-во совершенных попыток attempt увеличивается на единицу; 2) запрашивается ввод числа n; 3) проверяется, если введенное число оказывается меньше нуля или больше максимального значения max, выводится предупреждение "Будь внимательней, дружок!" и происходит переход к следующей итерации (continue) миную нижестоящие операторы; если введенное число меньше "загаданного" числа, то выводится сообщение "Малова-то будет", а если больше - "Перебор". Цикл завершается когда введенное и загаданное числа совпадут.

 

Содержание |  Назад  |  Вперед