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

数据结构递归(01)汉诺塔经典问题

说明:使用递归时,必须要遵守两个限制条件:

  1. 递归存在限制条件,满⾜这个限制条件时,递归不再继续;
  2. 每次递归调⽤之后越来越接近这个限制条件;

1 汉诺塔(Hanoi Tower)经典问题

1.1 汉诺塔问题描述

汉诺塔(Hanoi Tower)问题是一个经典的递归问题,起源于一个关于印度的传说。问题描述如下:

有一个三脚架,上面有三个从下到上依次递减的圆盘,总共有n个圆盘,这些圆盘最初都放在第一个柱子上,并且每个圆盘上都有不同的大小,使得较大的圆盘不能放在较小的圆盘上面。任务是将所有圆盘从第一个柱子移动到第三个柱子,同时满足以下规则:

  1. 每次只能移动一个圆盘。
  2. 每次移动的圆盘必须放在另一个柱子的顶部。
  3. 任何时候,较大的圆盘不能放在较小的圆盘上面。

1.2 汉诺塔问题分析

汉诺塔问题的分析可以通过递归的方式来理解。下面是针对n=1, n=2, n=3时的步骤说明(其中ABC分别对应第一二三个柱子):

#n=1时:
初始状态     第一步(完成)      
A B C       A B C
1 0 0       0 0 1   #n=2时:
初始状态     第一步       第二步       第三步(完成)
A B C       A B C       A B C       A B C
1 0 0       0 1 0       0 1 0       0 0 1
2 0 0       2 0 0       0 0 2       0 0 2#n=3时:
说明:由n=2时的状态可知,2个盘从A移动到B或C均是可行的,那么这里我们就将1和2堪称整体。
初始状态     第一步       第二步       第三步(完成)
A B C       A B C       A B C       A B C
1 0 0       0 1 0       0 1 0       0 0 1
2 0 0       0 2 0       0 2 0       0 0 2
3 0 0       3 0 0       0 0 3       0 0 3可以看到,这里的第一步和第三步实际上是使用了n=2时的结论。接下来我们把2 3换成出n-1 n之间的关系。
初始状态     第一步       第二步       第三步(完成)
A B C       A B C       A B C       A B C
1 0 0       0 1 0       0 1 0       0 0 1
2 0 0       0 2 0       0 2 0       0 0 2
3 0 0       0 3 0       0 3 0       0 0 3
...         ...         ...         ...
n 0 0       n 0 0       0 0 n       0 0 n

可以看出来,实际上和2与3 的关系是一致的。因此我们使用递归公式的分析进阶思考:

  • 对于n个圆盘,将前n-1个圆盘从A柱移动到B柱,使用辅助柱C。
  • 将第n个圆盘从A柱移动到C柱。
  • 将n-1个圆盘从B柱移动到C柱,使用辅助柱A。

这个递归过程会不断重复,直到所有的圆盘都按照规则成功地移动到目标柱子上。递归的深度是n-1,因为每次移动n-1个圆盘,然后是第n个圆盘,再是n-1个圆盘。总共需要进行2^n - 1次移动才能完成n个圆盘的汉诺塔问题。

1.3 汉诺塔问题 逻辑解决方案

解决汉诺塔问题的方法是递归。对于n个圆盘,解决步骤可以概括为:

  1. 将上面的n-1个圆盘从起始柱子移动到辅助柱子(不违反规则)。
  2. 将最大的圆盘(第n个圆盘)从起始柱子移动到目标柱子。
  3. 将n-1个圆盘从辅助柱子移动到目标柱子(现在最大的圆盘已经在目标柱子上,不违反规则)。

这个过程可以继续递归地应用到n-1个圆盘上,直到n为1,这时问题就变得非常简单,只需将圆盘直接移动到目标柱子上。

2 代码实现

2.1 python代码实现

#!/usr/bin/python3
# -*- coding: UTF-8 -*-def hanoi(n, source, target, auxiliary):if n > 0:# 将n-1个圆盘从source移动到auxiliary,以target作为辅助hanoi(n-1, source, auxiliary, target)# 将第n个圆盘从source移动到targetprint(f"Move disk {n} from {source} to {target}")# 将n-1个圆盘从auxiliary移动到target,以source作为辅助hanoi(n-1, auxiliary, target, source)# 调用函数,将3个圆盘从A柱移动到C柱,B柱作为辅助
hanoi(3, 'A', 'C', 'B')

