1207 汉诺塔ii.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1207 汉诺塔II
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
/*分治法问题。
可以理解为：首先将塔的上端i个盘子通过四个柱子移动到B柱子上，
再将剩下的N-i个盘子通过三个柱子移动到C柱子上。最后再将B柱上的i个盘子移动到C柱子上。
依照这个思路来推导出公式即可。
f[1]:=1;
f[2]:=f[1]+2;f[3]:=f[2]+2;------加俩个2
f[4]:=f[3]+4;f[5]:=f[4]+4;f[6]:=f[5]+4;-----加3个4
。。。。。。－－－加4个8
*/

#include <iostream>
#include <cstdio>
using namespace std;

int step[65];

int main()
{
    int t,n,i,j,now;

    t=1;now=1;step[0]=0;
    for(i=1;i<=11;i++)
    {
        for(j=0;j<i;j++)
        {
            if(now>64)
                break;
            step[now]=step[now-1]+t;
            now++;
        }
        t*=2;
    }

    while(scanf("%d",&n)==1)
    {
        cout<<step[n]<<endl;
    }
    return 0;
}