CFA LogoCFA Logo Computer
Загрузка поиска
Новости Компьютеры Прайс-лист [Новое] Прайс-лист [Б/У] Для ноутбуков Конфигуратор ПК Заказ, Оплата, Доставка Сервис объявления Драйвера Статьи Как нас найти Контакты
Новости
RSS канал новостей
То, что энтузиасты ждали так долго, наконец-то случилось, и компания NVIDIA анонсировала свой новый ...
Официальный анонс графического ускорителя GeForce GTX 1080 Ti состоялся 1 марта, и партнеры NVIDIA ...
Компания ASRock представила мировой общественности материнскую плату H110-STX MXM, которая рассчитана ...
Компания MSI в рамках серии Arsenal Gaming представляет пользователям материнские платы линейки ...
По данным наших коллег, в этом месяце компания Huawei официально представит свой новый смартфон. ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 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. Легенда про программиста была мною несколько переделана; имени его я не называю.

Рекомендуем ещё прочитать:






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

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы: *
captcha
Обновить






Рейтинг@Mail.ru
Хостинг на серверах в Украине, США и Германии. © www.sector.biz.ua 2006-2015 design by Vadim Popov