斐波那契数列c语言 求斐波那契(Fibonacci)数列通项的七种实现方法

2019-01-22 - 斐波那契

求斐波那契(Fibonacci)数列通项的七种实现方法  更新时间:2013年05月24日 09:49:43   作者:   我要评论

一:递归实现 使用公式f[n]=f[n-1] f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1。 二:数组实现 空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快。 三:vector<int>实现 时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源。

斐波那契数列c语言

四:queue<int>实现 当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了, f(n)=f(n-1) f(n-2),f(n)只和f(n-1)和f(n-2)有关,f(n)入队列后,f(n-2)就可以出队列了。

五:迭代实现 迭代实现是最高效的,时间复杂度是0(n),空间复杂度是0(1)。 六:公式实现 百度的时候,发现原来斐波那契数列有公式的,所以可以使用公式来计算的。

斐波那契数列c语言

由于double类型的精度还不够,所以程序算出来的结果会有误差,如果把公式展开计算,得出的结果就是正确的。 完整的实现代码如下: 复制代码 代码如下: #include "iostream" #include "queue" #include "cmath" using namespace std; int fib1(int index)     //递归实现 {  if(index<1)  {   return -1;  }  if(index==1

index==2)   return 1;  return fib1(index-1) fib1(index-2); } int fib2(int index)     //数组实现 {  if(index<1)  {   return -1;  }  if(index<3)  {   return 1;  }  int *a=new int[index];  a[0]=a[1]=1;  for(int i=2;i<index;i )   a[i]=a[i-1] a[i-2];  int m=a[index-1];  delete a;         //释放内存空间  return m; } int fib3(int index)           //借用vector<int>实现 {  if(index<1)  {   return -1;  }  vector<int> a(2,1);      //创建一个含有2个元素都为1的向量  a.

斐波那契数列c语言

reserve(3);  for(int i=2;i<index;i )  {   a.insert(a.

begin(),a.at(0) a.at(1));   a.pop_back();  }  return a.at(0); } int fib4(int index)       //队列实现 {  if(index<1)  {   return -1;  }  queue<int>q;  q.

push(1);  q.push(1);  for(int i=2;i<index;i )  {   q.

push(q.front() q.back());   q.pop();  }  return q.back(); } int fib5(int n)          //迭代实现 {  int i,a=1,b=1,c=1;  if(n<1)  {   return -1;  }  for(i=2;i<n;i )  {   c=a b;     //辗转相加法(类似于求最大公约数的辗转相除法)   a=b;   b=c;  }  return c; } int fib6(int n) {  double gh5=sqrt((double)5);  return (pow((1 gh5),n)-pow((1-gh5),n))/(pow((double)2,n)*gh5); } int main(void) {  printf("%d\n",fib3(6));  system("pause");  return 0; } 七:二分矩阵方法如上图,Fibonacci 数列中任何一项可以用矩阵幂算出,而n次幂是可以在logn的时间内算出的。

下面贴出代码: 复制代码 代码如下: void multiply(int c[2][2],int a[2][2],int b[2][2],int mod) {  int tmp[4];  tmp[0]=a[0][0]*b[0][0] a[0][1]*b[1][0];  tmp[1]=a[0][0]*b[0][1] a[0][1]*b[1][1];  tmp[2]=a[1][0]*b[0][0] a[1][1]*b[1][0];  tmp[3]=a[1][0]*b[0][1] a[1][1]*b[1][1];  c[0][0]=tmp[0]%mod;  c[0][1]=tmp[1]%mod;  c[1][0]=tmp[2]%mod;  c[1][1]=tmp[3]%mod; }//计算矩阵乘法,c=a*b int fibonacci(int n,int mod)//mod表示数字太大时需要模的数 {  if(n==0)return 0;  else if(n<=2)return 1;//这里表示第0项为0,第1,2项为1  int a[2][2]={{1,1},{1,0}};  int result[2][2]={{1,0},{0,1}};//初始化为单位矩阵  int s;  n-=2;  while(n>0)  {   if(n%2 == 1)    multiply(result,result,a,mod);   multiply(a,a,a,mod);   n /= 2;  }//二分法求矩阵幂  s=(result[0][0] result[0][1])%mod;//结果  return s; } 附带的再贴上二分法计算a的n次方函数。

斐波那契数列c语言

复制代码 代码如下: int pow(int a,int n) {  int ans=1;  while(n)  {   if(n&1)    ans*=a;   a*=a;   n>>=1;  }  return ans; } 您可能感兴趣的文章:python实现斐波那契递归函数的方法python求斐波那契数列示例分享用Python实现斐波那契(Fibonacci)函数java实现斐波那契数列的3种方法C 输出斐波那契数列的两种实现方法c#斐波那契数列(Fibonacci)(递归,非递归)实现代码php实现斐波那契数列的简单写法php处理斐波那契数列非递归方法C语言使用普通循环方法和递归求斐波那契序列示例代码python实现斐波那契数列的方法示例

