[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Алгоритмы /

Ханойская башня - 2

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




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Алгоритмы /

Основные понятия теории алгоритмов - часть первая
09-04-2009   

Алгоритмом часто называют конечную совокупность инструкций для решения некоторого класса задач. Это определение неформально, так как с его помощью нельзя однозначно ответить на вопросы, что такое совокупность инструкций и некоторый класс задач... подробнее

Кол. просмотров: общее - 2962 сегодня - 0

Основные понятия теории алгоритмов - часть вторая
09-04-2009   

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

Кол. просмотров: общее - 2984 сегодня - 0

Основные понятия теории алгоритмов - часть третья
09-04-2009   

К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В... подробнее

Кол. просмотров: общее - 3057 сегодня - 0

Основные понятия теории алгоритмов - часть четвертая
09-04-2009   

Понятие алфавитного оператора является чрезвычайно общим. К нему фактически сводятся или могут быть сведены любые процессы преобразования информации, поскольку символам алфавита можно поставить в соответствие объекты произвольной природы... подробнее

Кол. просмотров: общее - 2749 сегодня - 1

Оценка сложности алгоритмов
09-04-2009   

С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов... подробнее

Кол. просмотров: общее - 2935 сегодня - 2



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects