Задача о ханойских башнях, как задача о комбинаторном объекте

Задача о Ханойских башнях общеизвестна и используется обычно при изучении рекурсии. Напомним формулировку задачи:
Дано три стержня. На первом стержне размещены n дисков разных диаметров, в порядке их увеличения. Сверху находится диск с наименьшим диаметром. Требуется переложить диски на третий стержень за наименьшее число перекладываний, соблюдая следующие правила:
• можно перемещать лишь по одному диску;
• больший диск не разрешается класть на меньший;
• откладывать диски в сторону не разрешается.
Рекурсивность решения очевидна. Пусть мы умеем переносить n-1 диск. В этом случае n дисков переносится так:
• верхние n-1 дисков переносятся с первого стержня на второй, используя свободный третий;
• последний n-й диск переносится с первого стержня на третий;
• n-1 дисков переносится со второго стержня на третий, используя первый в качестве свободного.
Простое рекурсивное решение данной задачи, определяющее порядок перекладывания дисков имеет вид:
Procedure Move1(n,s,t: Integer);
Begin
If n>1 Then Move(n-1,s,6-s-t);
WriteLn(s,t);
If n>1 Then Move(n-1,6-s-t,t);
End;
В реализации значением s является номер стержня, с которого осуществляется перекладывание, а значением t – номер стержня, на который осуществляется перекладывание. Номер промежуточного стержня, при их нумерации 1, 2, 3, вычисляется по формуле 6-s-t.
«Взглянем» на задачу несколько с другой позиции. Каждое расположение дисков на стержнях будем рассматривать как комбинаторный объект. В этом случае, согласно методике рассмотрения комбинаторных объектов [1], следует решить четыре задачи: подсчитать количество объектов, генерировать объекты в соответствии с введенным отношением порядка на всем множестве комбинаторных объектов; по объекту вычислять его номер и по номеру получать объект. Среди всех возможных размещений дисков на стержнях есть подмножество, определяемое задачей, то есть перемещением пирамиды с первого стержня на третий за наименьшее число перекладываний. Считаем, что размещение a дисков на стержнях, меньше размещения b, если b следует за a в процессе решения задачи (простое, может быть несколько искусственное отношение порядка).
Для решения первой задачи (подсчет количества перемещений дисков) достаточно выполнить простые вычисления. Обозначим число перемещений как f(n). Значение f(n) получается в результате переноса башни из (n-1)-го диска с первого стержня на второй, затем одно перемещение n-го диска с первого стержня на третий и переноса башни из (n-1)-го диска со второго стержня на третий. Следовательно, f(n)=2*f(n-1)+1. Введем функцию g(n)=f(n)+1. Получаем: g(n)=2*f(n-1)+2=2*g(n-1). Так как f(0)=0, g(0)=f(0)+1, f(1)=1, g(1)=f(1)+1=2, то g(n)=2n, а f(n)=2n-1.
Решение второй задачи, если рассматривать все подмножество перемещений дисков, а не получение следующего перемещения, из текущего, определяется процедурой Move1. Дадим ее нерекурсивную реализацию, но не путем механической замены рекурсии на стек, а несколько иначе. Цель – найти методы решения оставшихся задач.
Проведем небольшой эксперимент. Запустим программу, например, при n=4 и по результату её работы заполним таблицы (часть информации – в столбцах 1, 3, 5, а оставшаяся часть заполняется вручную).


(вставить таблицу)

