递归题目之斐波那契数列

云淡锋轻 2012-12-06

展开全文

原题：用递归求第10个数，它等于前2数之和，如{1，1，2，3，5}

得到递归式为f(n)=f(n-1)+f(n-2)，终止条件为f(0)=1, f(1)=1。求的数为f(9)。

1 #include <iostream>
2 using namespace std;
3
4 int f(int n)
5 {
6 if (n==1 || n==0)
7     {
8 return 1;
9     }
10 else
11     {
12 return f(n-2)+f(n-1);
13     }
14 }
15
16 int main()
17 {
18     cout<<f(9)<<endl;
19
20 return 0;
21 }
22

由于递归式比较简单，所以这个程序也就没有什么好说的。

但是关于斐波那契，还是有不少内容来探讨。

斐波那契数列最初出现是计算兔子的数目，所以又被称为“兔子数列”，所以看到农夫养牛等问题，还是可以联系上的。

关于斐波那契的讨论，主要集中在对其的优化，以及其扩展题目上，递归已经由只有一项在变，变成两项在变了。其扩展的题目，如何得到递归式，如何透过现象来将递归式写出来，才是真正的要点。

包括农夫养牛问题，爬楼梯问题，打靶问题等等，应该算起来都算是斐波那契问题的一些扩展。

【扩展】

1. 一个农夫养了一头牛，三年后，这头牛每年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……问农夫10年后有多少头牛?n年呢

老外喜欢养牛，在很多题目中都可以看到奶牛还是什么牛的身影。这道题目的网址为：

http://topic.csdn.net/u/20091001/15/40bf4993-8ed7-45cc-968f-97c524dae3c4.html?80749

而前段时间园子中有兄弟已经详细探讨了这个问题。

http://www.cnblogs.com/chinese-zmm/archive/2009/10/31/1593586.html

关于这个问题，其实一开始遇到是使用模拟的思路去想的，而且想得比较的糊涂，因为牛生下来之后，并不是马上就可以生小牛，是在三年后，每年生一头牛，那假设某一年，就有能生小牛的，还有一年生小牛的，还有两年生小牛的，然后就自己把自己绕住了。

但是，其实没有这么复杂，就是将其分为能生小牛的和不能生小牛的。

从而得到：

今年的牛的数目=去年的牛的数目+三年前牛的数目

也就是f(n)=f(n-1)+f(n-3)

这里

f(n-2) 第一年

f(n-1) 第二年

f(n) 第三年

看了一下题目，应该是三年后，那就应该是n-3。

代码如下：

1 #include <iostream>
2 using namespace std;
3
4 int Fibonacci(int n)
5 {
6 if (n==1 || n==2 || n==3)
7     {
8 return 1;
9     }
10 return Fibonacci(n-1)+Fibonacci(n-3);
11 }
12
13 int main()
14 {
15     cout<<Fibonacci(10+1)<<endl;
16 }

这里输入参数为n+1，是因为是n年后的数目，所以需要加1。

这道题目，也可以使用数组将运算的结果保存下来，然后直接进行计算，这就是常说的动态规划。

代码如下：

1 int Fibonacci2(int n)
2 {
3 int *num=new int[n];
4     num[0]=num[1]=num[2]=1;
5 for (int i=3;i<n;i++)
6     {
7         num[i]=num[i-1]+num[i-3];
8     }
9 int ret=num[n-1];
10     delete []num;
11 return ret;
12 }
13
14 int main()
15 {
16     cout<<Fibonacci2(10+1)<<endl;
17 }

上面的程序使用了n个的数组来存，但是其实并不需要，只需要3个数参与运算即可。

而园子中的兄弟在这个基础上又做了两个扩展，一个是将特殊一般化，也就是不单单是3年，如果是m年呢？

如果m年则得到

f(n)=f(n-1)+f(n-m)

同时这里的牛只有生没有死，那加上到了一定的时间牛就会死呢？

假设牛到了第8年就挂了。

那就可以得到

f(n)=f(n-1)+f(n-3)-f(n-8)

2. 打靶问题：一个人打靶，成绩为0～10之间的任意一个整数。包括0和10。一共打了10次总共得分89分。问得分的可能性。

可以得到比较明显的一个递归式，f(n)=x+f(n-1)，而x的取值为0-10之间的任意一个整数。

所以我们需要去做一个变化的x，其实也就是一个循环来得到。

因为要求的结果为得分的可能性，所以我们要将结果保存起来，然后每遇到结果为89的，则将保存的结果打印出来，然后统计+1，所以我们需要一个10个数的数组来做这件事情。

递归终止条件是当n为0时终止，此时来判断分值并进行相应的操作。

1 #include <iostream>
2 using namespace std;
3
4 int countresult;
5 int store[10];
6
7
8 void getscore(int sum, int n)
9 {
10 if(sum<0 || sum+(n+1)*10<89 || sum>89)
11 return;
12 if(n==0)
13     {
14 //check the number
15 if(sum==89)
16         {
17 for(int i=0;i<10;i++)
18                 cout<<store[i]<<" ";
19             cout<<endl;
20             countresult++;
21         }
22 return;
23     }
24 for(int i=0;i<=10;i++)
25     {
26         store[10-n]=i;
27         getscore(sum+i,n-1);
28     }
29 }
30
31 int main()
32 {
33     getscore(0,10);
34     cout<<"总数"<<countresult<<endl;
35 return 0;
36 }

注意上面的代码，其实上面还是应用了递归中常使用的一种做法--剪枝。

上面的代码并不太好，比较好的是下面的代码，但是两种方法作出的值是一样的。

1 #include <iostream>
2 using namespace std;
3
4 int sum;
5 int store[10];
6
7 void Output()
8 {
9 for(int i = 9; i>=0; --i)
10     {
11        cout<<store[i]<<" ";
12     }
13    cout<<endl;
14 ++sum;
15 }
16
17 void Cumput(int score, int num)
18 {
19 if(score < 0 || score > (num+1)*10 ) //次数num为0～9
20 return;
21 if(num == 0)
22    {
23        store[num] = score;
24        Output();
25 return;
26    }
27 for(int i = 0; i <= 10; ++i)
28    {
29        store[num] = i;
30        Cumput(score - i, num - 1);
31    }
32 }
33
34 int main(int argc, char* argv[])
35 {
36     Cumput(89, 9);
37     cout<<"总数:"<<sum<<endl;
38 return 0;
39 }