PTA平台 7-12 兔子繁衍问题

7-12 兔子繁衍问题

一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，至少需要繁衍到第几个月时兔子总数才可以达到N对？

输入格式:

输入在一行中给出一个不超过10000的正整数N。

输出格式:

在一行中输出兔子总数达到N最少需要的月数。

样例">样例">样例">样例">样例">样例">样例">样例">样例">样例">输入样例:

30

输出样例:

9

通过审题

1.第一个月的兔子，第三个月起每个月生新兔子 之后每个月生新兔子

2.通过对上述问题枚举：

第一个月：R1 （R代表rabbit，1代表月份）

第二个月：R1

第三个月：R1, R13

第四个月：R1, R13, R14

第五个月：R1, R13, R14, R15, R135

第六个月：R1, R13, R14, R15, R16, R135, R136, R146

...

列举至此，可以发现R(1) = 1, R(2) = 1, R(3) = 2, R(4) = 3, R(5) = 5, R(6) = 8

得出递推式 R(n) = R(n - 1) + R(n - 2)

显然，这就是斐波那契数列

这里观察数据范围，N <= 10000 的正整数，使用常用递归方法会栈内存溢出

可以得出，在第21项时，斐波那契数列值大于10000

故针对此题，可以声明一个数组，保存数列1-21项的值

之后再和题目中的输入进行对比即可

Fibonacci：

 int i = 1;while (i <= 21){if (i == 1) {fib[i] = 1;}else if (i == 2) {fib[i] = 1;}else if (i >= 3) {fib[i] = fib[i-1] + fib[i-2];}i ++;}

完整的代码（c++）：

#includeusing namespace std;int main(void){int n;cin >> n;int fib[30];int i = 1;while (i <= 21){if (i == 1) fib[i] = 1;else if (i == 2) fib[i] = 1;else if (i >= 3) fib[i] = fib[i-1] + fib[i-2];i ++;}for(int j = 1; ; j++){if(fib[j] >= n) {cout << j;return 0;}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！