【无标题】

简介: 斐波那契数列的特点就是从第二项开始每一项都等于前两项之和。那么从数学角度思考可以写成它的一个表达式为Fib(n)=Fib(n-1)+Fib(n-2) 当n>2时。如果n<2即为1.

求解斐波那契数列--小白篇


一级目录 递归法


     ********递归法就是函数自身调用自己的技巧************
     **********递归的两个必要条件:********


1. 存在限制条件,当满足这个限制条件的时候,递归便不再继续。

2. 每次递归调用之后越来越接近这个限制条件。

斐波那契数列的特点就是从第二项开始每一项都等于前两项之和。那么从数学角度思考可以写成它的一个表达式为Fib(n)=Fib(n-1)+Fib(n-2) 当n>2时。如果n<2即为1.


代码如下:`

int Fib(int n)
{
  if (n <= 2)
    return 1;
  else
    return Fib(n - 1) + Fib(n - 2);
}
int main()
{
  int n;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d", ret);
  return 0;
}


但这个代码运行效率十分低下,为什么呢,,是因为不断进行了大量重复的计算,


243b13e5275e47bfb2bd36c19d293d5b.png


计算量非常大。那怎么解决呢?


二级目录 非递归法(即循环)


递归的方法计算量非常大,所以我们不使用递归的方法,用循环的方法,递归呢是从后往前想的,而正常的思考应该是从一开始往后想,只要把前两项相加就可以得到想要的数了。

![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/9a04ed68802345c1b1c5cefd28246054.png


f93c79576590421e96dc8f606f5524b2.png


先创建变量 a=1,b=1,c=1,把a看成第一项b看成第二项,而c 看成第三项,令c=a+b,这就得到了第第三项,可我们需要后面的项怎么弄呢,这时只要令 b的值赋给a ,c的值赋给b使这个过程进行循环就可以得到后面的项了,不过这个循环次数受n控制,当n=3 时 , 1+1=2 2+1 =3 这时进行了两次加法计算,而当n=5时,1+1=2, 2+1=3, 3+2=5,进行了三次加法计算,所每次循环n都要减1(循环条件是n>2)代码如下:*


在这里插入代码int Fib(int n)
{ 
  int a = 1;
  int b = 1;
  int c = 1;
  while (n>2)
  {
    c = a + b;
    a = b;
    b = c;
    n--;
  }
  return c;
}


三级目录 如何理解递归呢?


可以试着从函数栈帧方面思考:


每一次函数调用都会为本次函数调用分配空间(是在内存的栈区上的)


为本次函数调用分配空间的叫做这个函数调用的栈帧区间。


27f4f35c6a2b4795807801d99b137913.png


内存被分为栈区和堆区还有静态区。


0e78ba8485e94353a6a11db6dc924788.png


申请空间是自下而上的申请到的,而调用完后的函数所分配的空间还给内存时是自上而下销毁的 ,这与递归的思想相似。


7bc9048998be48b8bea30d2c67cf3f91.png


以上是我个人的观点,我是小白 勿喷哇!!!谢谢!!!

相关文章
|
前端开发
css 实现 title的效果,并且自己写修改类似title样式
css 实现 title的效果,并且自己写修改类似title样式
css 实现 title的效果,并且自己写修改类似title样式
|
1月前
|
存储 前端开发
【无标题】
【无标题】
16 0
meta常用标签总结
meta常用标签总结
86 0
|
算法 C++
无标题。。。
无标题。。。
|
JavaScript 前端开发
v-text和v-html
v-text和v-html
171 0
|
Web App开发 缓存 搜索推荐
|
应用服务中间件 nginx NoSQL
Title comes here
asdasdadawdwadaw
1482 0