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

Рекурсивно решаем задачу «перенести башню из n−1 диска на 2-й штырь». Затем переносим самый большой диск на 3-й штырь, и рекурсивно решаем задачу «перенеси башню из n−1 диска на 3-й штырь».

Отсюда методом математической индукции заключаем, что минимальное число ходов, необходимое для решения головоломки, равно 2ⁿ − 1, где n — число дисков[2][3].

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

Расположим штыри в виде треугольника. Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем перенесём какое-нибудь из оставшихся колец (такой ход единственный), после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные — в противоположном направлении.)

Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3.

Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде. Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он запатентовал (за номером 2632058) и использовал этот код в своей импульсной системе связи.

Коды Грея могут быть применены в решении задачи о Ханойских башнях.
Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G₀), и будем двигаться по кодам Грея (от G_i переходить к G_i+1). Поставим в соответствие каждому i-ому биту текущего кода Грея i-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита i как перемещение i-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия правильного выбора хода: для нечётного N последовательность перемещений наименьшего диска f→t→r→f→t→r→… (где f — стартовый стержень, t — финальный стержень, r -оставшийся стержень), а для чётного f→r→t→f→r→t→….

// Ханойские башни
#include <iostream>

using namespace std;

void hanoi_towers(int quantity, int from, int to, int buf_peg)	//quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)
{								//buf_peg - промежуточный колышек(1-3)
	if (quantity != 0)
	{
		hanoi_towers(quantity-1, from, buf_peg, to);

		cout << from << " -> " << to << endl;

		hanoi_towers(quantity-1, buf_peg, to, from);
	}
}

int main()
{
        setlocale(LC_ALL,"rus");
	int start_peg, destination_peg, buffer_peg, plate_quantity;
	cout << "Номер первого столбика:" << endl;
	cin >> start_peg;
	cout << "Номер конечного столбика:" << endl;
	cin >> destination_peg;
	cout << "Номер промежуточного столбика:" << endl;
	cin >> buffer_peg;
	cout << "Количество дисков:" << endl;
	cin >> plate_quantity;

	hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);
return 0;
}

program hanoibns(input,output);
var n:integer;
procedure tower(k:integer;a,b,c:char);
begin
     if k>1 then tower(k-1,a,c,b);
     writeln('from ',a,' to ',b);
     if k>1 then tower(k-1,c,b,a)
end;
begin
     read(n);
     tower(n,'A','C','B')
end.

hanoiSteps :: Int -> [(Int, Int)]
hanoiSteps n = step (max 0 n) 1 3 2 []
  where
    step 0 _ _ _ rest = rest
    step n f t s rest = step (n - 1) f s t $ (f, t) : step (n - 1) s t f rest

def Hanoi(n, A, C, B):
    if (n != 0):
        Hanoi(n - 1, A, B, C)
        print ('Move the plate from', A, 'to', C)
        Hanoi(n - 1, B, C, A)

public class Hanoi {
    public static void hanoiTowers(int quantity, int from, int to, int buf_peg)	{
        if (quantity != 0)
        {
            hanoiTowers(quantity-1, from, buf_peg, to);

            System.out.println("" + from + " -> " + to );

            hanoiTowers(quantity-1, buf_peg, to, from);
        }
    }

    public static void main(String[] args) {
        int start_peg = 1, destination_peg = 2, buffer_peg = 3, plate_quantity = 4;
        hanoiTowers(plate_quantity, start_peg, destination_peg, buffer_peg);
    }
}

#include <stdio.h>
#include <math.h>

void carryingOver(int, int, int);

main()
{
   int number, countDisk, counter = 1, count;

   printf("Введите количество дисков: "); /* Ханойская башня */
   scanf("%d", &number);

   while (counter <= pow(2, number) - 1) { /* Запускаем цикл повторений */

      if (counter % 2 != 0) { /* На нечетном ходу мы будем трогать только самый маленький диск */
         printf("%3d %d ", counter, 1);
         carryingOver(number, counter, 1); /* С помощью этой функции определяем для данного диска перемещение */
      }

      else {  /* Определяем диск который нужно переместить на четном ходу */
         count = counter;
         countDisk = 0;

         while (count % 2 == 0) {  /* Диск который нужно переместить */
            countDisk++;           /* будет числом деления номера хода на 2 без остатка */
            count = count / 2;
         }
         printf("%3d %d ", counter, countDisk + 1);
         carryingOver(number, counter, countDisk + 1);
      }
      counter++;
   }
   return 0;
}

