首页 > 代码库 > sicily 1029. Rabbit
sicily 1029. Rabbit
Description
The rabbits have powerful reproduction ability. One pair of adult rabbits can give birth to one pair of kid rabbits every month. And after m months, the kid rabbits can become adult rabbits.
As we all know, when m=2, the sequence of the number of pairs of rabbits in each month is called Fibonacci sequence. But when m<>2, the problem seems not so simple. You job is to calculate after d months, how many pairs of the rabbits are there if there is exactly one pair of adult rabbits initially. You may assume that none of the rabbits dies in this period.Input
The input may have multiple test cases. In each test case, there is one line having two integers m(1<=m<=10), d(1<=d<=100), m is the number of months after which kid rabbits can become adult rabbits, and d is the number of months after which you should calculate the number of pairs of rabbits. The input will be terminated by m=d=0.
Output
You must print the number of pairs of rabbits after d months, one integer per line.
Sample Input
Copy sample input to clipboard
2 33 51 1000 0
Sample Output
591267650600228229401496703205376
分析：首先通过分析可以得到递推公式为 f(n) = f(n-1) + f(n - m)那么就是通过上面的递推式来求得 f(d) 的值。一般来说不用递归，因为递归在数值大的时候时间消耗会非常大，那么这里就用记忆法，其实就是用一个数组来保存结果。因为题目里面说明了 d <= 100，所以结果的个数可以用一个 100 的数组来保存。另外一个就是大整数计算，这里我用一个 string 来表示，虽然看起来有点烦但还是能理解的。
#include <iostream>#include <string>#include <algorithm>using namespace std;string add(string num1, string num2) { // 高精度加法 reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); string::iterator iter1 = num1.begin(); string::iterator iter2 = num2.begin(); string str = ""; int add = 0; for (; iter1 != num1.end(), iter2 != num2.end(); ++iter1, ++iter2) { int value = http://www.mamicode.com/(*iter1 - ‘0‘) + (*iter2 - ‘0‘) + add; str = (char)((value % 10) + ‘0‘) + str; add = value / 10; } string::iterator iter = (iter1 == num1.end() ? iter2 : iter1); string::iterator iter_end = (iter1 == num1.end() ? num2.end() : num1.end()); for (; iter != iter_end; ++iter) { int value = http://www.mamicode.com/(*iter - ‘0‘) + add; str = (char)((value % 10) + ‘0‘) + str; add = value / 10; } if (add != 0) str = (char)(add + ‘0‘) + str; return str;}string getResult(int m, int d) { // 递推兔子的总数 string result[103]; for (int i = 0; i <= d; i ++) { if (i <= m) { int value = http://www.mamicode.com/i + 1; char t[256]; sprintf(t, "%d", value); result[i] = string(t); } else result[i] = add(result[i - 1], result[i - m]); // 递推公式为 f(n) = f(n - 1) + f(n - m) } return result[d];}int main(int argc, char const *argv[]){ int m, d; while (cin >> m >> d && m != 0 && d != 0) { cout << getResult(m, d) << endl; } return 0;}
sicily 1029. Rabbit
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。