很多时候递归是很直观的解决问题的方式,但往往递归的分支较多或层数较深的时候会导致程序运行超时或递归栈爆炸。
以HDUOJ 2041题为例,实际上该题就是fibnacci数列求解,但如果我们写成
int fib(int n) {
if(n==0) return 1;
if(n==1) return 1;
else return fib(n-1)+fib(n-2);
}
画出递归树,当n=40的时候,需要计算次数是大约是1+2^1+2^2+...+2^39=2^40-1(实际是((1+sqrt(5))/2)^n),约等于10^12,明显会超时。
这个时候就需要用递推来解决了,2041的代码如下
#include <iostream>
#include <iomanip>
#include <cmath>
#define PI 3.1415927
using namespace std;
//采用递推,如果使用递归会超时
int func(int n) {
int a[40]={0};
a[0]=1;
a[1]=1;
for(int i=2; i<n; i++) {
a[i]=a[i-1]+a[i-2];
}
return a[n-1];
}
int main()
{
int n;
cin >> n;
for(int i=0; i<n; i++) {
int m;
cin >> m;
cout << func(m) << endl;
}
return 0;
}
目前求fibnacci数列最快可以利用分治思想做到O(lgn)
分享到:
相关推荐
C语言函数的递归和调用实例分析
关于递归算法时间复杂度分析的探讨.pdf
在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法.在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分. 18117的数字和为:1+8+1+1+7=18....
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。C语言允许函数的递归调用。在递归调用中,主调函数又是被调函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层
代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间...
以前用递归总不明白,所以写个实例供大家参考 有数据库表的格式 一看就明白,就几行,还有个组建 treeview 给注了
这是一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。利用C语言编制递归下降分析程序,并对简单语言进行语法分析。
使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用自己,这种问题显然可以用递归解决,递归的...
1、使用递归下降分析算法分析表达式文法: exp ::= exp addop term | term addop ::= + | - term ::= term mulop factor | factor mulop ::= * | / factor ::= (exp) | number 其中number可以是多位的十进制数字串...
此代码展示了一种用递归解决迷宫问题的方法,可以自行输入迷宫即得到解答
八皇后问题实验报告递归非递归javaC语言+分析可用.pdf
一个关于递归下降语法分析器设计的文档
递归下降的语法分析编程实现,递归下降的语法分析编程实现,递归下降的语法分析编程实现,
一个关于递归下降的语法分析,对于学习编译原理的初学者应该比较有参考价值,结构清晰,易懂。
递归图工具和递归量化分析指标对复杂系统的分析
递归下降语法分析器的实现递归下降语法分析器的实现递归下降语法分析器的实现递归下降语法分析器的实现递归下降语法分析器的实现
有一个关于递归的小游戏,ppt教程,VB做的递归算法实例,短小精悍
词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 改造文法:消除二义性、消除左递归、提取左因子,判断是否为LL(1)文法。
该资源通过将生活中的问题转化为用递归的思想去解决。