Есть ли способ запрограммировать башни Ханоя без рекурсии / стеков?

Question

Я недавно написал программу для решения Ханойских башен с использованием рекурсии. Но есть ли способ решить эту загадку без использования стеков или рекурсии - предпочтительно циклы или что-то в этом порядке.

Вот код, который я написал с помощью рекурсии:

static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod); 
            return; 
        } 
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
        System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); 
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
    } 

Спасибо за любую помощь заранее:)

Answer 1

Да. Он может быть запрограммирован без рекурсии и без стеков (или имитированных стеков).

На странице Википедии в Ханойской башне есть раздел о бинарном решении , в котором описаны шаги для башни с N-дисками. Ханоя закодированы в двоичном представлении чисел от 0 до 2 ^N .

Я не буду копировать полную информацию здесь, но ядро ​​представляет собой аккуратную формулу для перевода номера хода m на ход, который необходимо сделать:

Перемещение m происходит от колышка (m & m - 1) % 3 к колышку ((m | m - 1) + 1) % 3, где диски начинаются на колышке 0 и заканчиваются sh на колышке 1 или 2 в зависимости от того, является ли количество дисков четным или нечетным

Существует другое решение, включающее коды Грея.