有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?
思考,这个题,如果仔细观察,不难发现是斐波那契数列,也就是从一月开始,兔子的个数是1,1,2,3,5,8....
.的形式增长的,所以我决定先写一个斐波那契函数,我使用递归的方式来写,非常简单:
1 2 3 4 5 6 7
| int fibo(int n) { if(n == 1||n ==2) return 1; else return fibo(n-1) + fibo(n-2); }
|
下面是整个程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<stdio.h> #include <conio.h>
int fibo(int n); main() { int i; for(int j = 1;j != 10; j++) { i = fibo(j); printf("%d月份的兔子数是:%d\n",j,i); } getch(); } int fibo(int n) { if(n == 1||n ==2) return 1; else return fibo(n-1) + fibo(n-2); }
|
更多的思考:
其实这种重复问题使用递归,会有很大的浪费,比如,计算fibo(8)=fibo(7)+fibo(6)
而fibo(7)的计算也会用到fibo(6),而这个fibo(6)每次又是通过递归重新计算的。
我们可以先做一个测试:
1 2 3 4 5 6 7 8 9 10
| int fibo(int n) { if(n == 1||n ==2) return 1; else { return fibo(n-1) + fibo(n-2); printf("fibo(%d)被调用了\n",n); } }
|
你调用一下fibo(10),就会发现,好多的函数被重复调用了。
所以,我们要想更好的办法避免这些浪费,这就用到了“动态规划”的思想:
int a[10];定义一个数组(这里为了说明问题,考虑十个月以内的)
这样,第一次调用后,把这个值存在数组中,(fibo(i)的值保存在a[i-1]中)
这样下一次,在使用这个值的时候就可以直接调用而不是递归了。
新的动态规划版斐波那契函数:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| int a[10];
int fibo(int n) { if(a[n-1] != 0) return a[n-1]; else { if(n == 1||n ==2) { a[n-1] = 1; return 1; } else { printf("fibo(%d)被调用了\n",n); a[n-1] = fibo(n-1) + fibo(n-2); return a[n-1]; } } }
|