Blog·Tanky WooABOUTRSS

HDOJ 2064 汉诺塔III

01 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

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

感觉这题算不错吧。 (在ambition大牛的指点下才发现哪错了,orz) 考虑了几点。

一个是找规律,另外一个就是大数的处理。

大家看看这个图。

怎么找规律。

假设f[n]表示把n层从1移到3的次数,则f[n] = f[n-1]*3+2

考虑为何,因为f[n-1]表示把n-1层从1移到3的次数,这时在底部再添一层时,首先1~n-1层要从1移到3,这就是f[n-1]次了,然后最后一层n从1移到2,为1次,1~n层肯定还得从3移到1(这样最后一层n才能在第3环的最后),这又是f[n-1]次了,最后第n层由2移到3,为1次,1~n-1层由1再到3是f[n-1]次。所以总共就是f[n] = f[n-1]*3+2次

另外,网上好多人写了这个代码:

// 注意这是错误的版本
#include 
#include 
using namespace std;

int main()
{
    int n;
    while(scanf("%d", &n;) != EOF)
    {
        printf("%I64d\n", __int64(pow(3.0, n)) -1);
    }
    return 0;
} 

大家测试就会发现在n=34和n=35时会和标准答案有出入,这是因为pow和double型都会精度丢失。 他们应该是很早做的。杭电的数据肯定很弱,发现BUG后改过来了。

正确的方法,用数组保存即可,注意用64为整型__int64保存。

 // Tanky Woo
// HDOJ 2064


#include 
#include 
using namespace std;

__int64 num[36];
int main()
{
    int n;
    num[0] = 1;
    num[1] = 2;
    for(int i=2; i<36; ++i)
        num[i] = num[i-1]*3+2;
    while(scanf("%d", &n;) != EOF)
        printf("%I64d\n", num[n]);
    return 0;
} 

当然,你测试就会发现只当n=34和35时会有标准有出入,所以你也可以这么写:

// Tanky Woo
#include 
#include 
using namespace std;

int main()
{
    int n;
    while(scanf("%d", &n;) != EOF)
    {
        if(n == 34)
            printf("16677181699666568\n");
        else if(n == 35)
            printf("50031545098999706\n");
        else
            printf("%I64d\n", __int64(pow(3.0, n)) -__int64(1));
    }
    return 0;
}