Pulpcode

捕获,搅碎,拼接,吞咽

0%

兔子生兔子

有一对兔子,从出生后第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];
}
}
}