【C/C++】斐波那契数列数列系列问题详解

这篇具有很好参考价值的文章主要介绍了【C/C++】斐波那契数列数列系列问题详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 C++初阶
🌙励志卓越可以成为你努力的动力,追求完美却只会让你身心俱疲。🌙
🍉一起加油,去追寻、去成为更好的自己!

  斐波那契数列数列是我们学习递归的入门问题,是一种非常经典的题型,也衍生出了一些更复杂的题型,这一节就让我们彻底理解斐波那契数列系列问题。

斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法

提示:以下是本篇文章正文内容,下面案例可供参考


🍎、概念介绍

🍉、什么是斐波那契数列?

  斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N

🍉、怎么定义斐波那契数列

斐波那契数列指的是这样一个数列:1,1,2,3,5,8,13,21,34,55,89…
递推公式
斐波那契数列:1,1,2,3,5,8,13,21,34,55,89…
斐波纳契数列以如下被以递归的方法定义:
f[0] = 0, f[1] = 1;f[n] = f[n -1] + f[n - 2](n >= 2)
这个数列从第三项开始,每一项都等于前两项之和。
显然这是一个线性递推数列。

🍎、斐波那契数列系列问题详解

🍇最入门的斐波那契数列问题
斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
分析题意:是最基本的斐波那契数列问题,问的就是第n个斐波那契数列的值是多少并且输出出来。
根据我们的递推方程 : f[0] = 0, f[1] = 1;f[n] = f[n -1] + f[n - 2](n >= 2)即可求出

🔥递归示意图:🔥
斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
🔥最原始的递归代码示例:

#include<iostream>
using namespace std;
const int N = 100010;
int fbnq(int n)
{
    if (n == 1 || n == 2) return 1;
    if(n > 2)
    return (fbnq(n - 1) + fbnq(n - 2));
}

int main ()
{
    int n;
    cin >> n;
    cout << fbnq(n) << endl;
}

🔥写法二,利用数组a,实现一个斐波那契数列数组,下标和要输出的数对应一下。

#include<iostream>
using namespace std;
const int N = 100010;
int a[N] = {0}; //全局数组初始化,也可以不用,因为全局数组默认值都是1
void fbnx()
{
    a[1] = 1, a[2] = 1;
    for (int i = 3; i < 100001; i++)
    {
        a[i] = (a[i - 1] + a[i-2]) % 1000000;
    }
}
int main ()
{
    fbnx();
    int n;
    cin >> n;
    cout << a[n] << endl;
}

🍇牛客网:斐波那契凤尾
难度:中等
斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
分析题意:也是让我们输出n对应的斐波那契数,但是是有多组输入,而且是1 - 100000的斐波那契数,肯定超int了,所以只保留最后六位,还是向之前的递归过程。
🔥解法:我们用之前的写法2,建立一个斐波那契数列数组

🔥代码示例:

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N] = {0};
void fbnx()
{
	a[0] = 1, a[1] = 1;
	for (int i = 2; i < 100001; i++)
	{
		a[i] = (a[i - 1] + a[i-2]) % 1000000;//怕超Int,直接%100万
	}
}
int main()
{
	int n;
	fbnx();
	while (cin >> n)
	{
		if (n < 29)
		{
			printf("%d\n", a[n]);
		}
		else
		{
			printf("%06d\n", a[n]);
		}
		
	}

	return 0;
}

🍇牛客网: 星际密码
难度:较难
斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
分析题意:我为什么觉得这道题较难,就是因为本题题意比较难理解。矩阵运算和斐波那契数列结合了起来
斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
🔥所以这道题的解法就是初始化斐波那契数列,每次获取对应数据,打印后4位即可。
🔥代码示例:

#include<iostream>
#include<vector>
using namespace std;
int main ()
{
    vector<int> v = {1, 1};//初始化vector
    for(int i = 2;i < 10001; i++)
    {
        v.push_back((v[i - 1] + v[i -2]) % 10000);//取最后四位
    }
    
    int n;
    while(cin >>n)
    {
        int x = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> x;
            printf("%04d", v[x]);
        }
        printf("\n");
    }
    return 0;
}

本题小结:有时候不是因为这道题涉及的算法难,而是你看不懂这道题涉及的算法是啥,而且许多边界我们也是需要控制的,所以这就需要我们多刷题,才能更快,更准地读懂题意。


🍎、总结和思考

斐波那契数列c++,C++初阶,算法手札,蓝桥杯,c++,c语言,算法
  本文介绍了一下斐波那契数列概念,以及其定义方式,也通过三个斐波那契数列问题,来帮助大家来了解斐波那契数列问题的解法,解决斐波那契数列问题的关键就是要理解其递归过程,知道它的递归方程式,然后如果难一点的斐波那契数列问题就要考虑取模,希望大家读后能够有所收获!文章来源地址https://www.toymoban.com/news/detail-782204.html

到了这里,关于【C/C++】斐波那契数列数列系列问题详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(46)
  • C语言经典算法实例6:斐波那契数列

    斐波那契数列指的是这样一个数列:1,1,2,3,5,8,13,21,34,55,89… 这个数列从第3项开始,每一项都等于前两项之和。 斐波那契数列的定义者,是意大利数学家莱昂纳多·斐波那契(Leonardo Fibonacci),生于公元1170年,卒于1250年,籍贯是比萨。 他被人称作“比萨的莱昂

    2024年02月02日
    浏览(46)
  • 【算法优选】 动态规划之斐波那契数列模型

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契

    2024年02月05日
    浏览(56)
  • 一分钟学算法-递归-斐波那契数列递归解法及优化

    一分钟学一个算法题目。 今天我们要学习的是用递归算法求解斐波那契数列。 视频教程链接:https://www.bilibili.com/video/BV1Wu4y1i7JJ/ 首先我们要知道什么是斐波那契数列。 斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都

    2024年02月11日
    浏览(51)
  • 动态规划入门篇——斐波那契数列与爬楼梯问题

           动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,也是求解多阶段决策过程最优化问题的一种方法。它主要用来解决一类最优化问题,通过将复杂问题分解成若干个子问题,并综合子问题的最优解来得到原问题的最优解。动态规划的核心在于对问题的状态进

    2024年03月14日
    浏览(44)
  • Java【动态规划】斐波那契数列模型, 图文思路详解 + 代码实现

    本篇总结动态规划中的 斐波那契数列模型 的解法和思路 按照以下流程进行分析题目和代码编写 思路分析步骤 代码编写步骤 1, 状态表示 1, 构造 dp 表 2, 状态转移方程 2, 初始化+边界处理 3, 初始化 3, 填表(抄状态转移方程) 4, 填表顺序 4, 返回结果 5, 返回值 / OJ链接 题目分析

    2024年02月08日
    浏览(60)
  • 递归以及斐波那契数列递归算法和迭代算法的实现与分析

    程序调用自身的编程技巧称为递归( recursion) 递归有两个过程,简单地说一个是 递的过程 ,一个是 归的过程 。 递归的两个必要条件 1. 存在限制条件 ,当满足这个限制条件的时候,递归便不再继续。 2.每次递归调用之后越来越 接近这个限制条件 . 递归本质就是函数调用

    2024年02月12日
    浏览(40)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(48)
  • 【动态规划专栏】专题一:斐波那契数列模型--------2.三步问题

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月21日
    浏览(47)
  • 3-【斐波那契数列模型】LeetCode面试题08.01-三步问题

    题目 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入:n = 3  输出:4 说明: 有四种走法 示例2: 输入:n = 5 输出:13 提示:n范围在[1, 1000

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包