HDU 1207

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1207

四柱汉诺塔问题

当 r = (sqrt(8*n+1)-1)/2 时，

存在 count = (n-(r*r-r+2)/2)*(int)pow(2,r)+1 ，此时所需的步骤最少。

 #include<stdio.h>

 #include<math.h>

 int main()

 {

     int n,r;

     long long int count;

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

     {

         r = (sqrt(*n+)-)/;

         count = (n-(r*r-r+)/)*(int)pow(,r)+;

         printf("%I64d\n",count);

     }

     return ;

 }

还有一种方法，模拟三柱汉诺塔问题

三柱汉诺塔的步骤是：

（1）把n-1个盘子移动到B柱上

（2）把第n个盘子移动到C柱上

（3）把n-1个盘子移动到C柱上

那么四柱汉诺塔的步骤为：

（1）把n-k个盘子移动到B柱上

（2）把k个盘子移动到C柱上

（3）把n-k个盘子移动到C柱上

一开始我以为k=2，所以得到的结果不是最小，那么应该用for循环从1到n都计算一遍找到能使结果最小的k值。

将k个盘子移动到C柱上的步骤就是三柱汉诺塔问题，题目已经给出最小步骤为2^k-1

而1和3步骤所需最小步数一样，那么Hanoi[n]=a[k]+2*a[n-k],a[k]=pow(2,k)-1。

注意该题的数据容易溢出，所以我定义数据类型为double

代码如下：

#include<stdio.h>

#include<math.h>

int main()

{

    int n;

    double a[],Hanoi[],k1,k2;

    int i,j;

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

        a[i] = pow(,i) - ;

    Hanoi[] = ;

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

    {

        k1=a[i];

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

        {

            k2 = a[j] + *Hanoi[i-j];

            if(k1 > k2)

                k1 = k2;

        }

        Hanoi[i] = k1;

    }

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

    {

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

    }

    return ;

}

Hanoi