尝试使用我自己的程序来理解 Hanoi 算法
Trying to understand Hanoi algorithm using my own program
我有以下河内塔的工作程序,我们将从 A--B 塔移动磁盘,C 是额外的 tower.I 定义函数的初始状态如下:moveDisks(n, 'A', 'B', 'C');
我将使用以下算法在每次移动时打印:
public static void moveDisks(
int n,
char fromTower,
char toTower,
char auxTower)
{
if (n == 1) // Stopping condition
System.out.println(
"Move disk " + n + " from " + fromTower + " to " + toTower);
else
{
moveDisks(n - 1, fromTower, auxTower, toTower);
System.out.println(
"Move disk " + n + " from " + fromTower + " to " + toTower);
moveDisks(n - 1, auxTower, toTower, fromTower);
}
}
}
从我程序中的递归调用可以看出,我有三种可能的调用:
A--B--C //fromTower, toTower,auxTower
A--C--B //fromTower, auxTower, toTower
C--B--A //auxTower, toTower, fromTower
但是,我得到了 3
个磁盘的以下打印输出:
The moves are:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
我知道我的程序是正确的,但我并没有真正了解它是如何进行 B--C
和 C--A
调用的,因为我从未进行过这样的 function/method。如果你能的话,我将不胜感激使用我的 A--B--C
、fromTower, toTower,auxTower
模型显示此递归方法如何在三个磁盘方面工作。
您仅从初始调用的角度考虑对 moveDisks
的可能调用:
moveDisks(.., 'A', 'B', 'C')
会打电话
moveDisks(.., 'A', 'C', 'B')
moveDisks(.., 'C', 'B', 'A')
但这些调用将继续递归,因此下一轮调用将是
moveDisks(.., 'A', 'B', 'C')
moveDisks(.., 'B', 'C', 'A') --> moving B to C
和
moveDisks(.., 'C', 'A', 'B')
moveDisks(.., 'A', 'B', 'C')
...
我自己在last.I弄明白了,可以看到它惊人地遵循二叉树结构,首先调用最左边的child(在这种情况下,child是一个打印语句)在递归中。
我的理解错误是,我假设 A--B--C
为所有递归调用的 from-to-aux
,尽管 from-to-aux
变量一直在变化 throughout.So当我从 n=3
和 A= from,B=to, C= aux
开始时,我收到以下调用:moveDisks(2, 'A', 'C', 'B')
和 moveDisks(2, 'C', 'B', 'A')
。现在,这些递归调用中的每一个都将独立地开始它们自己的调用,但对于第一个现在一个 A=from, C=to, and B=aux
和第二个 C=from, B=to and A=aux
。所以对于第一个我得到 moveDisks(1,'A','B','C')
和 moveDisks(1,'B','C','A')
调用,第二个我得到 moveDisks(1,'C','A','B')
和 moveDisks(1,'A','B','C')
calls.Recurssion 继续,直到到达停止点。
注意:太神奇了!我学的是递归,结果也学了二叉树!
我有以下河内塔的工作程序,我们将从 A--B 塔移动磁盘,C 是额外的 tower.I 定义函数的初始状态如下:moveDisks(n, 'A', 'B', 'C');
我将使用以下算法在每次移动时打印:
public static void moveDisks(
int n,
char fromTower,
char toTower,
char auxTower)
{
if (n == 1) // Stopping condition
System.out.println(
"Move disk " + n + " from " + fromTower + " to " + toTower);
else
{
moveDisks(n - 1, fromTower, auxTower, toTower);
System.out.println(
"Move disk " + n + " from " + fromTower + " to " + toTower);
moveDisks(n - 1, auxTower, toTower, fromTower);
}
}
}
从我程序中的递归调用可以看出,我有三种可能的调用:
A--B--C //fromTower, toTower,auxTower
A--C--B //fromTower, auxTower, toTower
C--B--A //auxTower, toTower, fromTower
但是,我得到了 3
个磁盘的以下打印输出:
The moves are:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
我知道我的程序是正确的,但我并没有真正了解它是如何进行 B--C
和 C--A
调用的,因为我从未进行过这样的 function/method。如果你能的话,我将不胜感激使用我的 A--B--C
、fromTower, toTower,auxTower
模型显示此递归方法如何在三个磁盘方面工作。
您仅从初始调用的角度考虑对 moveDisks
的可能调用:
moveDisks(.., 'A', 'B', 'C')
会打电话
moveDisks(.., 'A', 'C', 'B')
moveDisks(.., 'C', 'B', 'A')
但这些调用将继续递归,因此下一轮调用将是
moveDisks(.., 'A', 'B', 'C')
moveDisks(.., 'B', 'C', 'A') --> moving B to C
和
moveDisks(.., 'C', 'A', 'B')
moveDisks(.., 'A', 'B', 'C')
...
我自己在last.I弄明白了,可以看到它惊人地遵循二叉树结构,首先调用最左边的child(在这种情况下,child是一个打印语句)在递归中。
我的理解错误是,我假设 A--B--C
为所有递归调用的 from-to-aux
,尽管 from-to-aux
变量一直在变化 throughout.So当我从 n=3
和 A= from,B=to, C= aux
开始时,我收到以下调用:moveDisks(2, 'A', 'C', 'B')
和 moveDisks(2, 'C', 'B', 'A')
。现在,这些递归调用中的每一个都将独立地开始它们自己的调用,但对于第一个现在一个 A=from, C=to, and B=aux
和第二个 C=from, B=to and A=aux
。所以对于第一个我得到 moveDisks(1,'A','B','C')
和 moveDisks(1,'B','C','A')
调用,第二个我得到 moveDisks(1,'C','A','B')
和 moveDisks(1,'A','B','C')
calls.Recurssion 继续,直到到达停止点。
注意:太神奇了!我学的是递归,结果也学了二叉树!