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

2022-10-11 137

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

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

@TOC

前言

斐波那契数列（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;
}