递归问题示例

斐波那契数列

f ( n ) = { 1 n = 1 1 n = 2 f ( n − 1 ) + f ( n − 2 ) n > 2 1 , 1 , 2 , 3 , 5 , 8 . . . \begin{aligned} f(n)=\begin{cases}1&n=1\\ 1&n=2\\ f(n-1)+f(n-2)&n\gt2 \end{cases}\\ 1,1,2,3,5,8\quad ... \end{aligned} f(n)= 11f(n1)+f(n2)n=1n=2n>21,1,2,3,5,8...

上楼梯问题

一共有 n 个台阶,一次可以上 1 或 2 个台阶,请问有多少种走法?

(1)当 n = 1 n=1 n=1 时, f ( 1 ) = 1 f(1)=1 f(1)=1

(2)当 n = 2 n=2 n=2 时, f ( 1 ) = 2 , 1 + 1 2 f(1)=2,\quad \begin{aligned}1+1\\ 2\end{aligned} f(1)=2,1+12

(3)假设已知 f ( n − 1 ) , f ( n − 2 ) f(n-1),f(n-2) f(n1),f(n2),则 f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2)

到达第n级楼梯的方式可以从第n-1级楼梯一步走上来,也可以从第n-2级楼梯两步走上来

int f(int n){
    if(n<3)return n;
    return f(n-1)+f(n-2);
}
// 优化
vector<int> v;
int f(int n){
    if(n<3)return n;
    
    if (v.size() >= (n-2)) {
        return v.at(n-3);
    }
    v.push_back(f(n-1)+f(n-2));
    return v.back();
}
// 非递归
int g(int n){
    if(n<3)return n;
    queue<int> Q;
    Q.push(1);
    Q.push(2);
    for(int i=0;i<n-2;i++){
        int a = Q.front();
        Q.pop();
        int b=Q.front();
        Q.push(a+b);
    }return Q.back();
}

hanoi塔

在这里插入图片描述

  1. 把上面 n-1 个盘子移动到 B

  2. 只有一个盘子时,直接从 A 移到 C

  3. 把 B 的 n-1 个盘子也移到 C

