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

Алгоритм решения головоломки следующий:

1. Переместить верхние n-1 дисков на второй колышек.

2. Нижний диск с первого колышка переместить на третий.

3. Переместить n-1 дисков на третий колышек, используя первый в качестве вспомогательного.

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

Исходная задача сводится, таким образом, к двум задачам о переносе n-1 диска и одной задаче о переносе одного диска. Для n-1 требуется одно перемещение. Исходный текст программы для вычисления количества ходов приведён ниже (Листинг 1). Количество ходов здесь может быть вычислено как с применением рекурсии (функция hanoi1), так и без неё (функция hanoi2). В первом случае исходный текст функции короче.

1 2 3

Рис. 5. Головоломка “Ханойская башня”

Листинг 1. Программа “Ханойская башня”

{$S+}

program hanoi_moves;

function hanoi1(n: Word): LongInt;

begin

if n=1 then hanoi1:=1

else hanoi1:=2*hanoi1(n-1)+1;

end;

function hanoi2(n: Word): LongInt;

var j: LongInt; k: Word;

begin

if n=1 then hanoi2:=1

else

begin

j:=1;

for k:=2 to n do j:=2*j+1;

hanoi2:=j;

end;

end;

writeln(hanoi1(20));

writeln(hanoi2(20));

end.

1.5.2. Двумерное множество Кантора

Ещё один пример использования рекурсии приводится в программе Cantor (Листинг 2), которая строит двумерное множество Кантора. Множество строится следующим образом. Имеется квадрат, внутренняя часть которого закрашена каким-то цветом. Этот квадрат делится на 16 равных частей (тоже квадратных). Затем удаляются 4 средних квадрата, причём изображения их границ остаются. Далее процедура повторяется для каждого оставшегося квадрата. Алгоритм построения квадратного множества Кантора следующий:

1. Построить квадрат размером L.

2. Вырезать расположенный в центре квадрат размером L/2.

3. Разделить исходный квадрат на четыре равные части размером L/2.

4. Для каждого из четырёх квадратов повторить шаги 2 и 3.

В результате получается самоподобное множество – фрактал. В программе Cantor сохраняется изображение границы вырезанного квадрата, а построение множества идёт не от большего квадрата к меньшим, а наоборот.

Процедура SetWriteMode модуля Graph устанавливает режим вывода линии. Режим задаётся с помощью логической операции. В нашем примере используется операция “исключающее ИЛИ” (ей соответствует константа xorput), поэтому изображение линии комбинируется с изображением, уже выведенным на экран.

Листинг 2. Программа “Двумерное множество Кантора”

{$S+}

program Cantor;

uses Crt, Graph, graphs;

var ch: Char;

const min_size=1;

procedure draw(x,y: integer; size: Word);

var s: Word;

begin

if size>min_size then

begin

s:=size div 2;

draw(x-size, y+size, s);

draw(x-size, y-size, s);

draw(x+size, y+size, s);

draw(x+size, y-size, s);

end;

rectangle(x-size, y-size, x+size, y+size,);

bar(x-size+1, y-size+1, x+size-1, y+size-1);

end;

begin

open_graph;

SetFillStyle(solidfill, black);

SetColor(White);

draw(GetMaxX div 2, GetMaxY div 2, GetMaxY div 4);

OutTextXY(265, 235, ‘Press <Space>’);

ch:=ReadKey;

SetColor(Black);

SetWriteMode(xorput);

draw(getmaxx div 2, getmaxy div 2, getmaxy div 4);

SetColor(White);

OutTextXY(265, 235, ‘Press <Space>’);

ch:=ReadKey;

close_graph;

end.

1.5.3. “Индийский алгоритм” возведения в степень

Этот алгоритм вычисления натуральной n-й (n>1) степени целого числа х выглядит совсем просто:

§ при n=1 xn=x;

§ при n>1 xn= xn mod2(xn div2)2.

Основная цель этого алгоритма – сократить количество умножений при возведении в степень. Например, по этому алгоритму х5=х*(х2)2, т.е. достаточно трёх умножений вместо четырёх: х*х*х*х*х. Одно умножение экономится за счёт того, что х2 хранится как промежуточное значение и умножается само на себя. Точно так же х10=1*(х5)2=(х5)2, что требует лишь четырёх умножений (три из них для вычисления х5) вместо девяти “лобовых”. Но здесь придётся хранить сначала х2, а потом х5.

Очевидно, что вычисление хn сводится к вычислению хn div2, запоминанию результата, возведению в квадрат и умножению его на х при нечётном n. Итак, вычисление xn описывается рекурсивной функцией:

function pow(x,n:integer):integer;

var t:integer;

begin

if odd(n) then t:=x else t:=1;

if n=1 then pow:=x else pow:=t*sqr(pow(x,n div 2))

end;

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

Теперь опишем зависимость глубины рекурсии вызовов функции от значения аргумента. В каждом следующем вложенном вызове значение аргумента n меньше предыдущего значения, по крайней мере, вдвое. Поскольку при n=1 происходит возвращение из вызова, то таких уменьшений значения аргумента n не может быть больше чем log2n. Следовательно, глубина рекурсии вызова с аргументом n не превышает log2n.