汉诺塔移动次数

描述

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

下面的问题就是：当Ri在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三根柱子上？

输入

包含多组数据，每个数据一行，是盘子的数目N(1<=N<=64)

输出

对于每组数据，输出一个数，到达目标需要的最少的移动数

样例输入

3

样例输出

7

#include<stdio.h>
#include<math.h>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==1) printf("1\n");
        else{
            printf("%0.lf\n",pow(2,n)-1);
        }
    }
    
    return 0;
}

心路历程：

在知道汉诺塔移动的规律为2ⁿ-1，我想都没想直接用pow函数直接秒杀，将上面的代码提交上去，被秒杀了，居然没过，该死的居然没注意到n最大为64

思路：

用高精度数组模拟

先定义整形数组A（存储2ⁿ的结果），将数组A第一个元素初始化为2（因为2¹为2） ①号为主循环，②号循环将数组A中的每一个元素*2，③号循环处理数组A中每一位*2过后可能产生进位

#include<stdio.h>
#include<string.h>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){  //至于要写scanf("%d",&n)!=EOF，是因为学校oj平台的原因
        if(n==1) printf("1\n");
        else{
            int A[100];
            memset(A,0,sizeof(A));
            A[0]=2;
            for(int i=2;i<=n;i++){   //①
                for(int p=0;p<100;p++){   //②
                    //if(A[p]==0) break; //这句是不能加的，比如2的10次方为1024 没遇到1就退出循环
                    A[p]*=2;
                }
                for(int q=0;q<100;q++)  //③
                {
                    if(A[q]==0) break;
                    else{
                        if(A[q]>9){
                            A[q+1]+=A[q]/10;
                            A[q]%=10;
                        }
                    }
                }
            }
            
            int j;
            for(j=99;j>=0 && A[j]==0;j--); //倒着遍历，直到遇到数组A中不为0的下标
            for(int i=j;i>=1;i--){  //倒着遍历去输出
                printf("%d",A[i]);  
            }
            printf("%d",A[0]-1);  //A[0]-1，直接这么写是因为2ⁿ的最后一位只能在2、4、6、8中反复出现，不会出现向前进位的可能
            printf("\n");
        }
    }
    return 0;
}

如果加if(A[p]==0) break; 就会出现如下状况