首页 > 代码库 > 递推算法
递推算法
递推算法
一、递推算法简介
一般是两步:
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;这里不赘述了。
递推算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。