Hanoi双塔问题（并解决n非常大的情况）-题解（C语言代码）

解题思路:

注意事项:

参考代码:

/********************************************/

                /*规律算法：找规律易知，汉诺塔的转移次数为2的n次方减1

                //双汉诺塔为单汉诺塔的两倍，即为2的n+1次方减2

                由于幂指数成爆炸增长，long long类型也存储不下，应用大数阶乘的算法

/********************************************/

#include <stdio.h>

int arr[10000];     //存储大数

int finish(int n);   //处理2的n+1次幂

/********************************************/

int main ()

{

int n;

scanf ("%d",&n);

    n=finish(n);

    for (int i=n-1;i>=0;i--)

    printf ("%d",arr[i]);

return 0;

}

/********************************************/

int finish(int n)

{

arr[0]=1;

int k=1;

int j;

for (int i=0;i<n+1;i++)   //计算2的n+1次幂

{

for ( j=0;j<k;j++)            //每一位都乘2

            arr[j]=arr[j]*2;

        for ( j=0;j<k;j++)    //进位

if(arr[j]>=10) 

{

arr[j+1]+=arr[j]/10;

arr[j]=arr[j]%10;

}

if(arr[j]>0)                      //判断最高位

{

    while (arr[j]>=10)

    {

    arr[j+1]+=arr[j]/10;

arr[j]=arr[j]%10;

}

k=j+1;

        }

}

                    //减2,因为易知2的n次幂，个位只可能为2，4，6，8

    arr[0]-=2;

return k;

}