题目描述
给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘；
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。
输入格式
输入为一个正整数n，表示在A柱上放有2n个圆盘。
输出格式
输出仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。
样例输入
1
样例输出
2
解题思路
依据本图可推出：移动的次数=(2^n)-1，n为圆盘数
本题是2n个圆盘，所以移动的次数2*((2^n)-1)=2^(n+1)-2
那么直接套公式得：
#include<stdio.h> #include<math.h> int main() { int n; scanf("%d",&n); int sum; sum=pow(2,n+1)-2; printf("%d",sum); return 0; }
对于本题而言，答案正确，但是当我们把n输出的大一些时，会出现溢出现象，先来看这篇文章，如何处理超大的数：用数组存放每一位数，用数组输出每一位数
代码核心部分
n表示2的n次幂 for(int i=0;i<n;i++) a[i]=0; //先把数组每位数初始化为0,n越大，数组中的0就越多，例如n=5，表示2^5次幂(32),但是这里会储存5位数 a[0]=1; //让数的最后一位为1,这样接下来的遍历(*2)才有意义 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) a[j]*=2; //每次遍历，数组中的每一位数都要乘以2 for(int j=0;j<n;j++) { if(a[j]>9) { a[j+1]++; //如果数组中的一位数超过了9，需要进位 a[j]=a[j]%10; //进位后自身取余 } /* 这里可以用4验算一下，4=2^2,n=2,使用for嵌套--- i=0时,a[0]=2,a[1]=0 i=1时,a[0]=4,a[1]=0,如果要输出04，那么就必须逆序输出 */ } } 用数组输出 for(int p=n-1;p>=0;p--) //由于在数组中存数时是从最后一位开始存的，所以要逆序输出 { if(a[p]>0) //数组中可能有很多位都没用上，值为0，这些0不能输出，找出第一个不是0的位置再输出 { for(int q=p;q>=0;q--) printf("%d",a[q]); break; } }
回到本题，代码易得
#include<stdio.h> int main() { int n; scanf("%d",&n); int a[10000]; for(int i=0;i<n;i++) a[i]=0; //先把数组每位数初始化为0 a[0]=1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) a[j]<<=1;//比起a[j]*=2;移位运算符效率更高 for(int j=0;j<n;j++) { if(a[j]>9) { a[j+1]++; //如果数组中的一位数超过了9，需要进位 a[j]=a[j]%10; //进位后自身取余 } } } a[0]-=1;//这里计算的是(2^n)-1的值 //if(n==0) printf("1"); //特判一下，如果n==0，2的0次方=1 //printf("\n");这里不用考虑这个情况了 //以上已经计算了(2^n)-1的值，现在要给他们每位数都×2,像11*2=以数组形式分别输出2和2 //直接把第一个循环复制下来,i<n,改为i=1即可,这里强调只循环1次 for(int i=0;i<1;i++) { for(int j=0;j<n;j++) a[j]<<=1;//比起a[j]*=2;移位运算符效率更高 for(int j=0;j<n;j++) { if(a[j]>9) { a[j+1]++; //如果数组中的一位数超过了9，需要进位 a[j]=a[j]%10; //进位后自身取余 } } } //以上2*((2^n)-1)已经计算完毕，接下来是输出 for(int p=n-1;p>=0;p--) //由于在数组中存数时是从最后一位开始存的，所以要逆序输出 { if(a[p]>0) { for(int q=p;q>=0;q--) printf("%d",a[q]); break; } } return 0; }
这样，就算2的150次幂也可以求解：
