双塔问题 递推 高精度 题解

AC代码

#include<bits/stdc++.h>
using namespace std;
#define N 105
void setLen(int a[], int i)
{
	while(a[i] == 0 && i > 1)
		i--;
	a[0] = i;
} 
void Multiply(int a[], int b, int r[])//高精乘低精 r = a * b
{
    int c = 0, i;
    for(i = 1; i <= a[0]; ++i)
    {
        r[i] = a[i] * b + c;
        c = r[i] / 10;
        r[i] %= 10; 
    }
    while(c > 0)
    {
        r[i] = c % 10;
        c /= 10;
        i++;
    }
   	setLen(r, i);
}
void Add(int a[], int b)//高精加低精 a += b
{
    int c = b, i = 1;
    while(c > 0)
    {
    	a[i] += c;
    	c = a[i] / 10;
    	a[i] %= 10;
    	i++;
	}
	if(i > a[0])
    	setLen(a, i);
}
void showNum(int a[])
{
    for(int i = a[0]; i >= 1; --i)
        cout << a[i];
}
int main()
{
	int n, a[205][N] = {};//a[i]:2*i层汉诺塔从A移动到C的步数
	cin >> n;
	a[1][0] = 1, a[1][1] = 2;//a[1] = 2;
	for(int i = 2; i <= n; ++i)
	{
		Multiply(a[i-1], 2, a[i]);//a[i] = 2*a[i-1];
		Add(a[i], 2);//a[i] += 2
	}
	showNum(a[n]);
    return 0;
}

欢迎加入团队