hdu 2184 汉诺塔VIII 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=2184

Problem Description
1,2,…,n表示n个盘子.数字大盘子就大.n个盘子放在第1根柱子上.大盘不能放在小盘上.在第1根柱子上的盘子是a[1],a[2],…,a[n]. a[1]=n,a[2]=n-1,…,a[n]=1.即a[1]是最下面的盘子.把n个盘子移动到第3根柱子.每次只能移动1个盘子,且大盘不能放在小盘上.问移动m次后的状况.

Input
第1行是整数T,表示有T组数据,下面有T行
每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1

Output
输出移动m次后的状况.每组输出3行,第i行第1个数是第i根柱子上的盘子数,然后是盘子的号数.

Sample Input
3
3 2
4 5
39 183251937942

Sample Output
1 3
1 2
1 1
2 4 1
1 3
1 2
13 39 36 33 30 27 24 21 18 15 12 9 4 1
12 38 35 32 29 26 23 20 17 14 11 8 5
14 37 34 31 28 25 22 19 16 13 10 7 6 3 2


代码

#include<stdio.h>
int main()
{
    unsigned __int64 m,a[64];
    int n,t,i,j,row[3][66];
    int *o,*p,*q,*tmp;
    for(a[0]=0,i=1;i<=63;i++)
        a[i]=a[i-1]*2+1;
    scanf("%d",&t);
    while(t--){
        scanf("%d%I64u",&n,&m);
        o=row[0];
        p=row[1];
        q=row[2];
        *o=*p=*q=1;
        while(n--){
            if(m<=a[n]){
                *(o+*o)=n+1;
                *o=*o+1;
                tmp=p;
                p=q;
                q=tmp;
            }
            else{
                *(q+*q)=n+1;
                *q=*q+1;
                tmp=o;
                o=p;
                p=tmp;
                m-=a[n]+1;
            }
        }
        for(i=0;i<3;i++){
            printf("%d",row[i][0]-1);
            for(j=1;j<row[i][0];j++)
                printf(" %d",row[i][j]);
            puts("");
        }
    }
    return 0;
}

分析
题目应该都看得懂,我就直接根据代码来分析了。
定义数组a,其中a[i]表示完成一次i层汉诺塔移动的次数。
指针o,p,q分别表示三个位置。
起始状态为n层都在o上,要往q方向移动。
然后分成两种情况:
1、
m<=a[n-1];
此时,第n层没机会移动,那么就相当于o上的n-1层往p上移动。
使其状态和起始状态一致,我们要交换p和q。
2、
m>a[n-1];
此时,先进行到下面状态,上面n-1层移动到p位置,第n层移动到q位置,消耗了a[n-1]+1次移动。
接下来就变成p上的n-1层往q上移动,只要交换o,p,令m=m-a[n-1]-1即可。

通过上述操作,都可以得到第n层的位置,并且问题变成n-1层都在o上,要往q方向移动。
现在我不用多说了,应该都发现规律了吧。自己好好琢磨。

发表评论?

5 条评论。

  1. 杭电 汉诺塔问题总结 - 编程 - 开发者 - pingback on 2013 年 8 月 17 日 在 上午 8:51

发表评论

Trackbacks and Pingbacks: