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

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

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

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

(Окончание, начало см. в МК № 32 (203))

Так вот, было это уже ближе к нашему времени — замученные постоянным перекладыванием золотых чурок жрецы обратили свои мудрые взоры на достижения прогресса. Первое, что им пришло на ум: а зачем, собственно, напрягаться и зарабатывать грыжи и растяжения, тягая диски? Дело в том, что в их религии ничего не говорилось про то, что диски должны перекладываться вручную. И они призвали в помощь (купили, благо золота много) робота-манипулятора. Их ждало разочарование: увеличение в скорости было незначительное, все-таки жрецы были натренированные (видать, больше ничего в жизни не делали), а работы предстояло все еще много. И тут кого-то осенило: в религии также ничего не говорилось про то, что стержней должно быть именно три, а значит, можно добавить еще хотя бы один стержень (алмазов, наверное, тоже хватало). По предварительным подсчетам жрецов, такая незначительная модификация позволила бы им не оставлять конец света на долю далеких потомков, а самим, лично, вкусить всю его прелесть. Обрадовавшись, жрецы с новыми силами приступили за работу. И… И все бы хорошо, но о том, как управляться с четырьмя стержнями, они не знали. Теперь алгоритмов, которые приводили к результату, было множество, самые очевидные нисколько не убыстряли работу, а в более сложных они путались. Решено было вернутся к роботу-манипулятору, но для него была нужна программа. Тогда жрецы, как всякие порядочные ламе… прошу прощения, неосведомленные пользователи, обратились — как бы вы думали, к кому? Правильно, к тому кто знает. К счастью для них, в пределах досягаемости оказался один программист. Удовлетворившись размером гонорара, выслушав постановку задачи и нисколько не смутившись целью проекта, он взялся за роботу. Первое время, как и положено, потратилось на проедание, пропивание и просиживание в Сети аванса, но когда сроки начали поджимать, пришлось листать номера журнала «Мой компьютер» в поисках раздела «Программирование» :-). Перед самой сдачей проекта программист задумался: ведь за какие-то несколько месяцев робот-манипулятор переложит все диски. Вряд ли за это время выловят все глюки из Винды, мир не увидит нового add-on'а Халфлайфа, и главное — он не успеет потратить свой гонорар. Руководствуясь этими, а также прочими благими побуждениями, программист заодно с программой заложил в робота взрывчатку, которая должна была сработать как раз тогда, когда последний диск будет опускаться на последний стержень, т. е. перед самым концом света. Избрав такой хитроумный план, он как бы и не обманывал клиента: заряд рванет только в случае, если вся программа отработает правильно. Результат не заставил себя ждать — через каких-то несколько месяцев храм был разрушен сильным взрывом. Программа отработала правильно, но и программисту пришлось нелегко. Другие мысли стали мучить его: а что если глюки из Windows нельзя полностью выловить? Если следующий add-on не выйдет? Что если мир обречен вечно решать свои проблемы, не имея шанса корректно завершить роботу? В общем, все эти раздумья привели к тому, что этот программист с тяжкой психической травмой был помещен в лечебницу, где и провел остаток своих дней.

После этого лирического отступления вернемся к главной нашей теме, а именно к программированию. Раз взрывчатка сработала, значит, задача была решена правильно. Возникает вопрос: как, как это было сделано? Не содрал же он и впрямь решение из журнала — значит, придумал сам. А раз кто-то уже раз смог, то и мы сможем, тем более что конец света этим уже не спровоцируем. Для того чтобы решить эту задачу, возвратимся немного назад. А именно к трем стержням, или даже к двум. Задумывались ли вы, что задачу можно решить и на двух стержнях, если нужно переложить всего один диск. Я это не просто так пишу, а к тому, что решение задачи Ханойских Башен можно интерпретировать и так: перенести какое-то количество дисков (N-1) с помощью трех стержней на вспомогательный стержень, оставшиеся диски (1) с помощью двух стержней перенести на конечный стержень, а затем с помощью трех стержней перенести диски с вспомогательного на конечный стержень. Теперь несложно провести аналогию для четырех стержней. Действовать можно так: перенести какое-то количество дисков с помощью четырех стержней на один из вспомогательных стержней, остальные диски с помощью трех стержней перенести на конечный стержень, потом перенести оставшиеся диски со вспомогательного на конечный стержень, используя опять-таки все четыре. Мы снова разбиваем задачу на подзадачи, используя также подзадачу с тремя стержнями, которая решена нами для любого количества дисков. Трудность состоит в том, что нам не известно, какое количество нужно переносить с помощью трех, а какое с помощью четырех стержней, чтобы потребовалось наименьшее количество переносов. В отличие от задачи о трех стержнях, где разбитие было однозначным —N-1 и 1, — для четырех мы можем разбивать по-разному. Например, если разбивать в отношении N-1 и 1, то потребуется точно то же количество перестановок, что и для трех стержней. На самом деле, нельзя так просто сказать, на какие группы нужно делить диски, но мы можем посчитать это с помощью следующей процедуры:

Итак, просто рассматриваем все возможные разбиения и выбираем из них наилучшие. Проверим, сколько перестановок нужно для 50 дисков на четырех стержнях, т.е. чему равно hn[4,50]. И вот какое число получилось —6657. Видно, жрецы были правы, возлагая надежды на четыре стержня: преимущество в скорости потрясающее. Пойдем же дальше и сформулируем задачу не только для 4, но и для M стержней. И правда, ведь для того чтобы перенести N дисков на M стержнях, требуется перенести K дисков с помощью M стержней, потом перенести N-K дисков с помощью M-1 стержней на окончательный стержень, после перенести K дисков на последний стержень. K для каждого конкретного случая можно определить разбиением, пользуясь следующей процедурой:

Теперь мы знаем, сколько перемещений нам придется сделать, чтобы переложить N дисков, используя M стержней. Так что дело осталось за малым, а именно: написать программу, которая будет производить все эти перекладывания (не самим же руки марать, в конце концов).

Нельзя сказать, чтобы это было совсем уж просто, но таки справились. Кстати, если бы жрецы не поскупились алмазами и установили 51 стержень, то им пришлось бы тягать диски всего 99 раз, да и думать надо было бы меньше. Напоследок хочу предупредить вас: не подкидывайте «троянских коней» своим коллегам и другим честным пользователям и никогда не обманывайте заказчиков — это может сказаться как на вашей репутации, так и на жизни в целом. Вы же не хотите закончить, как тот программист?

P.S. Все программы проверены на работоспособность, стоит лишь дописать в них ввод, и собрать последнюю программу воедино.

P.P.S. Легенда про программиста была мною несколько переделана; имени его я не называю.

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

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

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