Пример построения цикла

Рассмотрим функцию вычисления факториала:

int fact(int x)

{

if(x==0) return 1;

if(x==1) return 1;

int y=fact(x-1);

printf("x=%i, y=%i\n", x, y);

return x*y;

}

void main()

{

fact(5);

}

Эта функция рекурсивная, т. е. вызывает сама себя, она реализует факториал по его определению, т. е. факториал от 0 или 1 равен 1, а факториал от другого целого числа равен произведению этого числа на факториал от числа на единицу меньше. В рассматриваемой функции есть дополнительные строчки, которые печатают на каждом шаге само число, и факториал от числа на единицу меньше.

Большинство циклов можно записать в рекуррентной или итеративной формах. Рекуррентная форма использует рекурсивные функции, а итеративная находит нужное значение пошагово.

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

Рассмотрим работу этой функции для случая вычисления факториала 5:

x=2, y=1

x=3, y=2

x=4, y=6

x=5, y=24

Заметим, что на каждом шаге цикла выполняются определенные условия, их можно записать следующим образом: y = (x – 1)!. Условие, которое выполняется на каждом шаге цикла, называется инвариантом. Данное условие выполняется в самом начале работы функции: x = 2, y = 1. Это называется начальным условием цикла или предусловием, т. е. в начале цикла необходимо обеспечить выполнение этого условия и задать переменным нужные значения.

В последней строке напечатано: x = 5, y = 24. Для завершения работы нужно сделать еще один шаг, который в рекуррентной форме не показывается: x = 6, y = 120. Инвариант выполняется и в этом случае, в конце цикла он называется постусловием, т. е. условием, которое создастся после окончания цикла, или, другими словами, условием, которого имеют целью достигнуть с помощью цикла.

По постусловию можно определить условие окончания цикла. Это часть постусловия, которая позволяет определить, что цикл нужно закончить. В нашем случае условие окончания будет x = 6, или, в общем случае, x = n + 1, где n – число, для которого определяется факториал. Во многих языках программирования высокого уровня в формах записи цикла требуется указать не условие окончания, а условие продолжения цикла. В нашем случае цикл должен продолжаться до тех пор, пока x < 6 или x < n + 1.

Записав все условия (инвариант, предусловие, постусловие), можно сос-тавить тело цикла.

Очевидно, что для того чтобы приблизить условия окончания цикла, нужно увеличить x, например, на единицу. Обозначим x` = x + 1, где x` – значение переменной x на новом шаге. Нужно найти y` = (x` – 1)!. Мы не можем использовать функцию факториала, поскольку мы ее реализуем, но, используя определения факториала, и то, что y = (x – 1)!, получаем: y` = (x `– 1)! = (x + 1 – – 1)! = (x – 1)! x = y * x. Таким образом, можно получить значение y на новом шаге, умножив x на y из предыдущего шага. Получаем следующее тело цикла:

y=y*x;

x++;

Цикл разработан, осталось записать его на языке программирования. Запишем цикл с помощью изученного в первом семестре оператора for:

for(x=2, y=1; x<n+1; x++)

y=y*x;

В поле инициализации оператора мы записали инициализацию цикла – задание начальных значений переменных. Для того чтобы задать сразу два значения, был применен оператор «запятая», который указывает на то, что нужно выполнить последовательно два действия.

В операторе for во втором поле указывается условие выполнения цикла: цикл будет выполняться до тех пор, пока x < n, где n – число, факториал которого мы считаем.

Третье поле указывает шаг цикла, который выполняется после тела. Оператор x++ по смыслу соответствует шагу цикла, т. е. приближает условие окончания цикла, поэтому он был перенесен сюда из тела цикла.

Функция, вычисляющая факториал с помощью цикла, имеет вид:

int fact1(int n)

{

if(n==0) return 1;

if(n==1) return 1;

int x, y;

for(x=2, y=1; x<n+1;x++)

y=y*x;

return y;

}