四柱hanoi最少需要多少次移动

  使用动态规划
  ============
  一个4柱的hanoi问题可以分解为两个4柱的hanoi问题和一个3柱的hanoi问题：
  把k个（k<i）盘子移到其他柱子，然后把i-k个盘子移到目的柱子，
  再把k个柱子移到目的柱子上。
  选择一个k（在1~i-1之间），使得移动次数最少。
           i-1
  F4(i) =  min { F4(k) * 2 + F3(i-k) }
           k=1
  其中Fn表示n柱的hanoi问题的最少移动次数。
  我们知道 F3(i) = 2^i-1
  得到算法 #1 。

  但32位的long只能表示到i=32的情况。
  实际上，当i增大时，d(F3) 远大于 d(F4)
  F4的表示范围答应i取得更大。该i可以求出，是358
  该算法可以通过一定的修改，使得i的取值更大
  当 d(F3) > 2 * d(F4)时，可以考虑，k再增大F4(i)的值不再变小。
  即有：  
    F4(k) * 2 + F3(i-k) < F4(k') * 2 + F3(i-k')     (k'>k or k'<k)
  该函数的k点位置是一个最小值，且k向两侧时单调递增。
  如过从F3值小的一侧进行比较，可以在F3的值溢出（F3(i)的参数i>32时F3溢出）前找到最小值。
  改进的算法 #2 使用F4new。

  另一种方法
  ==========
  假如你仔细观察F4序列，可以发现一条规律：
  每个数字都是前一个数字加上2^p，而2^p将连续出现p+1次，然后p=p+1。

  令F4(0)=0，则
  F4(1)=F4(0)+2^0=1
  F4(2)=F4(1)+2^1=3
  F4(3)=F4(2)+2^1=5
  F4(4)=F4(3)+2^2=9
  F4(5)=F4(4)+2^2=13
  F4(6)=F4(5)+2^2=17
  F4(7)=F4(6)+2^3=25
  ...
  至少在我能计算的范围内没有反例。

  那么，这是怎么回事呢？
  原因是在F3，相邻的F3本身就是相差2^i的，
  而当选择k时，又需要选一个d( F3 )小于2 * d( F4 )的最小k值。
  随着i的增大，2 * d( F4 )也增大，那么d( F3 )也可以适当的增大，
  但仍然满足该条件。而d( F3 )每次增大都是比前次多一倍，
  所以表现为上面的p=p+1;
  但我仍然不清楚连续出现p+1次（而不是其他数量）的原因。
  不过好在根据现在已知的规则可以计算了：
     1
    2 2
   4 4 4
  8 8 8 8
  ...
  4柱hanoi的问题转化为一个求上面的三角的前i个数之和的问题。
  这个问题还是比较方便的：
  最简单的莫过于

  sum=0;
  for(p=0;i;p++)
    for(t=0;i && t<=p;t++,i--)
      sum+=1<<p;

  了吧？不过不要忘了，sum应该是一个unsigned long，
  并且1<<p处也要转化类型。

  这里的算法 #3 就是了。
*/
#include <stdio.h>
#include <math.h>
unsigned long F4[33],F3[33],F4new[400];

int main()
{
 int i,k,maxi;
 unsigned long min,tmp;
 // 初始化F3
 F3[1]=1;
 for(i=2;i<33;i++)
  F3[i]=F3[i-1]*2+1;

 // #1 算法
 F4[1]=1;
 for(i=2;i<33;i++)
 {
  min=F4[1]*2+F3[i-1];
  for(k=2;k<i;k++)
  {
   tmp=F4[k]*2+F3[i-k];
   if(min>tmp)
    min=tmp;
  }
  F4[i]=min;
 }

 // #2 算法
 F4new[0]=0;
 F4new[1]=1;
 for(i=2;i<400;i++)
 {
  min=F4new[i-1]*2+F3[1];
  for(k=i-2;k;k--)// 反向寻找。
  {
   tmp=F4new[k]*2+F3[i-k];
   if(min>tmp)
    min=tmp;
   else break; //找到最小值，跳出
  }
  F4new[i]=min;
  if(F4new[i]<F4new[i-1])break;
 }
 maxi=i;

 while(1)
 {
  printf("How many disks? 1 to 32. [exit on 0]:");
  scanf("%d",&i);
  if(i==0)break;
  if(i<1)printf("Positive Number please!\n");
  else if(i<=32)printf("#1: %lu\t",F4[i]);
  if(i<maxi)printf("#2: %lu steps needed.\n",F4new[i]);
  else printf("too large!.F4new[%d] is over unsigned long!\n",maxi);

  // #3 算法
  unsigned long sum=0L;
  for(int p=0;i;p++)
   for(int t=0;i && t<=p;t++,i--)
    sum+=(unsigned long)1<<p;
  printf("#3: %lu\n",sum);

 }
 return 0;
}