首页 > 代码库 > 递推算法

递推算法

递推算法

一、递推算法简介

一般是两步:

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;这里不赘述了。

 

递推算法