2.2 C++代码实现

#include <iostream>// 函数声明
void hanoi(int n, char source, char target, char auxiliary);int main() {int numDisks = 3; // 圆盘的数量hanoi(numDisks, 'A', 'C', 'B'); // 将3个圆盘从A柱移动到C柱,B柱作为辅助return 0;
}// 函数定义
void hanoi(int n, char source, char target, char auxiliary) {if (n <= 0) return; // 递归的基本情况// 将n-1个圆盘从source移动到auxiliary,以target作为辅助hanoi(n - 1, source, auxiliary, target);// 将第n个圆盘从source移动到targetstd::cout << "Move disk " << n << " from " << source << " to " << target << std::endl;// 将n-1个圆盘从auxiliary移动到target,以source作为辅助hanoi(n - 1, auxiliary, target, source);
}

相关文章:

数据结构递归(01)汉诺塔经典问题

说明&#xff1a;使用递归时&#xff0c;必须要遵守两个限制条件&#xff1a; 递归存在限制条件&#xff0c;满⾜这个限制条件时&#xff0c;递归不再继续&#xff1b; 每次递归调⽤之后越来越接近这个限制条件&#xff1b; 1 汉诺塔&#xff08;Hanoi Tower&#xff09;经典…...

计算机专业课面试常见问题-计算机网络篇

目录 1. 计算机网络分为哪 5 层&#xff1f; 2. TCP 协议简述&#xff1f; 3. TCP 和 UDP 的区别&#xff1f;->不同的应用场景&#xff1f; 4. 从浏览器输入网址到显示页…...

HarmonyOS ArkUi ArkWeb加载不出网页问题踩坑

使用 使用还是比较简单的&#xff0c;直接贴代码了 别忘了配置网络权限 Entry Component struct WebPage {State isAttachController: boolean falseState url: string State title: string Prop controller: web_webview.WebviewController new web_webview.WebviewCont…...

微信换手机号了怎么绑定新手机号?

微信换手机号了怎么绑定新手机号&#xff1f; 1、在手机上找到并打开微信&#xff1b; 2、打开微信后&#xff0c;点击底部我的&#xff0c;并进入微信设置&#xff1b; 3、在微信设置账号与安全内&#xff0c;找到手机号并点击进入&#xff1b; 4、选择更换手机号&#xff0c…...

64.WEB渗透测试-信息收集- WAF、框架组件识别(4)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;63.WEB渗透测试-信息收集- WAF、框架组件识别&#xff08;3&#xff09;-CSDN博客 我们在…...

java.lang.LinkageError: 链接错误的正确解决方法,亲测有效,嘿嘿,有效

文章目录 问题分析报错原因解决思路解决方法&#xff08;含代码示例&#xff09;1. 检查类加载器2. 避免在运行时修改类定义3. 更新或修复 JVM4. 检查应用程序的依赖使用 Maven 检查依赖项使用 Gradle 检查依赖项 java.lang.LinkageError 是 Java 虚拟机在尝试链接类定义时发生…...

python最基础

基本的类 python最基础、最常用的类主要有int整形&#xff0c;float浮点型&#xff0c;str字符串&#xff0c;list列表&#xff0c;dict字典&#xff0c;set集合&#xff0c;tuple元组等等。int整形、float浮点型一般用于给变量赋值&#xff0c;tuple元组属于不可变对象&#…...

Python学习路线图(2024最新版)

这是我最开始学Python时的一套学习路线&#xff0c;从入门到上手。&#xff08;不敢说精通&#xff0c;哈哈~&#xff09; 一、Python基础知识、变量、数据类型 二、Python条件结构、循环结构 三、Python函数 四、字符串 五、列表与元组 六、字典与集合 最后再送给大家一套免费…...

66、基于长短期记忆 (LSTM) 网络对序列数据进行分类

