专栏首页用户画像斐波那契数列递归算法和非递归算法

斐波那契数列递归算法和非递归算法

斐波那契数列的表达式:

F(1)=1 F(2)=1

F(n)=F(n-1)+F(n-2)    (n>2)

递归算法:时间复杂度O(2^n)

int recursive_method(int n)
{
    if (n == 1 || n == 2)
         return 1;
   else
         return recursive_method(n - 1) + recursive_method(n - 2);
}

非递归算法:时间复杂度O(n)

int non_recursive_method(int n)  
{  
    int p = 1;  
    int q = 1;  
    int tmp;
    if (n == 1 || n == 2)  
	return 1; 
    else{ 
       for(int i = 3; i < n; i++) 
       { 
	      tmp = p;//本次循环的F(n-2)
              p = q; //p用来存储F(n-1),下一次循环就变成了F(n-2)

              q = tmp + q; //F(n)=F(n-1)+F(n-2) 
	}
 	return q; //q储存的为最新的F(n) 
    } 
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer 和为s的两个数字

    输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

    week
  • 剑指offer 构建乘积数组

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+...

    week
  • 剑指offer 二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    week
  • Java 8 中的拉姆达表达式是什么?

    拉姆达表达式就是一个匿名函数。在 C#中,拉姆达表达式是一个委托类型,因此拉姆达表达式可以赋值给一个委托变量。 Java 中,没有委托,Java 的设计者只能...

    水货程序员
  • 过河卒

    P1002 过河卒 题目描述 棋盘上AAA点有一个过河卒,需要走到目标BBB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CCC点有一个对方的马,该马所...

    glm233
  • LeetCode 684. 冗余连接(并查集)

    输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存...

    Michael阿明
  • cf1136E. Nastya Hasn't Written a Legend(二分 线段树)

    显然从一个位置开始能影响到的位置是单调的,而且这些位置的每个改变量都是\((a_i + x) + \sum_{t=i}^{j-1} k_t\)

    attack
  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • 06--图解数据结构之并查集

    张风捷特烈
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack

扫码关注云+社区

领取腾讯云代金券