河内塔：recursionalgorithm

虽然我对理解recursion没有任何问题，但我似乎无法把头脑放在河内问题的recursion解决scheme上。这里是维基百科的代码：

procedure Hanoi(n: integer; source, dest, by: char); Begin if (n=1) then writeln('Move the plate from ', source, ' to ', dest) else begin Hanoi(n-1, source, by, dest); writeln('Move the plate from ', source, ' to ', dest); Hanoi(n-1, by, dest, source); end; End;

我理解基本案例和将问题分解为更小块的概念，直到您能够移动单个磁盘。但是，我无法弄清楚非基本情况下的两个recursion调用是如何协同工作的。也许有人可以帮我吗？谢谢。

实际上，你从那里拿到代码的部分也提供了一个解释：

将n个光盘从挂钩A移到挂钩C：

将n-1张光盘从A移动到B.这使光盘#n单独挂在钉A上

将光盘#n从A移到C

将n-1张光盘从B移动到C，使它们坐在光盘#n上

很明显，你必须先删除n -1张光盘才能访问第n张光盘。而且你必须首先把它们移到另一个钉子上，而不是你想要全塔出现的地方。

除了光盘数量之外，post中的代码还有三个参数：一个源插入，一个目标插入和一个临时挂钩，光盘可以存储在这两个盘之间（每个大小为n – 1的光盘都适合）。

recursion实际上发生了两次，那里，一次之前，一次。在写入之前，将n -1张光盘移动到临时挂钩上，使用目标挂钩作为临时存储（recursion调用中的参数顺序不同）。之后，剩余的光盘将被移动到目标挂钩，然后第二次recursion迫使整个塔的移动，通过将n – 1塔从临时挂钉移动到目标挂钉上方，在光盘n之上。

一年前我有function编程课程，并为algorithm绘制此图。希望它有帮助！

 (0) _|_ | | __|__ | | ___|___ | | ____|____ ____|____ ____|____ (1.1) | | | __|__ | | ___|___ _|_ | ____|____ ____|____ ____|____ (A -> B) (1.2) | | | | | | ___|___ _|_ __|__ ____|____ ____|____ ____|____ (A -> C) (1.3) | | | | | _|_ ___|___ | __|__ ____|____ ____|____ ____|____ (B -> C) (2.1) | | | | | _|_ | ___|___ __|__ ____|____ ____|____ ____|____ (A -> B) (3.1) | | | | | | _|_ ___|___ __|__ ____|____ ____|____ ____|____ (C -> A) (3.2) | | | | __|__ | _|_ ___|___ | ____|____ ____|____ ____|____ (C -> B) (3.3) | _|_ | | __|__ | | ___|___ | ____|____ ____|____ ____|____ (A -> B)

3环问题已被分解为2个2环问题（1.x和3.x）

在http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html上有recursion河内实现的很好的解释。;

总结一下，如果你想把A盘的底盘移动到B盘，你首先必须把A盘上的所有小盘从A盘移到C盘。然后第二个recursion调用就是把盘子移到C盘在您的底座将单个大型平板从A移动到B后，回到B上。

我同意这个观点在你第一眼看的时候就不是立竿见影的，但是当你开始看的时候，这是相当简单的。

基本情况：你的塔的大小是1.所以你可以一次完成，从源头直接到目的地。

recursion的情况下，你的塔的大小为n> 1.所以你移动n-1号塔顶塔到一个额外的挂钩（by），将大小为1的塔底移动到目标挂钩，从到目的地。

所以用一个简单的例子，你有一个高度为2的塔：

  _|_ | | __|__ | | ===== ===== =====

第一步：把2-1（= 1）的顶塔移到额外的挂钩（中间的那个，可以这么说）。

  | | | __|__ _|_ | ===== ===== =====

下一步：将底部光盘移动到目的地：

  | | | | _|_ __|__ ===== ===== =====

最后，将（2-1）= 1的最高塔移到目的地。

  | | _|_ | | __|__ ===== ===== =====

如果你仔细想想，即使是三层以上的塔，总是会有一个空的多余的挂钩，或者一个挂着所有较大的圆盘的挂钩，当交换塔时，recursion就会使用。

假设我们想通过B将光盘从A移动到C，则：

