递归基础_汉诺塔问题_经典的多状态问题_整体法/分两个函数互相递归

题目就不多说了，总之就是利用仨柱子，A/B/C，把A柱子上的一堆塔移到C上

这题之前老想不通，主要难点——

它实在是有很多个不同情况，三个柱子，状态太多，多而且杂
怎么表示它的当前状态, 怎么设置
每个状态下的转移方程要是什么，
怎么用已经设好的状态表示

不过，塔，其实本质上就和—栈—差不多，设置三个栈模拟，利用已有的状态转移方式，就可以解出这个移动过程，

这也是这题最经典的地方，柱子表示了栈结构的特性，转移过程就像栈的进出

关键是这个过程是什么—分别对递归最终点是什么，

目标问题——当前最底层 n 从某一个柱子移到C——P（n）+ P（n-1）

n=1；

1 ：A— C；

n=2；

1 ：A—B
2 ：A—C //第2层成功转移
1 ：B—C//第1层成功转移

n=3；

1：A—C
2 ：A—B
1 ：C—B//前2层全部转移到B-中转站
3 ：A—C//第3层成功转移
1 ：B—A
2 ：B—C//第2层成功转移
1 ：A—C//第1层成功转移

此时可以发现，当第3层转移成功的时候，下一步操作就是将第2层（n-1）转移过来——即：重复n=2 的过程，直到第1层

另外有一个大前提在于，如果能把第n层从A转移到C，此时必为，已经将第n-1层以上的所有塔转移到了B中，然后才能实现 n ：A—C；

把最底层n层A转移到C设置成一个关键节点，

以这个节点往前看：

要实现将n-1层以上的所有塔移到B，必须实现n-1：C—B ；n-2层塔移到C，以此类推需要实现n-3：移到B

。。。

以这个节点往后看：

对于能把第n-1层转移到C，必为已经将第n-2层以上的所有塔转移到了A中，然后才有 n -1 B—C；

对于第n-2层的转移，必为已经将n-3层以上的所有塔转移到了B中，然后才有 n A—C；

。。。

那所有的移动搜可以看成是2个汉诺塔的变形，最底层第n层看成第3个，第一层到第n-1层看成整体第2个

用整体看，当前状态，可以视为，两种运动

1. 将前n-1从A移到中转站B

2.将第座n从A移到目标C

3.将前n-1再从B移回来；

重复上面的操作直到，前n-1 移回来的时候恰好是第1项

移动单个的设置为函数 move（）

移动一整叠的视为函数 f（）

以下为代码，：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <map>
 7 #include <algorithm>
 8 typedef long long ll;
 9 using namespace std;
10 int n;
11 int step=0;
12 void move(char a,int i,char b) {
13     cout<<"step "<<++step<<":"<<i<<" From "<<a<<" To "<<b<<"
";
14 }
15 
16 //step 1: 1 From A To B
17 void f(int n,char x1,char x2,char x3) {//n层x1->x3
18     if(n==1) {
19         //无论是第几层整体移动,
20         //最后一块一定是第1块被移到某处
21         move(x1,n,x3);
22         return ;
23     }
24     f(n-1,x1,x3,x2);//先把前n-1:A-B
25     move(x1,n,x3);//移动最底层n:A-C
26     f(n-1,x2,x1,x3);//再把前n-1,B-C移回来
27 }
28 
29 
30 
31 
32 int main() {
33     cin>>n;//最深不会超过n
34     f(n,'A','B','C');
35 
36 }

View Code

除了使用递归来实现,汉诺塔还可以使用迭代来实现,但是迭代的难度在于它不使用"整体"思想;

因此精确到每一步的过程非常复杂

链接参考: https://blog.csdn.net/luobo140716/article/details/51489484

中间还有点问题，(待续）

老实一点，可爱多了