Ханойские башни. Дорога на итерацию.

Архив 2014/15
#1

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

Классическую раскрутку рекурсии в этой задаче с использованием стека можно посмотреть, например, здесь [1]. Она довольно громоздкая, поэтому я не публикую. Тем паче существует очень изящная реализация с использованием битовой арифметики, которая была обнаружена здесь [2]. Весь алгоритм пишется буквально в две строчки.

Пусть стержни занумерованы таким образом: 0, 1, 2. Вcего, как известно, нужно сделать 1 shl n - 1 (<=> 2^n - 1) перемещений, где n - кол-во дисков, которых нужно перенести с нулевого стержня. По сути, нужно научиться определять номера стержней, задействованных в перемещении диска, только лишь по известному двоичному представлению номера хода.

Для начала решим промежуточную задачу: нужно вычислить кол-во перемещений диска к данному моменту - m. Это можно сделать, отбросив первую справа единицу и последующие нули. То есть, если i = 01010100, то m = 01010 = 10, т.е. некий диск d, который мы собираемся перенести, к данному моменту перекладывался 10 раз. На самом деле, этот номер этого некого диска d также можно вычислить по i-му перемещению, он равен кол-ву бит в цепочке вида 10…00, то есть для рассмотренного примера с i = 01010100, 10 раз перекладывался диск с номером 100 = 3. Есть формула, которая легко посчитает номер диска при заданном шаге, но смысла её писать особо нет, ибо нас все же интересует номера СТЕРЖНЕЙ, а не дисков. Для вычисления m работает формула: i And (i - 1). Она не отбрасывает единицу и последующие нули, а просто выделяет нужные биты в числе m. То есть, если i = 01010100, то после применения формулы, результат будет 01010000, иными словами, формула просто обнуляет первую справа единицу. Можно сказать, что в таком представлении, m = m * 2^d, где d - номер диска, который нужно перенести на i-ом шаге. А номер стержня, с которого мы перекладываем диск, - такая же операция, взятая по модулю 3! Аналогично, формула для нахождения m + 1: i Or (i - 1) + 1 - количество перемещений диска к заданному моменту плюс 1. Здесь, также домножив m + 1 на 2^d и поделить по модулю 3, получится номер стержня, на который мы перекладываем диск. Кроме того, множитель 2^d совсем не мешает, от цепочки нулей в m и m - 1 не нужно удалять цепочку нулей в конце битовой строки. Итого, всего пару строчек на решение задачи:

// При нечетном n - перенос всех дисков с 0 стержня на 2, при четном - все диски на стержень 1.

procedure Hanoi(n: integer);
begin 
  for var i := 1 to 1 shl n - 1 do
    writeln('Перенести с ', (i And (i - 1)) mod 3, 
              ' на ', i Or (i - 1) + 1) mod 3);
end;

Ссылаюсь на: [1] Шень А. Прогрммирование: теоремы и задачи. МЦНМО, 2004 [2] http://en.wikipedia.org/wiki/Tower_of_Hanoi

2 лайка
#2

Можно поправить нумерацию так, чтобы при нечетном n был перенос всех дисков с 1 на 3, при четном - с 1 на 2. Достаточно заменить взятие по модулю 3 взятием по модулю 3 + 1. То есть: ``` (i and (i - 1)) mod 3 + 1

#3

Написал визуализацию hanoi.pas (2.1 КБ)

1 лайк
#4

Исправили ошибку с foreach

1 лайк
#5

Хорошая новость.

#6