1、基于长短期记忆 (LSTM) 网络对序列数据进行分类的原理及流程 基于长短期记忆&#xff08;LSTM&#xff09;网络对序列数据进行分类是一种常见的深度学习任务&#xff0c;适用于处理具有时间或序列关系的数据。下面是在Matlab中使用LSTM网络对序列数据进行分类的基本原理和流…...

RabbitMQ消息可靠性等机制详解(精细版三)

目录 七 RabbitMQ的其他操作 7.1 消息的可靠性(发送可靠) 7.1.1 confim机制(保证发送可靠) 7.1.2 Return机制(保证发送可靠) 7.1.3 编写配置文件 7.1.4 开启Confirm和Return 7.2 手动Ack(保证接收可靠) 7.2.1 添加配置文件 7.2.2 手动ack 7.3 避免消息重复消费 7.3.…...

88888

49615...

深度学习之激活函数

激活函数的公式根据不同的函数类型而有所不同。以下是一些常见的激活函数及其数学公式&#xff1a; Sigmoid函数&#xff1a; 公式&#xff1a;f(x)特性&#xff1a;输出范围在0到1之间&#xff0c;常用于二分类问题&#xff0c;将输出转换为概率值。但存在梯度消失问题&#…...

OpenStack开源虚拟化平台(一)

目录 一、OpenStack背景介绍&#xff08;一&#xff09;OpenStack是什么&#xff08;二&#xff09;OpenStack的主要服务 二、计算服务Nova&#xff08;一&#xff09;Nova组件介绍&#xff08;二&#xff09;Libvirt简介&#xff08;三&#xff09;Nova中的RabbitMQ解析 OpenS…...

C++ | Leetcode C++题解之第207题课程表

题目&#xff1a; 题解&#xff1a; class Solution { private:vector<vector<int>> edges;vector<int> indeg;public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCo…...

vue3中的自定义指令

全局自定义指令 假设我们要创建一个全局指令v-highlight&#xff0c;用于高亮显示元素。这个指令将接受一个颜色参数&#xff0c;并有一个可选的修饰符bold来决定是否加粗文本。 首先&#xff0c;在创建Vue应用时定义这个指令&#xff1a;&#xff08;这里可以将指令抽离成单…...

Postman接口测试工具的原理及应用详解(一)

本系列文章简介&#xff1a; 在当今软件开发的世界中&#xff0c;接口测试作为保证软件质量的重要一环&#xff0c;其重要性不言而喻。随着前后端分离开发模式的普及&#xff0c;接口测试已成为连接前后端开发的桥梁&#xff0c;确保前后端之间的数据交互准确无误。在这样的背景…...

C++ initializer_list类型推导

目录 initializer_list C自动类型推断 auto typeid decltype initializer_list<T> C支持统一初始化{ }&#xff0c;出现了一个新的类型initializer_list<T>&#xff0c;一切类型都可以用列表初始化。提供了一种更加灵活、安全和明确的方式来初始化对象。 class…...

造一个交互式3D火山数据可视化

本文由ScriptEcho平台提供技术支持 项目地址&#xff1a;传送门 使用 Plotly.js 创建交互式 3D 火山数据可视化 应用场景 本代码用于将火山数据库中的数据可视化&#xff0c;展示火山的高度、类型和状态。可用于地质学研究、教育和数据探索。 基本功能 该代码使用 Plotly…...

【网络安全】一文带你了解什么是【CSRF攻击】

CSRF&#xff08;Cross-Site Request Forgery&#xff0c;跨站请求伪造&#xff09;是一种网络攻击方式&#xff0c;它利用已认证用户在受信任网站上的身份&#xff0c;诱使用户在不知情的情况下执行恶意操作。具体来说&#xff0c;攻击者通过各种方式&#xff08;如发送恶意链…...

短视频电商源码如何选择

在数字时代的浪潮下&#xff0c;短视频电商以其直观、生动、互动性强的特点&#xff0c;迅速崛起成为电商行业的一股新势力。对于有志于进军短视频电商领域的创业者来说&#xff0c;选择一款合适的短视频电商源码至关重要。本文将从多个角度探讨如何选择短视频电商源码&#xf…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...