递归应用之汉诺塔

╰+攻爆jí腚メ 2022-07-13 12:11 197阅读 0赞

问题描述：

有一个梵塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上（如图）。

把这些个盘子从A座移到C座，中间可以借用B座但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘

子始终保持大盘在下，小盘在上。

描述简化：把A柱上的n个盘子移动到C柱，其中可以借用B柱。

![2011111320150185.gif][]

问题思路：

1.要把A上面的N个盘子移动到C上，而且移动过程中必须小上大下。那么我们最终有一个状态肯定是A上面只剩一个最大的盘子，B上面有N-1个盘子，而C上没有盘子。

2.我们把A上面的最大的盘子移动到C上，这样我们就完成了第一个从A到C的转移。此时A为0，B为N-1，C为1

3.这时问题变成了把B上面的N-1个盘子移动到C上面，与原题目要求把A上面的N个盘子移动到C上要求一致。也就构成了递归。

转化为函数思想：

doTowers(topN,A,B,C) 表示把topN个盘子从A移动到C

\* 第一步：doTowers(topN-1, A, C, B)把topN-1个盘子从A移动到B上

\* 第二步：把A上的最后一个盘子移动到C上  
\* 第三步：doTowers(topN-1, B, A, C)把topN-1个盘子从B移动到C上

代码实现：

public class TowersApp {
    	static int nDisks=3;
    	public static void doTowers(int topN,char A,char B,char C) {
    		if(topN==1) {
    			System.out.println("Disk 1 from "+A +" to "+C);
    		}
    		else {
    			doTowers(topN-1, A, C, B);
    			System.out.println("Disk"+topN+" from "+A +" to "+C);
    			doTowers(topN-1, B, A, C);
    		}
    	}
    	public static void main(String[] args) {
    		doTowers(nDisks, 'A', 'B', 'C');
    	}
    
    }

输出结果：

Disk 1 from A to C  
Disk2 from A to B  
Disk 1 from C to B  
Disk3 from A to C  
Disk 1 from B to A  
Disk2 from B to C  
Disk 1 from A to C  
解决实际问题时、不能太去关心实现的细节（因为递归的过程恰恰是我们实现的方法）就像这个问题，如在第一步就过多的纠结于如何把n-1个盘子移动到B上、那么你的思路就很难继续深入。只要看做是用函数实现就好，如果你能看出不管怎么移动，其实本质都一样的时候，那么就能较快的得到结果了。就像这个案例，要注意到我们做的关键几步都只是移动的顺序有改变，其中的规则没有改变。如果用函数表示的话，就只是参数调用的顺序有所不同了。在递归的运用中、不用关心每一步的具体实现 ，只要看做用一个函数表示就好。分析问题的时候，最好画出自己的推理过程，得到有效的状态图。

[2011111320150185.gif]: /images/20220713/3516ba375297456f8b5ce27ca85e765f.png