当前位置: 首页 > news >正文

斐波那契数列模型:在动态规划的丝绸之路上追寻斐波那契的足迹(上)

文章目录

  • 引言
  • 递归与动态规划的对比
  • 递归解法的初探
  • 动态规划的优雅与高效
    • 自顶向下的记忆化搜索
    • 自底向上的迭代法
  • 性能分析与比较
  • 小结

在这里插入图片描述

引言

斐波那契数列,这一数列如同一条无形的丝线,穿越千年时光,悄然延续其魅力。其定义简单而优美:

F(0)=0,F(1)=1

F(n)=F(n−1)+F(n−2), n>1

这看似简单的递归公式,却蕴含着深刻的数学结构,成为计算机科学中的经典问题之一。斐波那契数列不仅仅出现在数学课本上,它在自然界、计算机算法、金融模型等领域中无处不在。对于程序员而言,斐波那契数列不仅是一个练习递归的好题目,更是一个优化算法的标杆。

在这篇文章中,我们将通过动态规划的技术来探讨如何高效地求解斐波那契数列,从而避免传统递归方法中低效的冗余计算。我们将以 C 语言为例,展示动态规划方法如何一步步揭开这一问题的面纱。

递归与动态规划的对比

递归解法的初探

初识斐波那契数列,往往从递归开始。递归是一个从问题的定义出发,层层拆解的过程。我们通过编写递归函数来模拟斐波那契数列的计算:

#include <stdio.h>int fibonacci_recursive(int n) {if (n <= 1) {return n;}return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}int main() {int n = 10;printf("Fibonacci(%d) = %d\n", n, fibonacci_recursive(n));return 0;
}

代码分析

这段代码极其直观,正如数列的定义那样,利用递归直接表达了斐波那契数列的生成。

然而,这种实现方式的效率极低。

  • 对于每一个fibonacci_recursive(n) 调用,都会同时递归调用 fibonacci_recursive(n-1) fibonacci_recursive(n-2),造成了大量的重复计算。例如,在计算 fibonacci_recursive(5)
    时,会重复计算 fibonacci_recursive(3) 和 fibonacci_recursive(2)。

  • 通过这样的计算树可以看到,随着 n 值的增加,重复计算的次数呈指数级增长。时间复杂度为
    O(2^n),这对于较大的 n 来说,已经无法接受。

动态规划的优雅与高效

递归方法的瓶颈在于大量的重复计算,而动态规划(Dynamic Programming, DP)正是为了解决这个问题而应运而生。

动态规划的精髓在于通过存储中间结果来避免重复计算,将复杂的递归结构转化为迭代计算。

动态规划解决斐波那契数列问题的关键在于,子问题之间是重叠的,即在计算 F(n) 时,F(n-1) 和 F(n-2) 都已经被计算过,因此可以将这些中间结果保留,从而提高效率。

自顶向下的记忆化搜索

自顶向下的动态规划方法结合了递归和记忆化技术。在递归的过程中,我们通过一个数组或哈希表来存储已经计算过的结果,避免了重复计算。
以下是 C 语言的实现:

