算法 | 两种方式实现斐波那契数

简介: 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”

在这里插入图片描述
啊我摔倒了..有没有人扶我起来学习....

前言

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”


一、递归实现斐波那契数

  • 首先,我们要知道,要实现递归,就要:

    1. 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
    2. 其次,递归不能无限循环下去,需要结束条件
  • 然后,用递归的思想去分析斐波那契数的特点,把它拆分成一个个相似的小问题,再确定结束递归的条件

在这里插入图片描述

  • 我们发现,除了前两个数1,后面每个数都是它的前两个数之和。于是我们就可以确定出:

    1. 每一个小问题就是==用前两个数之和计算出后一个数==
    2. 停止递归的条件是当n<=2
  • 所以,第n个斐波那契数肯定是,第(n-1)个斐波那契数和第(n-2)个斐波那契数之和。根据这个想法,写出代码,并加上结束条件
int fibo_num(int n)
{
    if (n > 2)
        return fibo_num(n - 1) + fibo_num(n - 2);
    else
        return 1;
}
输出结果: 在这里插入图片描述

二、循环实现斐波那契数

  • 其实非递归方法(循环)更容易想到怎么写,刚刚也已经分析过了。只要给出前两个数1,然后每前两个数之和就是下一个数
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//斐波那契数(非递归)
int main()
{
    int n = 0;
    while (~scanf("%d", &n))
    {
        if (n <= 2)
            printf("第%d个斐波那契数是1\n", n);
        else
        {        
            int a = 1;
            int b = 1;
            int c = 0;
            for (int i = 3; i <= n; i++)
            {
                c = a + b;
                a = b;
                b = c;
            }
            printf("第%d个斐波那契数是%d\n", n, c);
        }
    }
    return 0;
}
输出结果: 在这里插入图片描述

三、比较递归与非递归实现斐波那契数

3.1 非递归

  • 很简单的原理没啥好讲的哈哈。咱们就看计算的次数叭~
咱们加入 count来计数
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//斐波那契数(非递归)
int main()
{
    int n = 0;
    int count = 0;
    while (~scanf("%d", &n))
    {
        if (n <= 2)
            printf("第%d个斐波那契数是1\n", n);
        else
        {        
            int a = 1;
            int b = 1;
            int c = 0;
            for (int i = 3; i <= n; i++)
            {
                count++;
                c = a + b;
                a = b;
                b = c;
            }
            printf("第%d个斐波那契数是%d\n", n, c);
            printf("循环了%d次\n", count);
        }
    }
    return 0;
}
输出结果: 在这里插入图片描述

3.2 递归

  • 假如我们求第6个斐波那契数是8,我们来看一下递归的原理图

在这里插入图片描述

可以看出来,貌似计算了挺多次,我们用代码算算看
#include<stdio.h>
//斐波那契数(递归)
count = 0;
int fibo_num(int n)
{  
    count++;
    if (n > 2)
        return fibo_num(n - 1) + fibo_num(n - 2);
    else
        return 1;
}

int main()
{
    int n = 0;

    while (~scanf("%d", &n))
    {
        int result = fibo_num(n);
        printf("第%d个斐波那契数是%d\n", n, result);
        printf("递归了%d次\n", count);
    }
    return 0;
}
输出结果: 在这里插入图片描述居然用了这么多次!!!
  • 最恐怖的还不是这,假如你要计算第40个斐波那契数?

在这里插入图片描述

  • 假如第50个呢?反正博主的电脑没跑出来。。。

四、总结

  • 总之,递归让代码变得简洁,但并不代表效率就提高了,要具体情况具体分析哦~

在这里插入图片描述

相关文章
|
Python
在dataframe中插入新的一行
在pandas中,可以使用`insert`函数在dataframe中插入新的一行。
1290 1
|
3月前
|
开发工具 git
使用Git下载指定版本或指定commit
使用Git下载指定版本或指定commit
|
Linux Windows
Windows查找监听端口对应的进程及其路径
Windows查找监听端口对应的进程及其路径
305 0
|
机器学习/深度学习 缓存 移动开发
Python 零基础快速上手(与C/C++对比)
Python 零基础快速上手(与C/C++对比)
398 0
【5分钟+】计算机系统结构:CPU性能公式
【5分钟+】计算机系统结构:CPU性能公式
1108 0
【5分钟+】计算机系统结构:CPU性能公式
|
Java 调度 Python
解决方案:APScheduler定时任务不执行,报错Run time of job ... was missed by ...
解决方案:APScheduler定时任务不执行,报错Run time of job ... was missed by ...
1648 0
解决方案:APScheduler定时任务不执行,报错Run time of job ... was missed by ...
|
算法 C++ 开发者
【C/C++ 解惑 】std::weak_ptr 背后解决的问题
【C/C++ 解惑 】std::weak_ptr 背后解决的问题
246 0
|
Python
dataframe操作查询
Pandas提供了多种查询方法,以下是一些常见的方法: 使用df.loc方法,根据行、列的标签值查询。 使用df.iloc方法,根据行、列的数字位置查询。 使用df.where方法,根据条件过滤数据。 使用df.query方法,根据字符串表达式查询数据。
989 0
|
人工智能 机器人 API
使用 OpenAI、LangChain 和 LlamaIndex 构建 Knowledge
使用 OpenAI、LangChain 和 LlamaIndex 构建 Knowledge
1400 0
|
安全 大数据 云计算
云专线的应用场景主要包括以下几个方面
云专线(Direct Connect)是一种网络服务,为用户提供一种安全、高速、稳定的私有网络连接,用于连接用户的本地IT环境(如私有云)与公有云、IDC、办公区等。这种服务主要通过运营商的MSTP、MPLS VPN、Vxlan等网络接入云服务器的内网,实现用户与云之间快速安全的访问。
641 0