河内塔递归

我已经阅读了河内塔问题陈述和解决方案。该解决方案指出，如果必须将一组N个磁盘从A移动到B，请将C用作临时磁盘，并将N-1个磁盘从A传输到C.然后将第N个磁盘从A传输到B，然后将N-1个磁盘从C到B.我知道这个问题已经减小了，因此是递归实现的竞争者。但是，我们一次不能传输超过1个磁盘。我们如何能够首先转移N-1个磁盘。河内塔递归

来源

2014-09-02 sad

见http://stackoverflow.com/q/25625964/489590了解更多详情。 – 2014-09-02 14:36:35

以递归方式传输'N'个磁盘的方式传输'N-1'磁盘。当你下到一个磁盘时，转移是微不足道的。 – Paulpro 2014-09-02 14:37:41

@Srinath Kattula：如果你用C++标记这个问题，请添加一些源代码或删除标记。 – duDE 2014-09-02 14:37:52

通过使用递归。另请参阅Tower of Hanoi: Recursive Algorithm和维基百科页面

递归如下：您知道如何移动1张光盘，假设您知道如何移动n-1张光盘，您如何移动n张光盘？

的“假设”的部分是你的递归：你通过移动9，然后1，那么9
要移动的9盘10个移动盘，你的一举一动8，然后1，然后8
要移动8盘...
...
要移动2盘，你的一举一动1，然后1，然后按1

来源

2014-09-02 14:41:50 valjeanval42

这就是递归步骤。使用相同的算法从A转移N-1磁盘，将N磁盘从A转移到B.如果N是1，则只需移动单个磁盘即可。（或者，如果N等于零，则不做任何事情）。

伪代码：

move(N, A, B): 
    if (N > 0) 
     move(N-1, A, C) 
     move_single_disk(A, B) 
     move(N-1, C, B)

来源

2014-09-02 14:41:55

回答

相关问题