解决河内拼图塔的递归方法

我试图找出“河内塔”的问题，它通过一种方式将堆栈中从最小到最大的磁盘从起始堆栈移动到目标堆栈。没有在较小的磁盘上放置较大的磁盘。解决河内拼图塔的递归方法

我被赋予了algorithim：

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不同这似乎不使用移动（1，“S”，“d”，“A”）的工作;在递归函数中。

至于我的代码代表，我似乎重复基本情况的一举一动，和林不知道如何构建我的打印报表给正确的输出应该是这样的：

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); 
    } 
}

来源

2016-02-15 Silverfin

我读了两遍，但我仍然不清楚你的问题。你能否考虑改写你的问题并清楚地表明你的问题？ – user2004685

@ user2004685当然，我的递归函数https://gist.github.com/Silverfin13/a7ec33e296396b8c8f90要求用户输入他们想放入[河内问题塔]的磁盘数量（http：//www.javawithus .com/programs/towers-of-hanoi），并且一步一步地告诉哪个磁盘要从上到下编号从1到n，以便将所有磁盘移动到目标磁盘。但是，它会为每一步重复我的基本情况，并且不会正确打印要采取的步骤。 – Silverfin

第一件事：了解移动ñ光盘的算法（从S到d，与A）

如果只有一个圆盘移动，只是移动它，然后停止*。
移动N - 选自S 1张光盘为A，与D.
移动第n个盘从S到d
移动n - 源自A 1张碟片d，与S

*同样：如果有0张光碟，请停止。（有些人会认为这是优越的终止条件，因为在你的代码中，当有一个特殊情况出现时，它会阻止打印语句，它将由你用第3步打印语句自然处理。例如，您决定更改此方法以返回步骤列表而不是打印它，此更改只能应用于一个位置）

您提到“我似乎重复了每次移动的基本情况“。如果你看看你的代码，并比较我上面的陈述。你会看到你在我的步骤3和步骤4之间调用Move(1, start, destination, aux);。这就是为什么你要重复你的基本情况，因为你明确地调用，重复你的基本情况，但它没有任何意义。

我可以看到的另一个主要问题： System.out.println("Move disk 1 from S to D");将总是按顺序打印'S'和'D'，当您经常需要指定不同的移动时，确保使用该语句的参数。

我不认为还有其他东西，但试试看。

回复您在帖子开始时给出的例子。它会产生比你的版本差别很大的输出。

您的指定（或尝试）在每个步骤应移动光盘的大小，本示例仅指定将光盘移动到哪个堆栈，而不管其大小。

以1作为其中间参数的递归调用将打印用于移动堆栈中最终光盘的移动指令（我的步骤3）。

来源

2016-02-15 06:30:41 moreON

我似乎仍然得到一个奇怪的[输出]（https://gist.github.com/Silverfin13/77430ce38895650922a2） – Silverfin

@ShahobMousavi请详细说明。你有什么改变，你的新输出是什么？你认为是什么导致它不正确？（如果你需要添加格式良好的信息，你可以编辑你的问题） – moreON

@ShahobMousavi你应该再看看你的递归调用，以及定义中参数的排序。（以及特殊情况下的打印行中的空格） – moreON

解决河内拼图塔的递归方法

回答

相关问题