АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2002 ГОД

Конструируем Ханойские башни

• Все журналы \ Номер 32/203 `2002 от 19.08.2002 \ Конструируем Ханойские башни

Владимир ТКАЧУК vova.tkachuk@fm.ua

Ох уж эти программисты, вечно чего-то наделают. Вот так один из них стал причиной отмены конца света. Как? Неужели правда? Ну, настолько же правда, насколько и все другие легенды, связанные с Ханойскими Башнями.

Итак, сначала все же про башни, а про программиста чуть позже. По официальной версии, Ханойские Башни —это головоломка, которую в 1883 г. придумал французский математик Эдуард Люка. Для тех, кто не знает, суть головоломки вот в чем: есть три стержня и восемь дисков разных диаметров, вначале все диски собраны на одном стержне так, что меньшие диски лежат на больших. Люка предлагал переложить все диски с первого стержня на третий, используя второй. При этом следует соблюдать следующее правило: диски можно перекладывать с одного стержня на другой, при этом нельзя класть диск поверх диска меньшего радиуса. По той же официальной версии, ради повышения интереса к своей головоломке Люка придумал легенду, повествующую про башню Брамы, увеличенную копию Ханойской. Эта башня состояла то ли из 50, то ли из 64 золотых дисков, а стержни были вырезаны из алмаза. Так вот, башни Брамы были созданы не иначе как при Сотворении мира, и с того времени жрецы в храме трудятся, перекладывая диски. По имеющимся данным, как только они закончат, наступит конец света, и потому жрецы очень стараются… —

Давайте быстренько сообразим, что и как нужно делать, чтобы поскорее покончить с этим миром — другими словами, как решить эту головоломку? Додуматься несложно: для того чтобы перенести самый большой диск, нужно сначала перенести все диски кроме последнего на второй стержень, потом перенести самый большой на третий, после чего останется перенести все остальные диски со второго на третий. Задачу о переносе N-1 диска мы решаем аналогично, только поменяем стержни местами (при первом переносе конечным стержнем будем считать второй, а не третий, при втором переносе начальным вместо первого будет второй). Как видите, задачка разрешима. И правда, ведь задачу о N-1 дисков мы сведем к задаче о N-2 дисков, ту в свою очередь к N-3 дискам, и так вплоть до 1 диска. Также ясно, что это единственно правильный подход, так что жрецы, скорее всего, действуют так же. Этот метод легко программируется с помощью рекурсии, код на языке Pascal выглядит так:

Программа проста, ее корректность очевидна. Но, возвращаясь к легенде, вспомним, ведь жрецы упражняются в переносе дисков с незапамятных времен — откуда ж им в те времена было знать про рекурсию? А им и не надо было знать, так как вышеописанный алгоритм имеет и рекуррентную интерпретацию. Если бы вам пришлось возится с этой головоломкой так долго, то вы бы наверняка заметили, что каждые два хода мы обязательно переносим самый маленький диск (это почти очевидно). Но кроме того, направление движения этого диска не меняется. Другими словами, диск циклически двигается либо по маршруту 1-2-3-1, либо по маршруту 1-3-2-1. Выбор маршрута, в чем тоже несложно убедиться, зависит от парности начального количества дисков. При желании это можно строго доказать, а я не сомневаюсь, что жрецы так и сделали: ведь не хочется все переделывать из-за оплошности, допущенной в начале. Итак, если решать головоломку, пользуясь этими свойствами, то и думать особо не придется: раз в два хода перекладываешь самый маленький диск, а остальные хода задаются однозначно, просто кладешь меньший диск на больший. Жрецы будут действовать так, пока все диски не соберутся на третьем стержне. Реализация также не сложна, разве что придется помнить, какие диски на каких стержнях лежат.

Обе программы перекладывают диски одинаковым образом — оно и неудивительно, ведь они действуют по оптимальному алгоритму. Удивительно другое: если головоломку решить так просто, то почему же конец мира до сих пор не настал? Хм, мы еще не исследовали сложность работы этих программ. Может быть, ответ кроется именно в этом? Так как обе программы действуют одинаково (делают одни и те же перестановки), то и сложность работы у них одна и та же. Конечно, удобней считать количество перестановок по рекурсивной программе, ведь в ней мы разбиваем задачу на подзадачи, а не просто «делаем, пока не сделалось». Опираясь на наши вступительные рассуждения, можем составить рекуррентное соотношение для количества перестановок 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. Зачем? Узнаете позже.

Посмотрим-ка, что наша программа вернет при N=50. Итак, h3[50]=1125899906842623!!! Это ж сколько бедным жрецам пахать! Наверно, им это число вряд ли понравилось бы. И поэтому я приступаю к главной части повествования — к той, что про программиста :-).

(Продолжение следует)

Идёт загрузка...

Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:
Комментарий:
Введите символы или вычислите пример: * Обновить