linux畅想

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

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

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

Output
输出移动m次后的状况．每组输出３行，第i行第１个数是第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方向移动。
现在我不用多说了，应该都发现规律了吧。自己好好琢磨。