Contents

1. 1. 汉诺伊塔 2
2. 2. 题目：
3. 3. 分析：

汉诺伊塔 2

题目：

分析：

• 3个柱子时是最少移动2^N - 1次
• 把n个盘分成两部分看，第一部分是用四个柱子时的最优解的方法移到第4个柱子然后移到第3个柱子上-
• 第二部分在第一部分的下面是用3个柱子时的最优解方法
  移动到第三个柱子上

#include<stdio.h>
#include<math.h>
int main(){

    int i, j, n;
    long long ans[70]={0,1};                    //从1到64
    long double mins, tmp;
    for(i = 2; i <= 64; i++)                    //从总共2个圆盘开始
    {
        mins = 1e70;
        for(j = 1; j < i; j++)
        {
            tmp = 2 * ans[j] + pow(2.0, i-j) - 1; //2*ans[j]意思是用四个柱子时的最优
            if(tmp < mins)                      //解方法把第一部分移动到第4个柱子
                mins = tmp;                     //然后又移动到第3个柱子
        }
        ans[i] = mins;                          //建立四个柱子时的最优解
    }
    while(scanf("%d", &n) != EOF)
    {
        printf("%I64d\n", ans[n]);
    }
    return 0;
}