Какие выводы можно сделать из этой информации?
1. Первый диск перекладывается g(n)/2 раз, второй – g(n)/4, и, наконец, n диск один раз.
2. Из двоичного представления номера перекладывания i определяется номер диска и то, какой раз он перекладывается. Приведем пример. Пусть n=7, двоичное представление какого-то перекладывания имеет вид 1011000. Значит, четвертый диск перекладывается шестой раз. Требуется «натолкнуть» ученика на мысль о том, что номер позиции первой единички слева дает номер диска (‘1000’ – четвертый диск), а оставшаяся часть ‘101’ определяет номер перекладывания этого диска (к пятерке прибавляем единицу).
3. Выписывание для каждого диска очередности номеров стержней (из последнего столбца таблицы), на которые он перемещается, позволяет установить следующую закономерность. Диски с той же четностью, что и диск с номером n перемещаются по стержням в порядке 1-3-2-1-3-2… (номера стержней), диски с другой четностью – 1-2-3-1-2-3… Получается, что зная номер диска, а следовательно и его четность, и номер его перемещения, можно вычислить и номер диска, с которого он перемещается и номер диска, на который он перемещается – операция нахождения остатка от деления на 3. В первом случае номер следующего стержня вычисляется с шагом два от номера текущего, во втором случае с шагом один, естественно, по модулю 3.
Примечание. Рекомендуется «вручную» заполнить таблицу при n=5.
Текст программной реализации.
Program Move2;
Var w,n,i,j,s,g:Integer;
Begin
ReadLn(n);
w:=(1 Shl n) - 1; {Вычисляем количество перемещений. После сдвига единицы на n разрядов влево мы должны остаться в диапазоне Integer.}
For i:=1 To w Do Begin {Цикл по перемещениям.}
s:=i;
j:=1; {Определяем номер перемещаемого диска.}
While s Mod 2 = 0 Do Begin
s:=s Div 2; {После выхода из цикла значение s, уменьшенное в два раза, определяет номер перемещаемого диска.}
Inc(j);
End;
If (n-j) Mod 2 =1 Then g:=1 Else g:=2; {Определяем четность диска.}
s:=(g*(s Div 2)) Mod 3; {Вычисляем номер стержня, с которого перемещается диск. Значение на единицу меньше – операция Mod.}
WriteLn(j,' - ',s+1,' - ',(s+g) Mod 3 +1);
End;
End.
Для решения задачи о генерации следующей раскладки по стержням из текущей требуется хранить раскладку в некоторой структуре данных. Пусть это будет массив a (a: Array[1..NMax] Of Integer;). Элемент a[i] определяет номер стержня, на котором находится диск i. Реализация процедуры Move1 с фиксацией раскладки в массиве a имеет вид.
Procedure Move1(n,s,t:Integer);
Begin
If n>1 Then Move1(n-1,s,6-s-t); {Перекладывание n-1 диска на промежуточный стержень.}
WriteLn(n,':',s,'->',t); {Вывод перекладывания.}
a[n]:=t; {Перемещение диска n на стержень t.}
<Вывод раскладки дисков.>;//
If n>1 Then Move(n-1,6-s-t,t); {Перекладывание n-1 диска на стержень t.}
End;
Предположим, что на трех стержнях дана некоторая раскладка дисков. Попробуем решить несколько другую задачу, а именно, определить является ли раскладка, зафиксированная в массиве a, промежуточной при перекладывании дисков со стержня s на t при оптимальном (наименьшем) перекладывании пирамиды.
Идея решения. В процессе перекладывания пирамиды из n дисков со стержня s на стержень t, необходимо достичь раскладки, в которой верхние n-1 диск находятся на промежуточном стержне q. После чего последний диск n перемещается на стержень t, и, затем пирамида из n-1 диска со стержня q перемещается на стержень t. Отсюда следует, что диск n может находиться либо на стержне s, либо на стержне t, но никак на стержне q. И далее:
• если диск n находится на стержне s, то осуществляется перемещение n-1 диска со стержня s на q, следовательно, диск n-1 может находиться либо на стержне s, либо на стержне q, но никак не на стержне t;
• если диск n находится на стержне t, то осуществляется перемещение n-1 диска со стержня q на конечный стержень t, следовательно, диск n-1 либо находится на стержне q, либо уже на стержне t, но никак не на стержне s;
• если диск n находится на стержне q, то данная раскладка дисков не может являться промежуточной при минимальном перекладывании дисков со стержня s на t.
Аналогичные рассуждения верны и для дисков с номерами n-1, n-2 и так далее. Оформим их в виде следующей рекурсивной функции.
Function Check(n, s, t: Longint):Boolean;
Begin
If n>0 Then {Еще не все диски просмотрены.}
If a[n] = s Then Check:=Check(n-1,s,6-s-t){Диск с номером n находится на стержне s. Выполняем проверку для диска n-1 при перекладывании со стержня s на стержень q=6-s-t.}
Else If a[n] = t Then Check:=Check(n-1,6-s-t,t) {Диск с номером n находится на стержне t. Выполняем проверку для диска n-1 при перекладывании со стержня q=6-s-t на стержень t.}
Else Check:=False {Диск с номером n оказался на стержне q.}
Else Check:=True; {Проверка прошла успешно для всех дисков.}
End;
Эта функция имеет недостаток, связанный с использованием оперативной памяти, выделяемой для стека адресов возврата (используется при реализации рекурсивной логики). Так, в данной ситуации при стандартных настройках в системе программирования Паскаль число n не должно превосходить примерно 900. Приведем нерекурсивный аналог данной функции.
Function Check(n, s, t: Longint):Boolean;
Var ch: Boolean;
Begin
ch:=True;
While (n>0) And ch Do Begin
If a[n] = s Then t:=6-s-t
Else If a[n] = t Then s:=6-s-t
Else ch:=False;
Dec(n);
End;
Check:=ch;
End;
Попробуем усложнить задачу, а именно, подсчитать количество перекладываний дисков, выполненных до получения данного размещения.
Function Check(n, s, t: Longint; Var cnt: Longint):Boolean;
Begin
If n>0 Then Begin
cnt:=cnt*2;{Диск с номером n перемещается в 2 раза чаще, чем диск с номером n+1 – вывод сделан по данным, приведенным в таблице.}
If a[n] = s Then Check:=Check(n-1,s,6-s-t)
Else If a[n] = t Then Begin
cnt:=cnt+1;{Диск с номером n был перемещен – плюс одно перемещение.}
Check:=Check(n-1,6-s-t,t)
End
Else Check:=False
End
Else Check:=True;
End;
При вызове функции Check возвращаемый параметр cnt должен быть равен 0. Если функция Check вернет значение True, то переменная cnt будет иметь требуемое значение. Как было получено значение cnt? При каждом входе в рекурсию значение переменной умножалось на два и, если имело место перекладывание диска, увеличивалось на единицу. Таким образом, каждому диску i, перемещенному со стержня s на t, в двоичной записи значения cnt в i-ом разряде соответствует 1, а не перемещенному диску – 0. Запись 1 осуществляется в соответствующей «копии» рекурсивно вызываемой функции Check.
Для решения третьей задачи – вычисления по размещению дисков на стержнях номера размещения, преобразуем функцию Check в требуемую функцию SetToNum.
Function SetToNum (n,s,t:Integer):LongInt;
Begin
If n>0 Then
If a[n] = s Then { Диск n не перемещался.}
SetToNum:= SetToNum(n-1,s,6-s-t) {Оставляем значение SetToNum без изменений.}
Else {Диск n переместился на стержень t.}
SetToNum:= 1 Shl (n-1) + SetToNum(n-1,6-s-t,t) {В значение SetToNum в бит n записываем 1.}
Else SetToNum:=0;
End;
Для формирования раскладки дисков по ее номеру (четвертая задача) требуется определить на каком стержне находится диск i (i = 1, …, n). Для этого необходимо проверить, присутствует ли 1 в бите i номера раскладки дисков. Если 1 присутствует, это означает, что диск переложен на стержень t, 0 – диск находится на стержне s. Естественно, что s и t – номера стержней только внутри соответствующей рекурсивно вызванной функции NumToSet.
Procedure NumToSet(n,s,t:Integer);
{Переменная cnt глобального типа LongInt.}
Var moved:LongInt;
Begin
If n>0 Then Begin
moved:=(1 Shl (n-1)) And cnt; {Значение moved равно нулю, в том случае, если диск n со стержня s не перемещался.}
If moved=0 Then Begin {Диск не перемещался.}
a[n]:=s; {Поместить диск n на стержень s.}
NumToSet(n-1,s,6-s-t); {Определение раскладки n-1 диска.}
End
Else Begin {moved <>0 ( moved = 2^(n-1)).}
a[n]:=t; {Диск n на стержне t.}
NumToSet(n-1,6-s-t,t); {Определение раскладки n-1 диска.}
End;
End
Else <вывод раскладки дисков>;
End;
Итак, осталась последняя задача – определение следующей раскладки. Видится два способа её решения. Первый заключается в том, чтобы раскладку получать через вычисление следующего перемещаемого диска. Его номер можно вычислить, зная количество совершенных перемещений. Известно, что в двоичной записи значения переменной cnt в i-ом разряде перемещенному диску соответствует 1, а не перемещенному диску – 0. Младший разряд, хранящий 1, указывает на номер последнего перемещенного диска. Увеличивая значение переменной cnt на единицу, получаем номер следующего перемещаемого диска.
В значительной степени процедура генерации следующей раскладки дисков (Next) повторяет функцию Check, последняя дополнена подсчетом количества перекладываний.
Procedure Next(n, s, t: Integer; Var cnt, d: LongInt);
Begin
If n>0 Then Begin
cnt:=cnt*2;
If a[n] = s Then Begin {Диск n еще не был перемещен со стержня s.}
Next(n-1,s,6-s-t,cnt,d);
If n=d Then a[n]:=t; {Диск n перемещаем на стержень t.}
End
Else
If a[n] = t Then Begin
cnt:=cnt+1;
Next(n-1,6-s-t,t,cnt,d);
End;
End
Else Begin {Просмотрены все диски.}
Inc(cnt); {Определяем следующую раскладку дисков.}
While (cnt Mod 2 = 0) Do Begin
Inc(d);
cnt:=cnt Div 2; {Определение последнего перемещенного диска в раскладке.}
End;
Inc(d);
End;
End;

При вызове процедуры Next возвращаемые параметры cnt и d должны быть равны 0. Недостатком данного варианта процедуры Next является ограниченность числового типа Longint.
Второй вариант генерации следующей раскладки дисков основан на определение последнего не перемещенного диска. За основу опять же взята функция Check.
Procedure Next(n,s,t: Integer; Var d:Integer);
Begin
If n>0 Then
If a[n] = s Then Begin {Диск n еще не был перемещен со стержня s.}
d:=n; {d – номер не перемещенного диска n.}
Next(n-1,s,6-s-t,d);
If n=d Then
a[n]:=t; {Диск n перемещается на стержень t.}
End
Else
If a[n] = t Then Next(n-1,6-s-t,t,d);
End;