Hanoi双塔问题 （C语言代码）

解题思路:

先找规律，然后利用高精度算法

注意事项:

参考代码:

#include<stdio.h>

//根据规律，该问题的解是res=2*（2^n-1）=2^(n+1)-2 

int twopown(int n);//高精度计算2^n 

int res[200]={0};

int main()

{

int n,num,i;

int a[200]={0};//由于最后要减2，这里不得不计算一下高精度减法，所以定义了一个数组a[200],它只有a[0]=2,其他位都是0，用它当高精度减数 

a[0]=2;

scanf("%d",&n);

num=twopown(n+1);//计算 2^(n+1)，并得到这个大整数的总位数 

for(i=0;i<num;i++)//高精度减法，首先每一位对应简单相减 

{

res[i]=res[i]-a[i];

}

for(i=0;i<num;i++)//然后考虑退位 

{

if(res[i]<0)//如果这一位小于0 

{

res[i+1]=res[i+1]-1;//先向高位借位 

res[i]=res[i]+10;//借位后此位加10 

}

}

for(i=num-1;i>=0;i--)

{

printf("%d",res[i]);//倒叙输出（因为res[0]对应最低位） 

}

return 0;

}

int twopown(int n)//高精度计算2^n 

{

int i,j,num=1;//num用来计算最后结果大整数的位数 

res[0]=1;//初始化，因为要计算乘法，res[0]首先要置1 

for(i=0;i<n;i++)//i控制乘n次 

{

for(j=0;j<num;j++)//j控制此时有意义的位数的乘法 ，对有意义的位，都先简单乘2 

{

res[j]=res[j]*2;

}

for(j=0;j<num;j++)//处理大于10的位 

{

if(res[j]>=10)//如果某位大于10 

{

res[j+1]=res[j+1]+res[j]/10;//向高位进位 

res[j]=res[j]%10;//此位只留除10的余数 

}

}

if(res[j]>0)//如果这次乘二得到了新的有意义的位，则num加一 

num++;

}

return num;

}