Не дубликат
Ханойская башня с запрещенным перемещением от источника к месту назначения (C)
Ханойская башня - Как не пропускать привязку при каждой рекурсии
Это упражнение 1.2. из книги Конкретная математика Грэма, Кнута и Паташника:
Найдите кратчайшую последовательность ходов, которая перемещает башню из n дисков с левого стержня A на правый стержень B, если прямые ходы между A и B запрещены. (Каждое движение должно быть до или от среднего колышка.)
После того, как я решил математически вышеупомянутую проблему, я решил реализовать его с помощью рекурсии в Java.
Вот рекурсивный метод Я написал, чтобы решить исходную проблему:
public static void hanoi(int n, boolean left)
{
if (n == 0) return;
hanoi(n-1, !left);
if (left) System.out.println(n + " left");
else System.out.println(n + " right");
hanoi(n-1, !left);
}
Для исходной проблемы моя программа совместима с тем, что на самом деле происходит в реальном мире, когда вы пытаетесь решить проблему, но для работы модифицированной версии у меня было чтобы настроить мою программу в соответствии с реальной версией, как показано ниже.
public static void hanoi(int n, boolean left)
{
if (n == 0) return;
hanoi(n-1, left);
if (!left) System.out.println(n + " left");
else System.out.println(n + " right");
hanoi(n-1, !left);
if (!left) System.out.println(n + " left");
else System.out.println(n + " right");
hanoi(n-1, left);
}
Как вы можете видеть, моя программа никогда не использует среднюю привязку, и я ошибочно поменял местами инструкции печати для левого и правого. И все же это тот, который дал мне правильные ответы. Например, для ханой (2) должен получиться следующий результат:
1 справа - 1 справа - 2 справа - 1 слева - 1 слева - 2 справа - 1 справа - 1 справа
Может Кто-нибудь, помогите мне понять, почему это происходит, или приведите пример рекурсивного кода (псевдокода или в Java), который совместим с реальным миром?