有没有办法在没有 recursion/stacks 的情况下对河内塔进行编程？

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

是的。它可以在没有递归和没有堆栈（或模拟堆栈）的情况下进行编程。

关于汉诺塔的维基百科页面有一个关于 binary solution 的部分，其中 N 盘汉诺塔的步骤编码为数字 0 到 2 的二进制表示^N.

我不会在这里复制全部细节，但核心是一个简洁的公式，用于将移动编号 m 转换为要进行的移动：

Move m is from peg (m & m - 1) % 3 to peg ((m | m - 1) + 1) % 3, where the disks begin on peg 0 and finish on peg 1 or 2 according as whether the number of disks is even or odd

还有一个涉及格雷码的解决方案。

有没有办法在没有 recursion/stacks 的情况下对河内塔进行编程？

Is there a way to program towers of hanoi without recursion/stacks?

java

methods

recursion

loops

towers-of-hanoi