#include <stdio.h>#define MAX 1000int memo[MAX];// 初始化 memo 数组
void initialize_memo() {for (int i = 0; i < MAX; i++) {memo[i] = -1;}
}// 使用记忆化递归计算斐波那契数列
int fibonacci_memo(int n) {if (n <= 1) {return n;}if (memo[n] != -1) {return memo[n];  // 返回已经计算过的结果}// 否则,计算并保存结果memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);return memo[n];
}int main() {int n = 10;initialize_memo();  // 初始化 memo 数组printf("Fibonacci(%d) = %d\n", n, fibonacci_memo(n));return 0;
}

代码分析:

  • 在这个实现中,我们使用了一个名为 memo 的数组来保存计算过的斐波那契数值。每次计算 fibonacci_memo(n) 时,首先检查 memo[n] 是否已经有值,如果有值,则直接返回结果;如果没有值,则计算并保存结果。
  • 这样做的时间复杂度为 O(n),空间复杂度为 O(n)。

自底向上的迭代法

在进一步优化中,我们可以将自顶向下的递归方法转换为自底向上的迭代方法,这不仅减少了递归调用的开销,还可以进一步优化空间复杂度。
在计算斐波那契数列时,我们只需要记住前两个数,而不需要存储整个序列。
以下是实现代码:

#include <stdio.h>// 自底向上的迭代法
int fibonacci_bottom_up(int n) {if (n <= 1) {return n;}int a = 0, b = 1;for (int i = 2; i <= n; i++) {int temp = a + b;a = b;b = temp;}return b;
}int main() {int n = 10;printf("Fibonacci(%d) = %d\n", n, fibonacci_bottom_up(n));return 0;
}

代码分析:

在这段代码中,我们从最小的两个数 0 和 1 开始,通过迭代逐步计算出更大的斐波那契数。我们仅用两个变量 a 和 b
来存储前两个数,从而使得空间复杂度降到了 O(1)。

性能分析与比较

通过对比不同方法的时间复杂度和空间复杂度,我们可以清楚地看到动态规划方法的优势。
在这里插入图片描述

从表中可以看到,自底向上的迭代法在时间和空间复杂度上都具有最优性能。
它不仅避免了递归调用的栈空间开销,还通过迭代方法有效降低了空间需求。

小结

斐波那契数列,作为数学中的一颗璀璨明珠,在计算机科学中具有举足轻重的地位。它不仅教会我们递归的基本思想,更让我们意识到优化的重要性。通过动态规划,我们能够以一种高效、优雅的方式解决斐波那契问题,避免了递归方法中冗余计算的困扰。

本篇关于动态规划解决斐波那契模型的讲解就暂告段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!

在这里插入图片描述

相关文章:

斐波那契数列模型:在动态规划的丝绸之路上追寻斐波那契的足迹(上)

文章目录 引言递归与动态规划的对比递归解法的初探动态规划的优雅与高效自顶向下的记忆化搜索自底向上的迭代法 性能分析与比较小结 引言 斐波那契数列&#xff0c;这一数列如同一条无形的丝线&#xff0c;穿越千年时光&#xff0c;悄然延续其魅力。其定义简单而优美&#xff…...

Hackthebox- Season7- Titanic 简记 [Easy]

简记 ip重定向到 http://titanic.htb,先添加hosts 收集子域名 wfuzz -c -u http://titanic.htb/ -w /usr/share/seclists/Discovery/DNS/subdomains-top1million-20000.txt -H Host:FUZZ.titanic.htb --hl 9 ******************************************************** * Wfu…...

Sa-Token 根据官方文档简单实现登录认证的示例

Sa-Token 根据官方文档实现登录鉴权测试 功能实现步骤依赖配置文件启动类创建 controller启动项目测试不用密码登录查看cookie状态 密码登录查看cookie状态 修改token名称 Apipost 测试无 cookie 模式【使用 token】后端将 token 返回到前端修改代码&#xff1a;测试&#xff1…...

rustdesk编译修改名字

最近&#xff0c;我用Rust重写了一个2W行C代码的linux内核模块。在此记录一点经验。我此前没写过内核模块&#xff0c;认识比较疏浅&#xff0c;有错误欢迎指正。 为什么要重写&#xff1f; 这个模块2W行代码量看起来不多&#xff0c;却在线上时常故障&#xff0c;永远改不完。…...

BS5852英国家具防火安全条款主要包括哪几个方面呢?

什么是BS5852检测&#xff1f; BS5852是英国针对家用家具的强制性安全要求&#xff0c;主要测试家具在受到燃烧香烟和火柴等火源时的可燃性。这个标准通常分为四个部分进行测试&#xff0c;但实际应用中主要测试第一部分和第二部分&#xff0c;包括烟头测试和利用乙炔火焰模拟…...

【运维】源码编译安装cmake

背景&#xff1a; 已经在本地源码编译安装gcc/g&#xff0c;现在源码安装cmake 下载源码 下载地址&#xff1a;CMake - Upgrade Your Software Build System 安装步骤&#xff1a; ./bootstrap --prefix/usr/local/cmake make make install 错误处理 1、提示找不到libmpc.…...

检测网络安全漏洞 工具

实验一的名称为信息收集和漏洞扫描 实验环境&#xff1a;VMware下的kali linux2021和Windows7 32&#xff0c;网络设置均为NAT&#xff0c;这样子两台机器就在一个网络下。攻击的机器为kali,被攻击的机器为Windows 7。 理论知识记录&#xff1a; 1.信息收集的步骤 2.ping命令…...

frameworks 之 Activity添加View

frameworks 之 Activity添加View 1 LaunchActivityItem1.1 Activity 创建1.2 PhoneWindow 创建1.3 DecorView 创建 2 ResumeActivityItem 讲解 Activity加载View的时机和流程 涉及到的类如下 frameworks/base/core/java/android/app/Activity.javaframeworks/base/services/cor…...

UWB技术中的两种调制方式:PPM与PAM

Ultra-Wideband (UWB) 技术以其低功耗、宽频谱和高精度定位的特点&#xff0c;广泛应用于物联网&#xff08;IoT&#xff09;、智能家居、资产追踪和无线通信等领域。在UWB中&#xff0c;信号的调制方式对于数据传输的效率和精度起着至关重要的作用。本文将深入探讨UWB中常用的…...

达梦:用户和模式

目录标题 数据库管理系统与用户权限管理**四权分立****用户管理与权限划分****用户管理界面与权限控制****用户创建与管理****实操**1. **默认创建用户与模式**&#xff1a;2. **用户权限和角色分配**&#xff1a;3. **命令行管理用户与角色**&#xff1a;4. 模式也可以创建 **…...

23. AI-大语言模型-DeepSeek

文章目录 前言一、DeepSeek是什么1. 简介2. 产品版本3. 特征4. 地址链接5. 三种访问方式1. 网页端和APP2. DeepSeek API 二、DeepSeek可以做什么1. 应用场景2. 文本生成1. 文本创作2. 摘要与改写3. 结构化生成 3. 自然语言理解与分析1. 语义分析2. 文本分类3. 知识推理 4. 编程…...

Spring-GPT智谱清言AI项目(附源码)

一、项目介绍 本项目是Spring AI第三方调用整合智谱请言&#xff08;官网是&#xff1a;https://open.bigmodel.cn&#xff09;的案例&#xff0c;回答响应流式输出显示&#xff0c;这里使用的是免费模型&#xff0c;需要其他模型可以去 https://www.bigmodel.cn/pricing 切换…...

计算机网络(涵盖OSI,TCP/IP,交换机,路由器,局域网)

一、网络通信基础 &#xff08;一&#xff09;网络通信的概念 网络通信是指终端设备之间通过计算机网络进行的信息传递与交流。它类似于现实生活中的物品传递过程&#xff1a;数据&#xff08;物品&#xff09;被封装成报文&#xff08;包裹&#xff09;&#xff0c;通过网络…...

云计算架构学习之Ansible-playbook实战、Ansible-流程控制、Ansible-字典循环-roles角色

一、Ansible-playbook实战 1.Ansible-playbook安装软件 bash #编写yml [rootansible ansible]# cat wget.yml - hosts: backup tasks: - name: Install wget yum: name: wget state: present #检查playbook的语法 [rootansible ansible]…...

《运维工程师如何利用DeepSeek实现智能运维:分级实战指南》

目录 智能运维革命:DeepSeek带来的范式转变DeepSeek核心运维能力全景解析分级实战场景与解决方案 3.1 初级工程师:自动化运维入门3.2 中级工程师:复杂系统诊断与优化3.3 高级工程师:架构级智能运维典型项目案例深度剖析 4.1 金融系统全链路监控体系构建4.2 电商大促资源弹性…...

windows事件倒计时器与提醒组件

widgets 这是桌面组件前端开源组件&#xff0c;作者称&#xff1a;项目还在持续完善中&#xff0c;目前包含键盘演示、抖音热榜、喝水提醒、生日列表、待办事项、倒计时、灵动通知、打工进度等多个组件 有vue编程能力的可以自己做组件 百度网盘 夸克网盘 桌面组件 | Ca…...

Mac OS JAVA_HOME设置

个人博客地址&#xff1a;Mac OS JAVA_HOME设置 | 一张假钞的真实世界 在MacOS上使用DMG文件安装了Jdk8 之后&#xff0c;在默认路径下找不到JDK的HOME路径&#xff1a; $ which java /usr/bin/java $ ls -l /usr/bin/java lrwxr-xr-x 1 root wheel 74 12 6 2015 /usr/b…...

6.3 DBMS的功能和特征

文章目录 DBMS的6大功能DBMS的3个特征DBMS的分类 DBMS的6大功能 DBMS包含数据定义&#xff0c;数据库操作&#xff08;检索、插入、修改、删除&#xff09;&#xff0c;数据库运行管理&#xff08;保证多用户环境下正常运行&#xff09;&#xff0c;数据组织、存储、管理&…...

C# ConcurrentQueue 使用详解

总目录 前言 在C#多线程编程中&#xff0c;数据共享如同走钢丝——稍有不慎就会引发竞态条件&#xff08;Race Condition&#xff09;或死锁。传统Queue<T>在并发场景下需要手动加锁&#xff0c;而ConcurrentQueue<T>作为.NET Framework 4.0 引入的线程安全集合&a…...

python脚本文件设置进程优先级(在.py文件中实现)

在 Python 代码中可以直接通过 psutil 模块或 系统调用 来设置进程优先级&#xff0c;无需依赖终端命令。以下是具体方法和示例&#xff1a; 1. 使用 psutil 模块&#xff08;跨平台推荐&#xff09; psutil 是一个跨平台库&#xff0c;支持 Windows、Linux 和 macOS。通过其 …...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

React核心概念:State是什么?如何用useState管理组件自己的数据?

系列回顾&#xff1a; 在上一篇《React入门第一步》中&#xff0c;我们已经成功创建并运行了第一个React项目。我们学会了用Vite初始化项目&#xff0c;并修改了App.jsx组件&#xff0c;让页面显示出我们想要的文字。但是&#xff0c;那个页面是“死”的&#xff0c;它只是静态…...

2.2.2 ASPICE的需求分析

ASPICE的需求分析是汽车软件开发过程中至关重要的一环&#xff0c;它涉及到对需求进行详细分析、验证和确认&#xff0c;以确保软件产品能够满足客户和用户的需求。在ASPICE中&#xff0c;需求分析的关键步骤包括&#xff1a; 需求细化&#xff1a;将从需求收集阶段获得的高层需…...