【递归与递推】新汉诺塔

题目描述

设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。
现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
移动时有如下要求：
·一次只能移一个盘；
·不允许把大盘移到小盘上面。

输入

第一行是状态中圆盘总数；
第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号；
第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。

输出

每行一步移动方案，格式为：move I from P to Q
最后一行输出最少的步数。

样例输入

6
3 1 2 3
2 4 5
1 6
0
6 1 2 3 4 5 6
0

样例输出

move 4 from B to C
move 1 from A to C
move 2 from A to B
move 1 from C to B
move 3 from A to C
move 1 from B to A
move 2 from B to C
move 1 from A to C
move 5 from B to A
move 1 from C to B
move 2 from C to A
move 1 from B to A
move 3 from C to B
move 1 from A to C
move 2 from A to B
move 1 from C to B
move 4 from C to A
move 1 from B to A
move 2 from B to C
move 1 from A to C
move 3 from B to A
move 1 from C to B
move 2 from C to A
move 1 from B to A
move 6 from C to B
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
move 2 from C to B
move 1 from A to B
move 4 from A to C
move 1 from B to C
move 2 from B to A
move 1 from C to A
move 3 from B to C
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 5 from A to B
move 1 from C to A
move 2 from C to B
move 1 from A to B
move 3 from C to A
move 1 from B to C
move 2 from B to A
move 1 from C to A
move 4 from C to B
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
move 2 from C to B
move 1 from A to B
56

解：显然该题是用递归解题。因为不允许把大圆盘放在小圆盘上，所以，可以考虑为优先移动大圆盘。假设一共有n个圆盘，那么就应当优先移动编号为n的圆盘至目标位置。那么编号n的圆盘就不会对其他小圆盘有干扰了。接下来就是将编号为n-1的圆盘移动至其目标位置。
为了之后编写函数方便，输入时可进行加工。可将“初始状态”和“目标状态”分为两个数组a和b进行记录。a[i]即表示i号的初始位置，b[i]则为目标位置。先按照题目的输入顺序输入，一旦输入i，则在a[i]中记录
行数并转化为柱子的，b[i]同理。为了节省存储空间，可用一个变量重复输入。
如上述分析，从最大的n开始调用。函数需两个参数，即为需移动的圆盘编号k和要将其移动的位置t。若k的初始位置已在t上，可直接return。若没有，则先将k-1至1移动到辅助柱子上，这时就要用到循环并在循环
中递归。循环完后，再将a[k]改为t(相当于进行移动)，并输出，再将移动次数加一。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n,cnt=0;                                 //全局变量cnt计次
 6 char a[46],b[46];                            //记录圆盘的初始和目标位置
 7 
 8 void move(int k,char t)
 9 {
10     if(a[k]==t)
11     {
12         return;
13     }
14     char h;                                 //辅助柱子
15     if((a[k]==65&&t==66)||(t==65&&a[k]==66))
16     {
17         h=67;
18     }
19     if((a[k]==65&&t==67)||(t==65&&a[k]==67))
20     {
21         h=66;
22     }
23     if((a[k]==67&&t==66)||(t==67&&a[k]==66))
24     {
25         h=65;
26     }
27     for(int i=k-1;i>=1;i--)
28     {
29         move(i,h);                         //递归求k-1号圆盘的移动操作
30     }
31     printf("move %d from %c to %c
",k,a[k],t);
32     a[k]=t;
33     cnt++;
34 }
35 
36 int main()
37 {
38     cin>>n;
39     int m,t;
40     for(int i=1;i<=3;i++)
41     {
42         cin>>m;
43         for(int j=1;j<=m;j++)              //记录每根柱子上的圆盘序号，并将圆盘的位置通过i转换的askll码表示
44         {
45             cin>>t;
46             a[t]=i+65-1;
47         }
48     }
49     for(int i=1;i<=3;i++)
50     {
51         cin>>m;
52         for(int j=1;j<=m;j++)
53         {
54             cin>>t;
55             b[t]=i+65-1;
56         }
57     }
58     for(int i=n;i>=1;i--)
59     {
60         move(i,b[i]);
61     }
62     cout<<cnt<<endl;
63 }