java递归方法求解河内塔之谜
我正试图解决“河内塔”问题,即通过辅助堆栈将磁盘堆栈从最小到最大从开始堆栈移动到目标堆栈,而无需将较大的磁盘放在较小的磁盘上
他给了我算法:
If numberDisks == 1:
Display “Move the top disk from S to D”.
Else
Move(numberDisks -1, ‘S’, ‘A’, ‘D’);
Move(1, ‘S’, ‘D’, ‘A’);
Move(numberDisks -1, ‘A’, ‘D’, ‘S’);
然而,这似乎与大多数其他examples不同,后者似乎不使用Move(1,'S,'D,'A');在递归函数中
就我的代码而言,我似乎在重复每一步的基本情况,我不确定如何构造我的print语句以提供正确的输出,它应该如下所示:
Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D
尝试移动3个磁盘时
// Recursively solve Towers of Hanoi puzzle
public static void main(String[] args) {
if (handleArguments(args)) {
System.out.println("numDisks is ok");
int numDisks = Integer.parseInt(args[0]);
Move(numDisks,'s', 'a', 'd' );
}
}
// recursive case
public static void Move(int disks, char start, char aux, char destination) {
// base case
if (disks == 1) {
System.out.println("Move disk 1 from S to D");
// if number of disks is 2 or greater
} else if(disks > 1) {
Move(disks - 1, start, aux, destination);
System.out.println("move disk " + disks + " from " + start + " to " + destination);
Move(1, start, destination, aux);
Move(disks - 1, aux, destination, start);
}
}
# 1 楼答案
第一件事:了解移动n张光盘的算法(从S到D,带A)
*同样:如果有0张光盘,请停止。(有些人可能会认为这是一个更好的终止条件,因为在您的代码中,它会阻止打印语句。如果有特殊情况,它将由您介绍步骤3的打印语句自然处理。例如,当您决定更改此方法以返回步骤列表而不是打印它时,此更改只需在一个位置应用)
你提到“我似乎在重复每一步的基本情况。”如果你看看你的代码,并与我上面的陈述进行比较。您将看到在我的步骤3和步骤4之间调用
Move(1, start, destination, aux);
。这就是为什么要重复基本情况,因为要显式地调用、重复基本情况,但这样做没有任何意义我看到的另一个主要问题是:
System.out.println("Move disk 1 from S to D");
将始终按顺序打印'S'和'D',当您经常需要指定不同的移动时,请确保使用此语句的参数我不认为还有别的,但是试试看
作为对你在文章开头给出的例子的回应。它产生的输出与您的版本略有不同
您指定(或尝试)在每个步骤中移动的光盘大小,本示例仅指定将光盘从哪个堆栈移动到哪个堆栈,而不考虑其大小
以1为中间变量的递归调用将打印移动指令以移动堆栈中的最终磁盘(我的步骤3)。p>