首页 > ACM题库 > HDU-杭电 > hdu 2175 汉诺塔IX[解题报告]C++
2013
12-30

hdu 2175 汉诺塔IX[解题报告]C++

汉诺塔IX

问题描述 :

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次移动的是那一个盘子.

输入:

每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1.n=m=0退出

输出:

每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1.n=m=0退出

样例输入:

63 1
63 2
0 0

样例输出:

1
2


找规律就好了。

会发现对称性。。。。

用的找规律代码:

#include <iostream>
#include<cmath>
 using namespace std;
int main()
{
    unsigned long long a[65],m,t;
    int n;
    a[1]=1;
    for(int i=2;i<64;i++)
        a[i]=2*a[i-1]+1;
    while(scanf("%d%I64d",&n,&m),n||m)
    {
        t=a[n]+1;
        for(int i=n;i>=1;i--)
        {
            t/=2;
            if(t==m)
            {
                    printf("%d\n",i);
                    break;
            }
            if(m>t)        m=m-t;
            else m=t-m;
        }
    }
    return 0;
}

 


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。