Паскаль. Основы программирования


Рекурсия - часть 4


Если к некоторому озеру подлетит m белых гусей и Серый, то на этом озере садится
 - ровно половина всех гусей вместе с серым. Поэтому после каждого озера число летящих гусей уменьшается ровно вдвое. После семи озер оно уменьшится в 27 = 128 раз, а остается летящим один Серый гусь. Значит, вначале было 128 гусей, из них 127 - белых.

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

Обозначим через xk количество летящих белых гусей, когда впереди еще k озер. Тогда условие задачи записывается так:

Отсюда получаем для последовательности (xk) рекуррентное соотношение

Зная его, легко составить рекурсивную процедуру:

    Procedure goose(x, k : integer);

        begin

           if k = 1 then writeln(x) else

goose(2*x + 1, k - 1)

        end;

В процедуру вводятся всего две переменные: x - искомое число гусей; k - число озер. Процедура устроена с расчетом, что гуси уже пролетели все 7 озер, значит надо вводить значение для x - один (1), а для k - семь (7). В процедуре устроено, что число k уменьшается на 1 и тогда опорным условием ("якорем") завершения процедуры является условие равенства 1 значений k и после этого на экран надо выдать значение числа гусей:

if k = 1 then writeln(x)

 

Опорное условие может быть и другим, если первоначальным значением k будет 1, тогда при повторном обращении к процедуре значение k надо не уменьшать, а увеличивать на 1 (k + 1), опорным условием, в этом случае, будет k = 7.

Ниже приводится законченная программа решения этой задачи:

Program Problem11;

    uses WinCrt;

    var

        k : integer;

{----------------------------------------------------------------------------------------}

    Procedure goose(x, k : integer);

        begin

           if k = 1 then write(x) else

goose(2*x + 1, k - 1)

        end;

{----------------------------------------------------------------------------------------}

    begin

       write('Введите число озер '); readln(k);

       write('В стае было ');

       goose(1, k);

       writeln(' гусей')

    end.

Придерживаясь подобных соображений, решите следующую задачу.




Начало  Назад  Вперед



Книжный магазин