OJ——1917(rabbits)"/>
岭师OJ——1917(rabbits)
1917: Rabbits
题目描述
兔子有很强的生育能力,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 1267650600228229401496703205376
#include<iostream> using namespace std; #include<string> int m,d; string f[102];string clean(string a) {while(a[0]=='0'){if(a.length()==1) break;else a.erase(0,1);}return a; }string adds(string a,string b) {string str;int len1=a.length();int len2=b.length();if(len1>len2){for(int i=1;i<=len1-len2;i++){b="0"+b; }}else{for(int i=1;i<=len2-len1;i++){a="0"+a;}}len1=a.length();int cf=0,temp;for(int i=len1-1;i>=0;i--){temp=a[i]-'0'+b[i]-'0'+cf;cf=temp/10;temp%=10;str=char(temp+'0')+str;}if(cf!=0) str=char(cf+'0')+str;return clean(str); }string rabbits(int n) {int index;if(n-m<0) index=0;else index=n-m;if(f[n].empty())f[n]=adds(rabbits(n-1),rabbits(index));return f[n]; }int main() {int i,index;f[0]="1";while(cin>>m>>d){if(m==0&&d==0) break;for(i=1;i<102;i++)f[i].clear();cout<<rabbits(d)<<endl;}return 0; }
更多推荐
岭师OJ——1917(rabbits)
发布评论