Ох уж эти программисты, вечно чего-то наделают. Вот так один из них стал причиной отмены конца света. Как? Неужели правда? Ну, настолько же правда, насколько и все другие легенды, связанные с Ханойскими Башнями.
Итак, сначала все же про башни, а про программиста чуть позже. По официальной версии, _Ханойские Башни —_это головоломка, которую в 1883 г. придумал французский математик Эдуард Люка. Для тех, кто не знает, суть головоломки вот в чем: есть три стержня и восемь дисков разных диаметров, вначале все диски собраны на одном стержне так, что меньшие диски лежат на больших. Люка предлагал переложить все диски с первого стержня на третий, используя второй. При этом следует соблюдать следующее правило: диски можно перекладывать с одного стержня на другой, при этом нельзя класть диск поверх диска меньшего радиуса. По той же официальной версии, ради повышения интереса к своей головоломке Люка придумал легенду, повествующую про башню Брамы, увеличенную копию Ханойской. Эта башня состояла то ли из 50, то ли из 64 золотых дисков, а стержни были вырезаны из алмаза. Так вот, башни Брамы были созданы не иначе как при Сотворении мира, и с того времени жрецы в храме трудятся, перекладывая диски. По имеющимся данным, как только они закончат, наступит конец света, и потому жрецы очень стараются… —
Давайте быстренько сообразим, что и как нужно делать, чтобы поскорее покончить с этим миром — другими словами, как решить эту головоломку? Додуматься несложно: для того чтобы перенести самый большой диск, нужно сначала перенести все диски кроме последнего на второй стержень, потом перенести самый большой на третий, после чего останется перенести все остальные диски со второго на третий. Задачу о переносе N-1 диска мы решаем аналогично, только поменяем стержни местами (при первом переносе конечным стержнем будем считать второй, а не третий, при втором переносе начальным вместо первого будет второй). Как видите, задачка разрешима. И правда, ведь задачу о N-1 дисков мы сведем к задаче о N-2 дисков, ту в свою очередь к N-3 дискам, и так вплоть до 1 диска. Также ясно, что это единственно правильный подход, так что жрецы, скорее всего, действуют так же. Этот метод легко программируется с помощью рекурсии, код на языке Pascal выглядит так:
Program Hanoi3; {3 — потому что для трех стержней} Var N : byte; Procedure Hanoi(first,second,third,N : byte); {first, second, third — номера начального, промежуточного и конечного стержней, N — количество дисков, которые надо перенести} Begin If N=1 then writeln(first,' --> ',third,'; ') {тривиальный перенос одного диска — вместо вывода на экран можно вызвать процедуру, отображающую перенос графически} else begin Hanoi(first,third,second,N-1); {перенос N-1 дисков на промежуточный стержень} Hanoi(first,second,third,1); {перенос 1 диска на конечный стержень} Hanoi(second,first,third,N-1); {перенос N-1 дисков с промежуточного на конечный стержень} end; End; Begin {ввод N — количество дисков} ... if N>0 then Hanoi(1,2,3,N); {переносим N дисков с стержня №1 на стержень №3} End.
Программа проста, ее корректность очевидна. Но, возвращаясь к легенде, вспомним, ведь жрецы упражняются в переносе дисков с незапамятных времен — откуда ж им в те времена было знать про рекурсию? А им и не надо было знать, так как вышеописанный алгоритм имеет и рекуррентную интерпретацию. Если бы вам пришлось возится с этой головоломкой так долго, то вы бы наверняка заметили, что каждые два хода мы обязательно переносим самый маленький диск (это почти очевидно). Но кроме того, направление движения этого диска не меняется. Другими словами, диск циклически двигается либо по маршруту 1-2-3-1, либо по маршруту 1-3-2-1. Выбор маршрута, в чем тоже несложно убедиться, зависит от парности начального количества дисков. При желании это можно строго доказать, а я не сомневаюсь, что жрецы так и сделали: ведь не хочется все переделывать из-за оплошности, допущенной в начале. Итак, если решать головоломку, пользуясь этими свойствами, то и думать особо не придется: раз в два хода перекладываешь самый маленький диск, а остальные хода задаются однозначно, просто кладешь меньший диск на больший. Жрецы будут действовать так, пока все диски не соберутся на третьем стержне. Реализация также не сложна, разве что придется помнить, какие диски на каких стержнях лежат.
Program Hanoi3_NoRecursion; Var d : array[1..3,1..64] of byte; {список дисков на каждом стержне} l : array[1..3] of byte; {количество дисков на каждом стержне} N,i : byte; {N — общее количество дисков} old,new : shortint; {старое и новое положение наименьшего диска} delta : shortint; {смещение, определяющее маршрут наименьшего диска} Procedure Transfer(i1,i2 : byte); {процедура переноса диска со стержня i1 на стержень i2} Begin l[i2]:=l[i2]+1; d[i2,l[i2]]:=d[i1,l[i1]]; write(i1,' -->(',d[i1,l[i1]],') ',i2,'; '); l[i1]:=l[i1]-1; End; Begin {Ввод N — количество дисков} … l[1]:=N; {сначала все диски на первом стержне, на остальных стержнях дисков нет} l[2]:=0; l[3]:=0; for i:=1 to N do d[1,i]:=N+1-i; {запись номеров дисков, которые лежат на первом стержне, диск №1 — наименьший} new:=1; {наименьший диск лежит на первом стержне} if odd(N) then {в зависимости от парности N, смещение — или 1 или -1} delta:=-1 else delta:=1; while l[3]0) and ((l[i]=0) or (d[old,l[old]]0 then Transfer(i,old); end; End.
Обе программы перекладывают диски одинаковым образом — оно и неудивительно, ведь они действуют по оптимальному алгоритму. Удивительно другое: если головоломку решить так просто, то почему же конец мира до сих пор не настал? Хм, мы еще не исследовали сложность работы этих программ. Может быть, ответ кроется именно в этом? Так как обе программы действуют одинаково (делают одни и те же перестановки), то и сложность работы у них одна и та же. Конечно, удобней считать количество перестановок по рекурсивной программе, ведь в ней мы разбиваем задачу на подзадачи, а не просто «делаем, пока не сделалось». Опираясь на наши вступительные рассуждения, можем составить рекуррентное соотношение для количества перестановок N дисков: T(n)=2T(n-1)+1. Ну да, два раза перекладываем по N-1 диска плюс еще один диск. Теперь нам известно, что T(0)=0, T(1)=1, T(2)=3, T(3)=7 (просто запустил прогу и посчитал). Так сделаем же предположение: T(n)=2n-1. Это совсем не сложно доказать, пользуясь составленным соотношением: T(n+1)=2(2n-1)+1=2n+1-1. А сейчас, после всей этой ужасной математики, напишем процедуру, которая считает количество необходимых перестановок для количества дисков от 1 до N. Зачем? Узнаете позже.
… Const MaxD = 50; {максимальное количество дисков} … h3 : array[0..MaxD] of comp; {так как перестановок может быть очень много, то нам нужен соответствующий тип данных} i,n : integer; … procedure Calc3; begin h3[0]:=0; {0 дисков требуют 0 перестановок} for i:=1 to n do h3[i]:=2*(h3[i-1]+1)-1; {уже известное рекуррентное соотношение} end;
Посмотрим-ка, что наша программа вернет при N=50. Итак, h3[50]=1125899906842623!!! Это ж сколько бедным жрецам пахать! Наверно, им это число вряд ли понравилось бы. И поэтому я приступаю к главной части повествования — к той, что про программиста :-).
(Продолжение следует)