求解一道题递推高精度

Question

题目描述

兔子有很强的生育能力，1对成年兔子可以每月生出1对幼年兔子。并且m个月后，幼年兔子成长为成年兔子。

当m=2时，每月兔子的对数是一个Fibonacci序列。不过在m<>2时候问题就不是那么简单了。如果一开始只有1对成年兔子，你的任务是计算d个月后有多少对兔子。你可以假设这期间没有兔子死去。

输入

包含多个测试用例，每个测试用例在一行上是两个整数m(1<=m<=10), d(1<=d<=100)。其中m指的是幼年兔子成长为成年兔子需要m个月，d指的是你需要计算的是d个月后兔子的对数。当m=d=0时表示输入结束。

输出

打印d个月后总共有多少对兔子，每个结果占一行

样例输入

2 3

3 5

1 100

0 0

样例输出

5

9

Answer 1

#include<iostream>
#include<string>
using namespace std;
int m,d;
 
string clear(string a)//清零
{
    if(a.empty())a="0";
    while(a[0]=='0')a.erase(0,1);
    if(a.empty())
        a="0";
    return a;
 
}
 
string add(string a,string b)//相加
{
    int i;
    while(a.size()<b.size())
        a="0"+a;
    while(b.size()<a.size()
        )b="0"+b;
 
    a="0"+a;
    b="0"+b;
    for(i=a.size()-1;i>0;i--)
    {
        a[i]+=b[i]-'0';
        if(a[i]>'9')
        {
            a[i]-=10;
            a[i-1]++;
        }
    }
    
    a=clear(a);
    return a;
}
 
int main()
{
    int n,index;
    string rabbits[102];
    while(scanf("%d %d",&m,&d)!=EOF)
    {
        if(m==0&&d==0)
            break;
        rabbits[0]="1";
        for(n=1;n<=d;n++)
        {
            if(n-m<0) index=0;
            else index=n-m;
            rabbits[n]=add(rabbits[n-1],rabbits[index]);
 
        }
 
        cout<<rabbits[d]<<endl;
        
 
    }
    return 0;
}