递归和非递归算法求解Fibonacci数列
我们可以采用递归以及非递归的方法对其进行求解。
下面分别用两种方法求解，并分析算法的时间复杂度。
输入 时，
输入 时，
假设 时 ， 正确,
当 时， 正确。
So the correctness of Algorithm has been proved.
对于 来说，每个问题被分成了两个子问题。每分割一次，问题的规模线性减少。
对于每个节点来说，每个节点对应算法执行一次操作的时间复杂度为 。
二叉树的总层数为 , 所以我们可以近似认为
下面给出具体分析：
对于 :
尾部常数 4 代表 四次常数操作 (1 comparison, 2 subtractions, 1 addition)
我们可以发现 , 代入得：
所以lower bound我们说，
我们认为 ， 因为
可得：
我们可以发现 , 代入得：
所以对upper bound我们说，
综上，该算法时间复杂度
首先，为A[0], A[1]赋值分别需要两个 的操作。
对于循环部分，时间复杂度为 。
所以
综上，迭代方法求解Fibonacci的时间复杂度为
最初发布在我的 个人博客 上。欢迎访问。
java: 用递归和非递归两种写出N!写1+1\/2-1\/3+1\/4-1\/5……+1\/n程序_百...
public class Digui { \/\/递归算法:public static double digui(int n){ double sum = 0.0;if (n == 1) { sum = 1;}else{ if (n%2 == 0) { sum = 1.0\/n+digui(n-1);}else{ sum = -1.0\/n+digui(n-1);} } return sum;} \/\/非递归算法：public static double feidi...
利用层序遍历非递归地求解树的深度
求解树的深度如果用递归的话那就很简单，思想就是树的深度等于左子树深度+1和右子树深度+1的最大值，这里不再赘述，但如果用非递归的话那就可以利用层序遍历了，这个算法是在王道的数据结构书上看到的。接下来以这个图为例解释一下这个算法。下面我们来进行循环：进入循环前:front=-...
面试必看算法题 | 回溯算法解题框架
例如，通过重复元素判断、状态检查等方法避免生成重复结果。在具体问题中，灵活运用这个框架，如在某些问题中，回溯并非必需，如单词搜索找到单词后即可停止搜索。排列、组合和子集问题是回溯算法的常见应用，通过理解顺序和无序的区别，我们可以利用递归或非递归方法高效求解。字典序排列则要求按照特定顺序生成...
分而治之算法注意事项
分而治之算法是一种常见的解决问题策略，它通过将大问题分解为较小的子问题来求解。虽然递归算法在处理分而治之问题时常见，但在某些情况下，非递归方式也能实现更快的执行速度。例如，在寻找8个金块中最轻和最重金块（金块问题）和归并排序中，非递归方法可以避免递归栈的开销。非递归的分而治之算法...
C语言的两个问题: 所有的递归程序均可以用非递归算法实现?递归函数中的...
C语言所有递归都可以用非递归算法实现,最典型的就是迭代法,有时比递归更容易理解。至于递归中的形式参数是自动变量,没明白楼主的意思,形参就是形参啊,形参变量也是变量,其内存分配在栈区,随着函数的结束,其内存也会被释放,形参的生命周期与函数生命周期相同哈(同生共死) 本回答由提问者推荐 举报| 答案纠错 | ...
...试写出技术下列递归函数f(n)的递归和非递归算法
include <stdio.h> \/\/递归：int f1(int n){ if(n==0)return 1;return n*f1(n\/2);} \/\/非递归：int f2(int n){ int sum=1;while(n!=0){ sum*=n;n\/=2;} return sum;} int main(){ int sum;while(scanf("%d",&sum)!=EOF){ if(sum<0)return 1;printf("%d %d\\n",...
...分别用非递归法和递归法编程求解该数列第1到1000项的和
就是要求1000阶乘吧，其实计算机的正常运算时做不到1000的，上面的那些程序只会都得到较小数字的阶乘，至于1000，根本算不出来的。。。看看这个吧。。。include<stdio.h> define Max 12345 int main(){ int wei[Max],jinwei[Max];int i,j,n,k,top=1;wei[1]=1,jinwei[1]=1;printf("please...
汉诺塔的算法是怎样的呢?
汉诺塔问题也可以借助非递归算法来解决，有许多种非递归算法可以解决汉诺塔问题，博主认为最常见的是利用递归二叉树，下面列举两种非递归算法。1.利用二叉递归树 文献[4]指出：汉诺塔问题的递归算法代码与二叉树的中序遍历算法代码十分相似，故采用了二叉树的中序遍历，发现汉诺塔问题的算法步骤正好可以画成一...
斐波那契数列两种算法的时间复杂度
*具体题目：求解斐波那契数列的F(n)有两种常用算法：递归算法和非递归算法。试分析两种算法的时间复杂度。时间复杂度分析：求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4)。。。以此类推，直至必须先计算F(1)和F(0),然后逆推得到F(n-1)...
利用栈编写递归函数的非递归算法
我感觉这道题目出得有问题：假设这道题目用递归来实现，当用户输入的x、y满足x=0 && y>=0或者x>0 && y<0时才合法。但是对于后一种情况，由于y是一个负数，输入的数在递归时传递给递归函数时的形式为x-1和2*y，2*y是永远不会变成一个大于等于0的数的，因此x=0 && y>=0就无法作为递归...
爱新觉罗寿凯宝： #include<stdio.h> void main() {int i,n;int f[]= {1,1};printf(＂请输入n的值:＂);scanf(＂%d＂,&n);for(i=2; i<=n; i++)f[i] = f[i-2] + f[i-1];for(i=0; i<=n; i++){if(i%5==0) printf(＂\n＂);printf(＂%12d＂,f[i]); }printf(＂\n＂); } //以上是非递归算...
安国市17684589762： 求fibonacci数列算法,并比较.(递归+非递归) - ？
爱新觉罗寿凯宝： 递归算法 int fib(int n){ //求fibonacci数列第n个数if(n==1 || n==2) return 1;else return fib(n-1) + fib(n-2); }非递归 int fib(int n){int a = 1, b = 1;if(n==1 || n==2) return 1;for(int i=3; i<=n; i++){int tmp = b;b = a + b;a = tmp;}return b; }
安国市17684589762： C语言题目:用递归和非递归子函数求n!、第n个Fibonacci数, 第1、2个为1. - ？
爱新觉罗寿凯宝： #include <stdio.h>//递归求n! int func1(int n) { if(n==1) return 1; elsereturn func1(n-1)*n; }//递归求Fibonacci int func2(int n) { if(n==1 || n==2) return 1; elsereturn func2(n-1)+func2(n-2); }//非递归求n! int func3(int n) { int i,sum=1; for(i=1;i<=n;i++) { ...
安国市17684589762： 菲波那契(Fibonacci)数列的第一项是0,第二项是l,以后各项都是前两项的和,试用递归算法和非递归算法各编 - ？
爱新觉罗寿凯宝： 首先 你得注意 如果你求的斐波那契数的第几项项数较大 就需用到高精度 以下程序仅适用于“无需高精度”的情况: 此为递归算法: #include<iostream> using namespace std; int work(int x) {if(x==1)return 0;else if(x==2)return 1;else return ...
安国市17684589762： 分别用递归和非递归方法求取Fibonacci数列. - ？
爱新觉罗寿凯宝： //fibonacci数列:1 1 2 3 5 8 13 21 34 55...#include<stdio.h> double fib_val[100]={0};double fibonacci_1(int n)//递归,计算时间长,n最好不超过30 {if(n<2){return 1.0;}return fibonacci_1(n-1)+fibonacci_1(n-2); }void fibonacci_2(int n)//非递...
安国市17684589762： 求fibonacci数列(递归+非递归) - ？
爱新觉罗寿凯宝： #include int main() { int i=0,j=1,k=1,l,n=1; scanf(＂%d＂,&l); while(n int main() { int i=0,j=1,k=1,l,n=1; scanf(＂%d＂,&l); while(n
安国市17684589762： C++ 递归及非递归的方法求Fibonacci函数 作者是谭顺富写的就好了 - ？
爱新觉罗寿凯宝： /* *文件功能:递归的方法求Fibonacci级数 *作者:姓名:谭顺富 学号:0531100821 电子邮件:tanshunfu@mail.gxu.cn *谭顺富的博客:http://tanshunfu.blog.163.com/profile/edit/*/# include <iostream> using namespace std; inline double fib(...
安国市17684589762： 递归求解斐波那契数列 - 上学吧普法考试？
爱新觉罗寿凯宝： #includevoid main( ) { int f[10]; int i; f[0]=1; f[1]=1; for (i=2;i<10;i++) f[i]=f[i-2]+f[i-1]; for (i=0;i<10;i++) printf (＂%3d＂,f[i]); }
安国市17684589762： 斐波那契数列的定义为它的第1页和第2页均为1以后各项为其前两项之和,设斐波那契第n项f(n)则有: - ？
爱新觉罗寿凯宝： 递归很简单:描述如下 f(n) if(n==1 || n==2) return 1; return f(n-1)+f(n-2); 非递归用循环就可以做到:a=b=1; for (i=3; i<n;i++) { t=b; b=a+b; a=t; } return b; 时间 空间复杂度 根据你自己的程序自己分析了,时间应该都在O(n),空间前者是O(n)(如果考虑递归调用入栈出栈), 后者是O(1);