将较小的光盘移动到B.
将另一张光盘移到C.
把B移到C
从A移到B
从C移到A

如果重复上述所有步骤，光盘将会传输。

我感到痛苦！

虽然这是一个旧的post，但我认为真正需要理解的不是“将此转移到该方法”，而是要使用recursion的副作用。

对我来说非常宝贵的帮助是“小小的Schemer”，它教导人们思考和编写recursion函数。

然而，这教导读者在下一次recursion调用中使用返回结果的结果。

在河内塔，答案不是在返回的结果本身，而是在观察返回的结果。

这个魔术发生在函数参数的连续重排中。

是的，这个问题真的有三个部分：

移动一个较小的塔到备用挂钩
将最后一张光盘移到目标挂钩
将备用挂钩上的剩余塔移到目标挂钩上。

在scheme中：

 (define (th nabc) (if (zero? n) 'done (begin (th (- n 1) acb) (display (list ac)) (newline) (th (- n 1) bac)))) (th 5 'source 'spare 'destination)

然而，显示function参数是解决问题的关键，也是对呼叫双树状结构的重要理解。

该解决scheme还proof by induction和温暖的光线向传统控制结构的所有程序员传达了proof by induction的力量。

可以肯定的是，手工解决这个问题相当令人满意。

统计光盘的数量
如果连的话，把第一张光碟移到备用的挂钉上，然后进行下一个合法的移动（不涉及上面的光碟）。然后将顶部光盘移到目标挂钩，进行下一个合法移动（nittd）。然后将顶部光盘移到源插件上，进行下一个合法移动（nittd）…
如果奇怪的话，将第一张光盘移到目的地挂钩，进行下一个合法移动（不涉及顶部光盘）。然后移动顶部光盘到备用挂钩，进行下一个合法的移动（nittd）。然后将顶部光盘移到源插件上，进行下一个合法移动（nittd）…

最好的做法是始终用同一只手握住顶部的光碟，并始终将其向同一方向移动。

n光盘的最后移动次数是2^n - 1 ， move n disc to destination的过程是一半的。

最后，向一位同事，你的妻子甚至狗（甚至他们不听）解释一个问题能够巩固启迪，这是很有趣的。

在读完所有这些解释之后，我想我会用我的教授用来解释河内recursion解决scheme的方法。再次用n表示环的数量，A，B，C表示钉。函数的第一个参数是环的数量，第二个参数代表源锚，第三个是目标锚，第四个是备用锚。

 procedure Hanoi(n, A, B, C); if n == 1 move ring n from peg A to peg B else Hanoi(n-1, A, C, B); move ring n-1 from A to C Hanoi(n-1, C, B, A); end;

我在研究生院受教，决不会觉得惭愧。那么，让我们看看n = 5的这个algorithm。首先问自己的问题是， 如果我想将第5个环从A移到B，其他4个环在哪里？ 如果第5个环占用了peg A，我们想将它移动到peg B，那么其他4个环就只能在peg C上面。在上面的algorithm中， 河内（n-1，A，C，B）将所有那4个其他的环移动到C，所以环5将能够从A移动到B.按照这个algorithm，我们看n = 4。如果环4将从A移到C，环3和小吗？它们只能在挂钩B上。接下来，对于n = 3，如果环3将从A移动到B，环2和环1在哪里？当然挂在C上。如果你继续遵循这个模式，你可以看到recursionalgorithm在做什么。这种方法不同于新手的方法，因为它会查看最后一个磁盘的第一个磁盘和最后一个磁盘。

把它看作一个堆栈，用整数表示磁盘直径（4,3,2,1）。第一次recursion调用将被调用3次，从而填充运行时堆栈，如下所示

第一次电话：1.第二次电话：2,1。第三个电话：3,2,1。

在第一次recursion结束后，运行时栈的内容从最大直径popup到中间极（先进后出）。接下来，将直径为4的磁盘移动到目的地。

第二次recursion调用与第一次相同，除了将元素从中间杆移动到目的地。

这很简单。假设你想从A移到C，

如果只有一个磁盘，就移动它。

如果有多个磁盘，请执行

移动所有磁盘（n-1个磁盘），除了从A到B的最下面一个磁盘
将底部磁盘从A移到C
将第一步中的n-1个磁盘从A移动到C.

请记住，在移动n-1个磁盘时，第n个磁盘根本不会成为问题（一旦它比所有其他磁盘都大）

请注意，移动n-1磁盘再次出现同样的问题，直到n-1 = 1，在这种情况下，你将会在第一个if（你应该移动它）。

程序如何知道，即使是“src”到“aux”，奇数是“src”到“dst”，这个问题的答案就在于程序。如果你用4个碟片分解拳头，那么看起来像这样：

 hanoi(4, "src", "aux", "dst"); if (disc > 0) { hanoi(3, 'src', 'dst', 'aux'); if (disc > 0) { hanoi(2, 'src', 'aux', 'dst'); if (disc > 0) { hanoi(1, 'src', 'dst', 'aux'); if (disc > 0) { hanoi(0, 'src', 'aux', 'dst'); END document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux); hanoi(0, 'aux', 'src', 'dst'); END }

4碟（偶数）的第一招也是从Src到Aux。

正如我们的一些朋友build议的，我删除了前两个答案，我在这里合并。

这给你清楚的理解。

一般的algorithm是…

algorithm：

 solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination { if(n==0)return; solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call) }

这里是工作示例点击这里

 public static void hanoi(int number, String source, String aux, String dest) { if (number == 1) { System.out.println(source + " - > "+dest); } else{ hanoi(number -1, source, dest, aux); hanoi(1, source, aux, dest); hanoi(number -1, aux, source, dest); } }

 void TOH(int n, int a, int b){ /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6. */ int c = 6-ab; if(n==1){ cout<<"Move from "<<a<<" to "<<b<<"\n"; } else{ // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem. TOH(n-1, a, c); // Move the last alone disk from 1st to 3rd stack. TOH(1, a, b); // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem. TOH(n-1, c, b); } } int main() { TOH(2, 1, 3); cout<<"FINISHED \n"; TOH(3, 1, 3); cout<<"FINISHED \n"; TOH(4, 1, 3); return 0; }

有三个塔，即源塔，目的塔和助手塔。源塔有所有的磁盘，你的目标是将所有的磁盘移动到目标塔，并确保这样做，你永远不会把更大的磁盘放在一个较小的磁盘上。我们可以在下面的步骤中使用recursion来解决这个问题：

源塔上有n个磁盘

基本情况：n = 1如果源塔中只有一个磁盘，请将其移动到目标塔。

recursion情况：n> 1

将最高的n-1个磁盘从源塔移到辅助塔
将剩余的唯一磁盘（第1步之后）移动到目标塔
将现在在助手塔中的n-1个磁盘移动到目标位置
塔，使用源塔作为帮手。

Java中的源代码：

 private void towersOfHanoi(int n, char source, char destination, char helper) { //Base case, If there is only one disk move it direct from source to destination if(n==1){ System.out.println("Move from "+source+" to "+destination); } else{ //Step1: Move the top n-1 disks from source to helper towersOfHanoi(n-1, source, helper, destination); //Step2: Move the nth disk from source to destination System.out.println("Move from "+source+" to "+destination); /*Step3: Move the n-1 disks(those you moved from source to helper in step1) * from helper to destination, using source(empty after step2) as helper */ towersOfHanoi(n-1, helper, destination, source); } }

第一次recursion调用将源码中除最大的那个之外的所有块移动到使用dest作为辅助堆。完成之后，除了最大的部分之外，所有的部分都将被搁置，而最大的一部分是免费的。现在，您可以将最大的一个移动到dest，并使用另一个recursion调用将所有片段从dest移动到dest。

recursion调用不会知道最大片段的任何内容（即他们将忽略它），但这没关系，因为recursion调用将只处理较小的片段，因此可以自由移动和移出最大片段。

作为CS的学生，你可能听说过math归纳。河内塔的recursion解决scheme类似 – 只有不同的部分才是真正不会像B和C那样迷失在全塔最后。

从简单的意义上说，这个想法是按照与现在相同的光盘顺序填充三个定义的塔中的另一个塔，而在该过程中的任何时间没有更大的光盘与小光盘重叠。

让'A'，'B'和'C'三个塔。 “A”最初将是包含“n”个光盘的塔。 'B'可以用作中间塔，'C'是目标塔。

algorithm如下：

使用“C”将n-1个光盘从塔“A”移动到“B”
将光盘从“A”移到“C”
使用“A”将n-1个光盘从塔“B”移动到“C”

在java中的代码如下：

公开课TowerOfHanoi {

 public void TOH(int n, int A , int B , int C){ if (n>0){ TOH(n-1,A,C,B); System.out.println("Move a disk from tower "+A +" to tower " + C); TOH(n-1,B,A,C); } } public static void main(String[] args) { new TowerOfHanoi().TOH(3, 1, 2, 3); }

}

这里解释一下。看看图片 – >

在这里输入图像描述

通过调用Movetower(3,a,b,c) ，您打算将所有3个光盘从A塔移动到B塔。所以顺序调用是 – >

 1. Movetower(3,a,b,c) // No Move needed 2. Movetower(2,a,c,b) // No move needed 3. Movetower(1,a,b,c) // Here is the time to move, move disc1 from a to b 4. Movetower(2,a,c,b) // Returning to this call again, this is the time to move disc2 from a to c 5. Movetower(1,b,c,a) // Again the time to move, this time disc1 from b to c 6. Movetower(3,a,b,c) // Returning to this call again, this is the time to move disc3 from a to b 7. Movetower(2,c,b,a) // Not the time to move 8. Movetower(1,c,a,b) // Here is the time to move, move disc1 from c to a 9. Movetower(2,c,b,a) // Returning to this call again, this is the time to move disc2 from c to b 10.Movetower(1,c,a,b) // Here is the time to move, move disc1 from a to b

希望它有助于:)

对于animation： https ： //www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

这里是我使用golangrecursion的河内问题解决scheme代码。 `主包

 import "fmt" func main() { toi(4, "src", "dest", "swap") } func toi(n int, from, to, swap string) { if n == 0 { return } if n == 1 { fmt.Printf("mov %v %v -> %v\n", n, from, to) return } toi(n-1, from, swap, to) fmt.Printf("mov %v %v -> %v\n", n, from, to) toi(n-1, swap, to, from) }`

Tower (N,source,aux.dest):

 if N =1 Then Write : Source -> dest return end of if

将N-1磁盘从挂钩源移动到挂钩辅助
```
 call Tower (N-1, source, dest, aux) 
```
写源 – > dest
将N-1个磁盘从peg aux移到peg dest
```
 call Tower (N-1, source, dest, aux) 
```
返回

/ ** * * / package com.test.recursion;

/ ** * @author kamals1986河内塔问题的recursionalgorithm*algorithm通过幂（2，n）增长。 * /公共课TowerOfHanoi {

 private static String SOURCE_PEG = "B"; private static String SPARE_PEG = "C"; private static String TARGET_PEG = "A"; public void listSteps(int n, String source, String target, String spare) { if (n == 1) { System.out.println("Please move from Peg " + source + "\tTo Peg\t" + target); } else { listSteps(n - 1, source, spare, target); listSteps(1, source, target, spare); listSteps(n - 1, spare, target, source); } } public static void main(String[] args) { long startTime = System.currentTimeMillis(); new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG); long endTime = System.currentTimeMillis(); System.out.println("Done in " + (endTime - startTime) / 1000 + "\t seconds"); }

}

 def Hanoi(n, A, B, C): if(n==1): print "move plates to empty peg" else: Hanoi(n-1, A, B, C) print "move"+str(n)+" to peg "+C Hanoi(n-1, B, C, A)

我也试图获得recursion。

我发现了一种我认为的方式，

我想它像一连串的步骤（步骤是不变的，它可能会改变，取决于前一个节点）

我必须弄清楚2件事情：

前一个节点
一步一种
之后还有什么其他的电话（这是下一个电话的参数

例

阶乘

1,2,6,24,120 ………或

1,2 *（1），3 *（2 * 1），4 *（3 * 2 * * 1.5（4 * 3 * 2 * 1）

step =最后一个节点的倍数

在步骤之后，我需要到下一个节点，抽象1

好

 function = n*f(n-1) its 2 steps process from a-->to step--->b

我希望这个帮助，只是想想2 thniks，而不是如何从节点到节点，但节点 – >步骤 – >节点

节点 – >步骤是函数步骤的主体 – >节点是其他函数的参数

再见:)希望我帮助