void move(int n, char a, char c){
    printf("%d: %c -> %c\n", n, a, c);
}
void hanoi(int n, char a, char b, char c){
    if(n>1){
        hanoi(n-1, a, c, b);
        move(n, a, c);
        hanoi(n-1, b, a, c);
    }else{
        move(n, a, c);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/297943.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CMU15-445-Spring-2023-Project #1 - Buffer Pool

前置知识&#xff0c;参考上一篇博客&#xff1a;CMU15-445-Spring-2023-Project #1 - 前置知识&#xff08;lec01-06&#xff09; 在存储管理器中实现缓冲池。缓冲池负责将物理页从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的…

spring boot 集成邮件发送功能

一、首先到QQ邮箱申请开启POP3、SMTP协议 二、安装依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency><dependency><groupId>org.springframew…

【漏洞挖掘】挖掘CNVD证书

文章目录 一、CNVD介绍事件型漏洞通用型漏洞 二、挖掘思路1. 黑盒测试资产搜集fofa API筛选脚本 2. 白盒测试代码审计 3. google hack注意事项 一、CNVD介绍 国家信息安全漏洞共享平台&#xff08;简称CNVD&#xff09;&#xff0c;对于白帽子来说&#xff0c;挖掘的漏洞提交后…

关于谷歌Gemini大模型

2023年12月7日&#xff0c;谷歌AI宣布发布新一代基于Transformer架构的大模型Gemini。 Gemini的名字来源于双子座&#xff0c;象征着模型的双重性质&#xff1a; 一方面&#xff0c;它是一个强大的训练模型&#xff0c;可以在各种下游任务上进行微调&#xff0c;如文本摘要、机…

MiniTab的宏基础知识

什么是宏&#xff1f; 宏是包含一系列 Minitab 会话命令的文本文件。可以使用宏自动执行重复性任务&#xff08;例如&#xff0c;生成月度报表&#xff09;或扩展 Minitab 的功能&#xff08;例如&#xff0c;计算特殊检验统计量&#xff09;。 Minitab 提供以下类型的宏&…

计算机毕业设计选题分享-SSM律师事务所业务管理系统01664(赠送源码数据库)JAVA、PHP,node.js,C++、python,大屏数据可视化等

SSM律师事务所业务管理系统 摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;律师事务所业务管理系统当然也不能排除在外。律师事务所业务管理系统是以实际运用为开发背景…

CodeWave智能开发平台--03--目标:应用创建--04自定义主题样式5子页面页面跳转逻辑

摘要 本文是网易数帆CodeWave智能开发平台系列的第07篇&#xff0c;主要介绍了基于CodeWave平台文档的新手入门进行学习&#xff0c;实现一个完整的应用&#xff0c;本文主要完成04自定义主题样式5子页面页面跳转逻辑 参考:新手训练营-PC端应用 CodeWave智能开发平台的07次接…

NVIDIA Jetpack6.0DP使用过程中的问题

Jetpack6.0DP是2023年12月才发布&#xff0c; 操作系统使用了ubuntu 22.04&#xff0c; gcc是11.4&#xff0c;版本都很高&#xff0c; 用起来还存在一些问题 无法使用jtop https://forums.developer.nvidia.com/t/jtop-no-longer-works-on-jp-6-0-dp/275215 使用$ sudo -H p…

【JAVA】OPENGL+TIFF格式图片,不同阈值旋转效果

有些科学研究领域会用到一些TIFF格式图片&#xff0c;由于是多张图片相互渐变&#xff0c;看起来比较有意思&#xff1a; import java.io.IOException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.logging.*;/*** 可以自已定义日志打印格式…

Oracle数据库新手零基础入门,Oracle安装配置和操作使用详解

一、教程描述 本套教程是专门为初学者量身定制的&#xff0c;无需任何Oracle数据库基础&#xff0c;课程采用循序渐进的教学方式&#xff0c;从Oracle数据库的基础知识开始讲起&#xff0c;并不会直接涉及到一项具体的技术&#xff0c;而是随着课程的不断深入&#xff0c;一些…

基于python的leetcode算法介绍之动态规划

文章目录 零 算法介绍一 例题介绍 使用最小花费爬楼梯问题分析 Leetcode例题与思路[118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/)解题思路题解 [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)解题思路题解 [96. 不同的二叉搜索树](h…

自动驾驶预测-决策-规划-控制学习(4):预测分析文献阅读

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、摘要分析1.Transformer模型是什么&#xff1f;什么是自注意力机制&#xff1f; 2.数据集是什么&#xff1f;3.预测车辆行驶轨迹和车辆换道意图4. LSTM 网络…

Pytest成魔之路 —— fixture 之大解剖!

1. 简介 fixture是pytest的一个闪光点&#xff0c;pytest要精通怎么能不学习fixture呢&#xff1f;跟着我一起深入学习fixture吧。其实unittest和nose都支持fixture&#xff0c;但是pytest做得更炫。 fixture是pytest特有的功能&#xff0c;它用pytest.fixture标识&#xff0c…

MybatisPlus—快速入门

目录 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 1.2 定义Mapper 2.MybatisPlus常用注解 2.1 TableName 2.2 TableId 2.3 TableField 2.4 小结 3. 常用配置 4. 总结 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 MyBatisPlus官方提…

如何使用 NFTScan NFT API 在 PlatON 网络上开发 Web3 应用

PlatON 是由万向区块链和矩阵元主导开发的面向下一代的全球计算架构&#xff0c;创新性的采用元计算框架 Monad 和基于 Reload 覆盖网络的同构多链架构&#xff0c;其愿景是成为全球首个提供完备隐私保护能力的运营服务网络。它提供计算、存储、通讯服务&#xff0c;并提供算力…

软件测试|什么是Python构造方法,构造方法如何使用?

构造方法&#xff08;Constructor&#xff09;是面向对象编程中的重要概念&#xff0c;它在创建对象时用于初始化对象的实例变量。在Python中&#xff0c;构造方法是通过特殊的名称__init__()来定义的。本文将介绍Python构造方法的基本概念、语法和用法。 什么是构造方法&…

React使用动态标签名称

最近在一项目里&#xff08;React antd&#xff09;遇到一个需求&#xff0c;某项基础信息里有个图标配置&#xff08;图标用的是antd的Icon组件&#xff09;&#xff0c;该项基础信息的图标信息修改后&#xff0c;存于后台数据库&#xff0c;后台数据库里存的是antd Icon组件…

ArkTS - 网络请求

一、Axios请求 应用通过HTTP发起一个数据请求&#xff0c;支持常见的GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE、CONNECT方法。 前端开发肯定都使用过一个叫axios的第三方库&#xff0c;它是是一个基于 promise 的网络请求库&#xff0c;可以用于浏览器和 node.js&…

Rust 字符串 初步了解

rust 的字符串 。字符串不是复合类型&#xff0c; String 和 &str &#xff1a; String 具有所有权&#xff0c;是存储在堆上的。&str 没有所有权&#xff0c;是对 String 的引用。字符串字面量也是 &str 类型&#xff0c;存储在栈上。 切片&#xff08;slice&a…

Nacos与Eureka

一、前言 在构建和管理微服务架构时&#xff0c;选择适当的服务注册中心至关重要。Nacos和Eureka都是微服务体系结构中常用的服务注册和发现工具。本文将探讨它们之间的区别&#xff0c;帮助开发者在选择适合其项目需求的注册中心时做出明智的决策。 二、架构和适用场景 Nacos …