汉诺塔问题

发表于

设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。

现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。

移动时有如下要求：

一次只能移一个盘；

不允许把大盘移到小盘上面。

汉诺塔问题是递归的一个很好的模型

思考并结合题意，本问题有如下性质

  1. 大的过了，小的才能过
  2. 6代表3根初始柱，3根中转柱，first[x]代表初始位置，6-(first[x]+y)便是中转柱，这个操作便是将小盘子都移开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
int n,last[55],first[55],ans=0,m,x;
const char ch[]={'0','A','B','C'};
void dfs(int x,int y){
    if(first[x]==y) return;
    for(int i=x-1;i>=1;i--) dfs(i,6-(first[x]+y));
    printf("move %d from %c to %c\n",x,ch[first[x]],ch[y]);
    first[x]=y;ans++;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=3;i++){
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),first[x]=i;
    }
    for(int i=1;i<=3;i++){
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),last[x]=i;
    }
    for(int i=n;i>=1;i--) dfs(i,last[i]);
    printf("%d",ans);
    return 0;
}