相关文章 C 搬水果贪心算法实现代码这篇文章主要介绍了C 搬水果贪心算法实现代码的相关资料,需要的朋友可以参考下 2017-06-06 C 的try块与异常处理及调试技术实例解析这篇文章主要介绍了C 的try块与异常处理及调试技术实例解析,有助于读者加深对try块调试技术的认识,需要的朋友可以参考下 2014-07-07 详解C语言gets()函数与它的替代者fgets()函数这篇文章主要介绍了详解C语言gets()函数与它的替代者fgets()函数的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下 2016-10-10 数据结构之归并排序的实例详解这篇文章主要介绍了数据结构之归并排序的实例详解的相关资料,这里对归并排序进行详细介绍,需要的朋友可以参考下 2017-08-08 探讨C语言的那些小秘密之断言我尽可能的把我所理解的断言的使用讲解清楚,希望我在此所讲的断言能够对你有所帮助,让你以后能够在代码中灵活使用断言 2013-09-09 老生常谈C/C 内存管理下面小编就为大家带来一篇老生常谈C/C 内存管理。

小编觉得挺不错的,现在就分享给大家,也给大家做个参考。

一起跟随小编过来看看吧 2017-05-05 C语言之从字符数组中删除特定的字符本篇文章主要介绍了从字符数组中删除特定字符的实现方法,有需要的朋友可以参考下 2015-07-07 详解C 编程中的输入输相关的类和对象这篇文章主要介绍了详解C 编程中的输入输相关的类和对象,是C 入门学习中的基础知识,需要的朋友可以参考下 2015-09-09 希尔排序算法的C语言实现示例这篇文章主要介绍了希尔排序算法的C语言实现示例,希尔排序可以看作为一种高级的插入排序,需要的朋友可以参考下 2016-04-04 基于一致性hash算法 C 语言的实现详解在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c 语言对一致性hash进行了简单的实现 2013-05-05

相关阅读
  • 斐波那契数列炒股 斐波那契回调线的正确画法概述

    斐波那契数列炒股 斐波那契回调线的正确画法概述

    2019-01-22

    上升趋势是指在给定时间周期内,当每一轮上涨的高点(拐点)不断创新高,每一轮回调的低点(拐点)也不断抬高的趋势,如图5.5。图5.5上升趋势下降趋势是指在给定时间周期内,当每一轮下跌的低点(拐点)不断创新低,每一轮回调的高点(拐点)也不断降低的趋势,如图5.6。图5.6下降趋势横向震荡是指在给定时间周期内。

  • 列昂纳多·斐波那契 斐波那契回调线的三种错误画法

    列昂纳多·斐波那契 斐波那契回调线的三种错误画法

    2019-01-22

    图5.16是斐波那契回调线的第一种常见错误示意图。该错误是将绘制斐波那契回调线的出发点和终点顺序相反连接,我们知道该图正确的斐波那契回调线出发点应该是低点1,终点是高点2;图中错误的将出发点认定为高点2,终点为低点1。这种错误的绘制方法使斐波那契回调线失去意义,并有可能误导我们的分析判断。读者不要一味地认为斐波那契回调线就是从低点连接到高点。

  • 斐波那契曲线

    斐波那契曲线

    2019-01-22

    相机中的斐波那契螺旋线的作用:用斐波纳契比例构造完美构图。你是否是一个注重细节的人?如果你是一名摄影师,那么最好回答是。对任何摄影师来说,理解了三分法则都是一个重要的里程碑。突然之间,你意识到以前拍的照片中,都把主体放在了画面...斐波那契曲线接近于一个指数函数f(x)(15)2x记得采纳啊斐波那契曲线是通过边长为斐波那契数列的一系列正方形

  • 斐波那契火锅 分析研究:斐波那契周期神奇用法

    斐波那契火锅 分析研究:斐波那契周期神奇用法

    2019-01-22

    古人云quot;时势造英雄quot;quot;识时务者为俊杰quot;,说明成为英杰人才都离不开时机。在投资领域,若要成为杰出的人物同样需要把握好时机。特别是在一个可以双向交易的投资市场中,投资什么品种其实已经既定,留给用户需要思考的问题是quot;什么是投资时段quot;。所谓投资就是未来可预见的时期内向某一领域投放足够数额的资金获得收益或则出现亏损的经济行为。