假设一对兔子的成熟期是一个月,即一个月可长成成兔,那么,如果每对成兔每个月都生一对小兔,一对新生的小兔从第二个月起就开始生兔子,试问从一对兔子开始繁殖,以后每个月会有多少对兔子?
斐波那契数列模型
本题考点:动态规划
状态表示:
f[i]表示在i月的时候有多少对兔子(包括成熟的不成熟的)
状态计算:
f[i] = f[i - 1] + f[i - 2]
; f[i - 1]
表示i-1
个月兔子对的数量,f[i - 2]
表示i-2
个月兔子对的数量;
因为第i-2
月的兔子对数量到这月已经成为成熟兔子对,并且每个成熟的兔子对都可以生出一对小兔
#include <stdio.h>
#include <string.h>
#define N 100
long long int f[N];
int main() {
memset(f, 0, sizeof(f));
f[0] = 1;
f[1] = 1;
f[2] = 2;
int i = 0;
for (i = 3; i < N; i++) {
f[i] = f[i - 1] + f[i - 2];
}
for (i = 0; i < N; i++) {
printf("%d's month: %lld\n", i, f[i]);
}
return 0;
}