1207 ACM 汉诺塔II 数学

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1207
中文题目，在原来三个柱子的情况下（汉诺塔一），增加了一个柱子，难度也增加了。
思路：
思考时尽量和汉诺塔一联系起来。
1 ，先看汉诺塔一的情况
只有一个盘子时，只需挪动一步；假如n个盘子要移动An步，则有n+1个盘子可以先通过An步把上面的n个盘子挪到第二个柱子上，再挪最大的盘子，最后把n个盘子挪到大的上面，总共2An+1步，则有A(n+1)=2An+1。
以上式子可推得An=2^n-1。
2，回过来看该題，该题多加了一根柱子，现在有四根柱子了，分别是a,b,c,d，计算将n个盘从第一根柱子a全部移到最后一根柱子d上所需的最少步数。

设F[n]为所求的最小步数，则有当n=1时，F[n]=1;当n=2时，F[n]=3;这里同经典汉诺塔一样，将移动盘子的任务分为三步：

一，将x(1<=x<=n)个盘从a柱依靠b,d柱移到c柱，这个过程需要步数设为F[x]（依靠两个柱子）;
二，将a柱上剩下的n-x个盘依靠b柱移到d柱（此时不能依靠c柱，c柱上的所有盘都比a柱上的盘小），移动方式相当于是一个汉诺塔1版，这个过程需要的步数为2^(n-x)-1（汉诺塔一）（依靠一个柱子）；
三，将c柱上的x个盘依靠a,b柱移到d柱上，这个过程同样需要的步数为F[x];

经过以上3步即可完成任务，总步数为F[n]=F[x]+2^(n-x)-1+F[x]=2*F[x]+2^(n-x)-1;题目中要求的是最少的步数，根据上式，x的不同取值，对于同一个n，也会得出不同的F[n]。因此答案转化为min{2*F[x]+2^(n-x)-1},其中1<=x<=n;用两个for循环遍历x的各个取值，记录最小值即可。
注意：
1，C++里面的幂函数pow
2,要用longlong或是（_int64 输出%I64d）

#include<stdio.h>

#include<cmath>  

int main()

{

    long long f[65],min;

    int i,j,n;

    f[1]=1;

    f[2]=3;

    for(i=3;i<65;i++)

    {

        min=0x7FFFFFFFFFFFFFFF;

        for(j=1;j<i;j++)

            if(2*f[j]+pow(2.0,i-j)-1<min)

                min=2*f[j]+pow(2.0,i-j)-1;

        f[i]=min;

    }

    while(scanf("%d",&n)!=EOF)

    {

        printf("%d\n",f[n]);

    }

}

巴特西

1207 ACM 汉诺塔II 数学

最新文章

热门文章