遞推演算法

一、遞推演算法簡介

一般是兩步：

1、根據題目條件推出遞推公式

2、根據遞推公式編寫代碼求解（一般可以寫成普通迴圈和遞歸）

二、實例

2.1 斐波拉契數列

斐波拉契數列，1 1 2 3 5 8 13 21 34......，寫出第n項。

（1）遞推公式

f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;

（2）代碼

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int Fibonacci(int n);
 5 int Fibonacci_Recursion(int n);
 6 
 7 
 8 /*
 9     非遞歸解法： 
10     和輾轉相除法的非遞歸解法好像
11     輾轉相除法是while迴圈以及中間是百分號
12     這裡是for迴圈以及中間是加號（f3=f2+f1）
13     for迴圈是知道迴圈次數的迴圈，while迴圈是單一限制條件的迴圈 
14 */ 
15 int Fibonacci(int n){
16     int f1=1;
17     int f2=1;
18     int f3;
19     for(int i=3;i<=n;i++){
20         f3=f2+f1;
21         f1=f2;
22         f2=f3;
23     }
24     return f3;
25 }
26 
27 /*
28     遞歸解法： 
29     本題的遞推條件為： f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;
30     遞推條件的限制條件 f(1)=1,f(2)=1是遞歸的限制條件
31     遞推條件的公式是遞歸的主體部分
32     這樣來想遞歸是不是特別簡單
33     
34     遞歸和非遞歸的區別：
35     這裡的非遞歸是從前往後推從而得到結論的，例如通過f(1)和f(2)得f(3)， 通過f(2)和f(3)得f(4)...
36     遞歸卻是從後往前，要求 f(9)，就要求f(8)和f(7),要求f(8)，就要求f(7)和f(6)
37     遞歸的具體過程這裡就不贅述了，遞歸是先由後往前，再由前往後得到f(9)，進行了兩輪 
38     非遞歸是直接由前往後到f(9) ，進行了一輪 
39 */ 
40 int Fibonacci_Recursion(int n){
41     if(n==2||n==1) return 1;
42     else{
43         return Fibonacci_Recursion(n-1)+Fibonacci_Recursion(n-2);
44     } 
45 } 
46 
47 int main(){
48     int n;
49     //n=Fibonacci(9);
50     n=Fibonacci_Recursion(9);
51     printf("%d\n",n);
52     return 0;
53 } 

（3）答案

34

三、實例擴展

3.1 臺階問題

有n階臺階，每次可以跨一階或者二階，求總共有多少種走法?

遞推公式為f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;這裡不贅述了。

3.2 兔子問題

農場來了一對小兔子，小兔子兩個月可長大，長大後每個月生一對小兔子，求n個月後兔子總對數。

遞推公式為f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;這裡不贅述了。