/* Функция определения перемещения дисков */
void carryingOver(int n ,int i, int k)
{
   int t, axisX, axisY, axisZ;

   if (n % 2 == 0) {  /* Определяем порядок осей в зависимости от четности */
      axisX = 1;      /* и не четности количества дисков */
      axisY = 2;
      axisZ = 3;
   }

   else {
      axisX = 1;
      axisY = 3;
      axisZ = 2;
   }

   /* Номер хода можно представить единственным образом */
   /* как произведение некоего нечетного числа на степень двойки */
   /* k будет номером диска который мы перемещаем */
   t = ((i / pow(2, k - 1)) - 1) / 2;

   if (k % 2 != 0) {    /* Определяем перемещение дисков  для нечетного хода */

      switch (t % 3) {         /* Выбираем перемещение в зависимости от данного условия */
         case 0:               
            printf("%d -> %d\n", axisX, axisY);
            break;
         case 1:
            printf("%d -> %d\n", axisY, axisZ);
            break;
         case 2:
            printf("%d -> %d\n", axisZ, axisX);
            break;
      }
   }

   else {     /* Определяем перемещение дисков  для чётного хода */

      switch (t % 3) {
         case 0:
            printf("%d -> %d\n", axisX, axisZ);
            break;
         case 1:
            printf("%d -> %d\n", axisZ, axisY);
            break;
         case 2:
            printf("%d -> %d\n", axisY, axisX);
            break;
      }
   }
}

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

Очевидно, что для любого количества стержней существует алгоритм для нахождения оптимальных решений, достаточно представить головоломку в виде неориентированного графа, сопоставив размещениям дисков вершины, а ходам — рёбра, и использовать любой алгоритм поиска (например, поиск в ширину) для нахождения оптимального решения. Однако эффективной стратегии определения оптимального решения для большого числа дисков нет: количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками, остаётся неизвестным.

Существует предположительно оптимальный алгоритм Фрейма — Стюарта, разработанный в 1941 году[4]. Связанная гипотеза Фрейма — Стюарта утверждает, что алгоритм Фрейма — Стюарта всегда находит оптимальное решение. Оптимальность алгоритма Фрейма — Стюарта была экспериментально проверена вплоть до 30 дисков на 4 стержнях[5]. В 2014 году было окончательно доказано, что для четырёх стержней Алгоритм Фрейма — Стюарта является оптимальным [6].

Другие варианты решения Ханойской башни с четырьмя стержнями рассматриваются в обзорной статье Пола Стокмайера[7].

Алгоритм Фрейма — Стюарта, дающий оптимальное решение для четырёх и предположительно оптимальное решение для большего количества стержней, описывается следующим образом:

• Пусть ${\displaystyle n}$ — количество дисков.
• Пусть ${\displaystyle r}$ — число стержней.
• Определим ${\displaystyle T(n,r)}$ как наименьшее число ходов, необходимое для переноса n дисков с использованием r стержней.

Алгоритм может быть описан рекурсивно:

1. Для некоторого ${\displaystyle k}$, ${\displaystyle 1\leq k<n}$, перенести верхние ${\displaystyle k}$ на стержень i, не являющийся ни начальным, ни конечным стержнем, затратив на это ${\displaystyle T(k,r)}$ ходов.
2. Не используя стержень i, содержащий теперь верхние ${\displaystyle k}$ дисков, перенести оставшиеся ${\displaystyle n-k}$ дисков на конечный стержень, используя только оставшиеся ${\displaystyle r-1}$ стержней и затратив на это ${\displaystyle T(n-k,r-1)}$ ходов.
3. Наконец, переместить верхние ${\displaystyle k}$ дисков на конечный стержень, затратив на это ${\displaystyle T(k,r)}$ ходов.

На весь процесс требуется ${\displaystyle 2T(k,r)+T(n-k,r-1)}$ ходов. Значение ${\displaystyle k}$ выбирается таким образом, чтобы значение этого выражения было минимальным. В случае 4 стержней, оптимальное ${\displaystyle k}$ равно ${\displaystyle n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1}$, где ${\displaystyle \left\lfloor \cdot \right\rceil }$ - это функция ближайшего целого.[8]