递归理解-汉诺塔问题
2018-12-05 21:48:15 # 算法，递归

汉诺塔问题的求解可以巧妙利用递归思想

以下摘自知乎上我认为阐述得很清除回答：

要用程序来解决这个问题，我们先定义一个移动函数：move（移动数，开始柱，中转柱，目标柱），
例如 move（2，A，B，C） 表示将2个盘子从A柱（开始柱）借助B柱（中转柱）移动到C柱（目标柱）。
关于开始柱，中转柱，目标柱这三个概念可以用移动过程中的某个状态来理解，

看下面一张图应该就能明白：
有三种状态的柱子，开始柱，中间柱，目标住，开始柱指的是开始状态时存放所有盘子的柱子，中转柱指的是中间状态时暂时存放n-1个（三层就是3-1个）盘子的柱子，
目标柱指的是盘子最终要移动到的柱子。这里需要注意，开始柱，中转柱，目标柱并不是一成不变的，而是会根据层次的不同而改变。（如果这里暂时不能理解的话，先读下去，再回头你就能明白了）。

接着我们分情况讨论一下盘子的移动：

情况一

当盘子只有1个（调用 move（1，A，B，C））当盘子只有一个的时候，

  • 只要直接将盘子从开始柱移动到目标柱就可以了，并没有中间状态（即不用借助中转柱），在move方法中可以用一句话表示该移动动作 print（’A—>C’）;

情况二

当盘子有2个（调用 move（2，A，B，C））这个情况分三个步骤进行：

  • step1. 把除了最大的盘子之外的盘子从A移到BA—>B (开始柱—>中转柱) 【相当于调用 move（1，A，C，B）】
  • step2. 把最大的盘子从A移到CA—>C (开始柱—>目标柱) 【相当于调用 move（1，A，B，C）】
  • step3. 把除了最大的盘子之外的盘子从B移到CB—>C (中转柱—>目标柱) 【相当于调用 move（1，B，A，C）】我想对于以上两个情况大家应该是没有什么疑问的，是可以确定的。

然后我们来看三层的情况

情况三

当盘子有3个（调用 move（3，A，B，C））这个情况同样分三步进行：

  • step1. 把除了最大的盘子之外的盘子从A移到B（注意对于这个步骤来说此时A为开始柱，C为中转柱，B为目标柱，这样才能完成把最上面的2个盘子从A—>B的任务）A—>C (开始柱—>中转柱) 【相当于调用 move（1，A，B，C）】A—>B (开始柱—>目标柱) 【相当于调用 move（1，A，C，B）】C—>B (中转柱—>目标柱) 【相当于调用 move（1，C，A，B）】
  • step2. 把最大的盘子从A移到C（对于这个步骤来说此时A为开始柱，B为中转柱，C为目标柱，这样才能把最大的盘子从A—>C）A—>C (开始柱—>目标柱) 【相当于调用 move（1，A，B，C），即直接执行 print（’A—>C’）】
  • step3. 把除了最大的盘子之外的盘子从B移到C（注意对于这个步骤来说此时B为开始柱，A为中转柱，C为目标柱，这样才能完成把处于step2中的中转柱的2个盘子从B—>C的任务）B —> A (开始柱—>中转柱) 【相当于调用 move（1，B，C，A）】B —> C (开始柱—>目标柱) 【相当于调用 move（1，B，A，C）】A —> C (中转柱—>目标柱) 【相当于调用 move（1，A，B，C）】

情况三的描述可能一下子不是那么好理解，但是大家应该能发现情况三的step1和step3的形式和整整个情况二的形式很像吧？而且要注意到分析的层次不相同时，开始柱，中转柱，目标柱是不一样的。

对于step1来说中转柱是C，对于step3来说中转柱是A，对于整个情况三来说中转柱是B。

前面我们已经确定了情况二调用的函数是 move（2，A，B，C），其等价于A—>B A—>CB—>C这三步，然情况三的step1是A—>C A—>B C—>B 这三步，跟情况二的形式是一样的，根据前面情况二的转化，那这三步就可以转化成函数 move（2，A，C，B)情况三的step3同理，做转化就成了函数 move（2，B，A，C）
而情况三的step2可以直接用一句 print（’A—>C’） 来代替 move（1，A，B，C）所以整个情况三就可以这样来表示：

  1. move（2，A，C，B) //step1.
  2. 把除了最大的盘子之外的盘子从A移到Bprint（’A—>C’） //step2.
  3. 把最大的盘子从A移到Cmove（2，B，A，C） //step3.
  4. 把除了最大的盘子之外的盘子从B移到C我们又知道情况三调用的函数是 move（3，A，B，C），

所以以上三行代码其实就等价于函数 move（3，A，B，C）。

来到这里应该就可以发现一点端倪了，情况四（4层）调用的函数是 move（4，A，B，C），

  1. 其用伪代码表示就是move（3，A，C，B) //step1.
  2. 把除了最大的盘子之外的盘子从A移到Bprint（’A—>C’） //step2.
  3. 把最大的盘子从A移到Cmove（3，B，A，C） //step3.
  4. 把除了最大的盘子之外的盘子从B移到C

对此有怀疑的小伙伴可以自己写出情况四的每步具体步骤然后再做转化，限于篇幅这里不再列出。

结论

那其实可以总结出：对于n（n>1）层汉诺塔，调用函数 move（n，A，B，C）来递归解决该问题，该函数执行的是

  1. move（n-1，A，C，B) //step1.

  2. 把除了最大的盘子之外的盘子从A移到Bprint（’A—>C’） //step2.

  3. 把最大的盘子从A移到Cmove（n-1，B，A，C） //step3.

  4. 把除了最大的盘子之外的盘子从B移到C

代码

然后有了以上的理解之后，我们就可以尝试写出解决该问题的代码了，Python实现：

1
2
3
4
5
6
7
def move(n,A,B,C):
    if n==1:             # 1个盘子，直接打印出移动动作
        print(A,'--->',C)
    else:                # n > 1时，用抽象出的3步来移动
        move（n-1，A，C，B) #step1.  把除了最大的盘子之外的盘子从A移到B
        print(A,'--->',C)  #step2.  把最大的盘子从A移到C
        move（n-1，B，A，C）#step3.  把除了最大的盘子之外的盘子从B移到C

so，读到这里，我大胆猜测大部分人心里应该明白得七七八八了

这里给出Java代码的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Hanoi {
	
	public static int move(int n,char A,char B,char C) {
		// 如果是移动过一个盘子
		if(n == 1) {
			System.out.println(A+"-->"+C);
			return 1;
		}else {
			// 一个以上的盘子
			int r1 = move(n-1,A,C,B);
			System.out.println(A+"-->"+C);
			int r2 = move(n-1,B,A,C);
			return r1+r2+1;
		}
	}
	
	
	public static void main(String[] args) {
		int count = 6;
		int result = Hanoi.move(count, 'A', 'B','C');
		System.out.println("total numbers of moves:"+result);
	}
}
上一页
2018-12-05 21:48:15 # 算法，递归
下一页