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

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

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

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

… Const MaxT = 51; {максимальное количество стержней, которое будет рассмотрено} var hn : array[4..maxT,0..maxD] of word; {в этом массиве хранится количество перестановок необходимое для переноса на M стержнях N дисков; веря подсчетам монахов, полагаем что это количество будет небольшим и потребует для хранения всего лишь тип word} hr : array[3..maxT,0..maxD] of byte; {в этом массиве хранится разбитие на группы, т.е. сколько дисков из N нужно переносить на M стержнях; остальные нужно переносить на M-1 стержнях} … Procedure CalcHR3; {записывает разбиение для трех стержней} Begin for i:=1 to n do hr[3,i]:=i-1; {на трех стержнях нужно переносит N-1 дмсков} End; … Procedure Calc4; {процедура считает наименьшее количество необходимых перестановок для переноса на четырех стержнях дисков в количестве от 1 до N, а также находит разбиения} Begin for i:=1 to n do begin hr[4,i]:=i-1; {полагает разбиение равным i-1 к 1} hn[4,i]:=2*hn[4,i-1]+1; {количество перестановок, которое при этом требуется} for j:=i-2 downto 1 do {здесь рассматриваются другие возможные разбиения j к i-j} if hn[4,i]>2*hn[4,j]+h3[i-j] then {выбираются разбиения, требующие наименьшего количества перестановок} begin hr[4,i]:=j; hn[4,i]:=round(2*hn[4,j]+h3[i-j]); end; end; End; …

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

… var j,k : integer; … Procedure CalcM; {считает количество необходимых перестановок и разбиений для от 5 до M стержней и от 1 до N дисков} Begin {алгоритм тот же, что и в Calc4, только более общий} Calc4; for i:=5 to m do for j:=1 to n do begin hr[i,j]:=j-1; hn[i,j]:=2*hn[i,j-1]+1; for k:=j-2 downto 1 do if hn[i,j]>2*hn[i,k]+hn[i-1,j-k] then begin hr[i,j]:=k; hn[i,j]:=2*hn[i,k]+hn[i-1,j-k]; end; end; End; …

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

Program Hanoi_forNdisks_andMshanks; Var n,m : byte; T : array[1..50] of byte; {здесь хранятся номера используемых стержней; так как их количество не фиксировано, то для хранения удобней использовать глобальный массив} … {Сюда вписываем все описанные ранее процедуры и связанные с ними переменные} … Procedure Swap(i,j : byte); {процедура, меняющая местами элементы массива T} Begin t[i]:=t[i]+t[j]; {пример обмена значений двух числовых переменных в обход третей} t[j]:=t[i]-t[j]; {для тех, кто этого фокуса не знает, должно быть интересно} t[i]:=t[i]-t[j]; End; Procedure Hanoi(n,m : byte); {модифицированная процедура из программы Hanoi3, n — количество дисков, которые надо перенести с первого на последний стержень, m — количество стержней} Begin if n=1 then write(t[1],' --> ',t[m],'; ') { тривиальный перенос одного диска} else begin Swap(m,m-1); {поменять стержни m и m-1 местами} Hanoi(hr[m,n],m); {перенести какое-то количество с помощью m стержней на m-1'ый стержень} Hanoi(n-hr[m+1,n],m-1); {перенести остальные диски с помощью m-1 стержня на m'ый стержень} Swap(m,m-1); {обратно поменять m и m-1 стержни местами} Swap(1,m-1); {сделать m-1'ый стержень стартовым} Hanoi(hr[m,n],m); {перенести оставшиеся диски с m-1'ого на m'ый стержень, используя m стержней} Swap(1,m-1); {восстановить порядок стержней} end; End; Begin {ввод m>=3 и n<=50} … fillchar(hn,sizeof(hn),0); fillchar(hr,sizeof(hr),0); Calc3; CalcHR3 if m>3 then CalcN; for i:=1 to m do t[i]:=i; {начальный порядок стержней} Hanoi(n,m); End.

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

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

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