【汉诺塔 —— (经典分治递归)】
汉诺塔 —— (经典分治递归)
- 一.汉诺塔介绍
- 二.分治算法解决汉诺塔问题
- 三.汉诺塔问题的代码实现
- 四.主函数测试展示
一.汉诺塔介绍
汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则:
每次只能移动柱子最顶端的一个圆盘;
每个柱子上,小圆盘永远要位于大圆盘之上;
图 1 给您展示了包含 3 个圆盘的汉诺塔问题:
图 1 汉诺塔问题
一根柱子上摞着 3 个不同大小的圆盘,那么在不违反规则的前提下,如何将它们移动到另一个柱子上呢?图 2 给大家提供了一种实现方案:
图 2 汉诺塔问题的解决方案
汉诺塔问题中,3 个圆盘至少需要移动 7 次,移动 n 的圆盘至少需要操作 2n-1 次。
在汉诺塔问题中,当圆盘个数不大于 3 时,多数人都可以轻松想到移动方案,随着圆盘数量的增多,汉诺塔问题会越来越难。也就是说,圆盘的个数直接决定了汉诺塔问题的难度,解决这样的问题可以尝试用分治算法,将移动多个圆盘的问题分解成多个移动少量圆盘的小问题,这些小问题很容易解决,从而可以找到整个问题的解决方案。
二.分治算法解决汉诺塔问题
为了方便讲解,我们将 3 个柱子分别命名为起始柱、目标柱和辅助柱。实际上,解决汉诺塔问题是有规律可循的:
1) 当起始柱上只有 1 个圆盘时,我们可以很轻易地将它移动到目标柱上;
2) 当起始柱上有 2 个圆盘时,移动过程如下图所示:
图 3 移动两个圆盘
移动过程是:先将起始柱上的 1 个圆盘移动到辅助柱上,然后将起始柱上遗留的圆盘移动到目标柱上,最后将辅助柱上的圆盘移动到目标柱上。
3) 当起始柱上有 3 个圆盘时,移动过程如图 2 所示,仔细观察会发现,移动过程和 2 个圆盘的情况类似:先将起始柱上的 2 个圆盘移动到辅助柱上,然后将起始柱上遗留的圆盘移动到目标柱上,最后将辅助柱上的圆盘移动到目标柱上。
通过分析以上 3 种情况的移动思路,可以总结出一个规律:对于 n 个圆盘的汉诺塔问题,移动圆盘的过程是:
1.将起始柱上的 n-1 个圆盘移动到辅助柱上;
2.将起始柱上遗留的 1 个圆盘移动到目标柱上;
3.将辅助柱上的所有圆盘移动到目标柱上。
由此,n 个圆盘的汉诺塔问题就简化成了 n-1 个圆盘的汉诺塔问题。按照同样的思路,n-1 个圆盘的汉诺塔问题还可以继续简化,直至简化为移动 3 个甚至更少圆盘的汉诺塔问题。
三.汉诺塔问题的代码实现
//将n个圆盘借助by从from移到to
void hanoi(int n, char from, char to, char by)
{void move(int n, char x, char y);if (n == 1)move(n, from, to);else{hanoi(n - 1, from, by, to);move(n, from, to);hanoi(n - 1, by, to, from);}
}void move(int n, char x, char y)
{printf("第%d个圆盘从%c->%c\n", n, x, y);
}int main() {int n = 0;printf("请输入A柱上圆盘个数:");scanf("%d", &n);//将n个圆盘借助C从A移到Bprintf("移动方法展示:\n");hanoi(n, 'A', 'B', 'C');return 0;
}
四.主函数测试展示


相关文章:
【汉诺塔 —— (经典分治递归)】
汉诺塔 —— (经典分治递归) 一.汉诺塔介绍二.分治算法解决汉诺塔问题三.汉诺塔问题的代码实现四.主函数测试展示 一.汉诺塔介绍 汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一…...
APP运营常用的ChatGPT通用提示词模板
用户获取:请帮助我制定一个用户获取计划,包括目标用户群体、获取渠道、营销策略等方面的内容。 用户留存:我们希望提高用户的留存率,请帮助我分析用户流失的原因,并提供一些留存策略和措施。 用户活跃度:…...
医学检验(LIS)管理系统源码,LIS源码,云LIS系统源码
医学检验(LIS)管理系统源码,云LIS系统全套商业源码 随着全自动生化分析仪、全自动免疫分析仪和全自动血球计数器等仪器的使用,检验科的大多数项目实现了全自动化分析。全自动化分析引入后,组合化验增多,更好的满足了临床需要&…...
RabbitMQ 安装(在docker容器中安装)
为什么要用? RabbitMQ是一个开源的消息代理和队列服务器,主要用于在不同的应用程序之间传递消息。它实现了高级消息队列协议(AMQP),并提供了一种异步协作机制,以帮助提高系统的性能和扩展性。 RabbitMQ的作…...
机器学习入门
简介 https://huggingface.co/是一个AI社区,类似于github的地位。它开源了许多机器学习需要的基础组件如:Transformers, Tokenizers等。 许多公司也在不断地往上面提交新的模型和数据集,利用它你可以获取以下内容: Datasets : 数…...
HarmonyOS ArkTS 保存应用数据(十)
1 概述 在移动互联网蓬勃发展的今天,移动应用给我们生活带来了极大的便利,这些便利的本质在于数据的互联互通。因此在应用的开发中数据存储占据了非常重要的位置,HarmonyOS应用开发也不例外。 2 什么是首选项 首选项为应用提供Key-Value键…...
【JavaEE】Spring更简单的存储和获取对象(类注解、方法注解、属性注入、Setter注入、构造方法注入)
一、存储Bean对象 在这篇文章中我介绍了Spring最简单的创建和使用:Spring的创建和使用 其中存储Bean对象是这样的: 1.1 配置扫描路径 想要成功把对象存到Spring中,我们需要配置对象的扫描包路径 这样的话,就只有被配置了的包…...
linux上的通用拍照程序
最近因为工作需要,在ubuntu上开发了一个拍照程序。 为了找到合适的功能研究了好几种实现方式,在这里记录一下。 目录 太长不看版 探索过程 v4l2 QT opencv4.2 打开摄像头 为什么不直接打开第一个视频节点 获取所有分辨率 切换摄像头 太长不看…...
代码随想录-刷题第七天
454. 四数相加II 题目链接:454. 四数相加II 思路:哈希法。使用map集合,key存放ab的值,value存放ab出现的次数。使用两层循环,循环前两个数组,找出ab,对map赋值。再用两层循环,遍历…...
C# 获取图像、字体等对象大小的数据结构SizeF
如果你想要获取字符串 "你好吗" 的字节数组长度或者字符数, 使用如下代码: string s "你好吗"; //字节数组长度 int byteCount System.Text.Encoding.UTF8.GetBytes(s).Length; //字符数 int charCount s.Length; 如果你想获取…...
「 系统设计 」 为什么要做架构分层?
「 系统设计 」 为什么要做架构分层? 参考&鸣谢 3.设计模式之分层思维:为什么要做代码分层架构? 从零开始学架构(八)分层架构和设计模式 架构模式之分层架构总结 文章目录 「 系统设计 」 为什么要做架构分层&…...
4:kotlin 方法(Functions)
想要声明一个函数需要使用fun关键字 fun hello() {return println("Hello, world!") }fun main() {hello()// Hello, world! }格式: fun 方法名(参数1: 参数1类型, 参数2 : 参数2类型, ...): 返回值类型 {方法体return 返回值 }fun 方法名(参数1: 参数1类型, 参数2…...
Pycharm run 输出界面控制一行能够输出的元素个数
Pycharm run 输出界面控制一行能够输出的元素个数 今天遇到了一个问题,当我们在 Pycharm 中打印输出数组时,如果数组一行的元素个数过多,那么我们在打印时就会出现以下问题。 代码如下: import numpy as npx np.array([[0., 0.7…...
C++初级项目webserver项目流程介绍(2)
一、引言 C的webserver项目是自己在学完网络编程后根据网课的内容做的一个初级的网络编程项目。 这个项目的效果是可以在浏览器通过输入网络IP地址和端口,然后打开对应的文件目录 效果如下: 也可以打开文件夹后点击目录,打开到对应的文件夹…...
SIPp mac和debian用法可能略有差别
<ereg regexp"<(.*)>" search_in"hdr" header"Contact:" check_it"true" assign_to"dummy,remote_contact"/> debian没事,但mac报错 <变< >变> 就都冇问题了 https://github.…...
echarts的横向柱状图文字省略,鼠标移入显示内容 vue3
效果图 文字省略 提示 如果是在x轴上的,就在x轴上添加triggerEvent: true,如果是y轴就在y轴添加,我是在y轴上添加的 并且自定义的方法(我取名为extension) // echarts 横向省略文字 鼠标移入显示内容 export const extension…...
laravel8安装多应用多模块(笔记三)
先安装laravel8 Laravel 安装(笔记一)-CSDN博客 一、进入项目根目录安装 laravel-modules composer require nwidart/laravel-modules 二、 大于laravel5需配置provider,自动生成配置文件 php artisan vendor:publish --provider"Nwid…...
Vue组件的几种通信方式
这里写目录标题 Vue组件的几种通信(数据传递)方式非父子组件间通信(Bus事件总线)介绍实例 非父子通信-provide&inject1.作用2.场景3.语法4.注意 父子组件间的通信固定props属性名(v-model)介绍实例 不固…...
golang panic关键词执行原理与代码分析
使用的go版本为 go1.21.2 首先我们写一个简单的panic调度与捕获代码 package mainfunc main() {defer func() {recover()}()panic("panic test") }通过go build -gcflags -S main.go获取到对应的汇编代码 可以看到当我们调度panic时,Go的编译器会将这段…...
Error running Tomcat8: Address localhost:1099 is already in use 错误解决
摘要: 有时候运行web项目的时候会遇到 Error running Tomcat8: Address localhost:1099 is already in use 的错误,导致web项目无法运行。这篇 blog 介绍了解决办法。 有时候运行web项目的时候会遇到 Error running Tomcat8: Address localhost:1099 is already in …...
Fluent环境变量配置全攻略:从udf.bat到setenv.exe,哪种方法最适合你?
Fluent环境变量配置方法论:四种方案的技术解构与场景化决策指南 当你在深夜的实验室里第三次重装Fluent和Visual Studio,编译UDF时依然弹出那个令人绝望的错误提示——这可能是每个CFD工程师都经历过的"成人礼"。环境变量配置这个看似基础的操…...
别再只调PID了!从一场起重机大赛看机器人设计的系统思维:结构、电源与控制的平衡艺术
从起重机大赛看机器人设计的系统思维:结构、电源与控制的平衡艺术 在机器人设计领域,我们常常陷入对单一技术点的过度关注——比如如何优化PID参数、选择哪种传感器、使用什么控制算法。然而,真正决定一个机器人系统成败的,往往是…...
RISC-V架构——物理内存保护(PMP)实战:从配置寄存器到安全区域设定
1. 初识RISC-V PMP:为什么需要物理内存保护? 第一次接触RISC-V的物理内存保护(PMP)功能时,我正为一个嵌入式项目调试内存越界问题。当时应用程序意外改写了关键配置区,导致系统崩溃。这种"手滑"操…...
别再只盯着CPU%了!htop里VIRT、RES、SHR内存三兄弟,到底哪个数字才该让你紧张?
别再只盯着CPU%了!htop里VIRT、RES、SHR内存三兄弟,到底哪个数字才该让你紧张? 当服务器突然发出内存告警,大多数工程师的第一反应是打开htop,然后盯着MEM%那一栏开始"抓凶手"。但很快你会发现,有…...
用Python和TensorFlow搞定PINN:从Burgers方程到Navier-Stokes的保姆级代码实战
用Python和TensorFlow搞定PINN:从Burgers方程到Navier-Stokes的保姆级代码实战 在工程计算和科学模拟领域,偏微分方程(PDE)的求解一直是核心挑战。传统数值方法如有限元、有限体积法虽然成熟,但面对复杂边界条件或高维…...
哨兵2号 vs Landsat 8:10米和30米分辨率下,GEE提取水体结果差异有多大?
哨兵2号与Landsat 8水体提取实战对比:分辨率差异如何影响监测精度? 当我们需要监测湖泊、河流或湿地时,卫星遥感无疑是最经济高效的选择。但在实际操作中,面对哨兵2号的10米分辨率和Landsat 8的30米分辨率,很多研究者都…...
3步解锁AMD Ryzen终极性能:SMUDebugTool硬件调试全攻略
3步解锁AMD Ryzen终极性能:SMUDebugTool硬件调试全攻略 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https://g…...
BetterJoy深度解析:Switch控制器在PC平台的完全指南
BetterJoy深度解析:Switch控制器在PC平台的完全指南 【免费下载链接】BetterJoy Allows the Nintendo Switch Pro Controller, Joycons and SNES controller to be used with CEMU, Citra, Dolphin, Yuzu and as generic XInput 项目地址: https://gitcode.com/gh…...
3秒解锁百度网盘资源:智能提取码查询工具完全指南
3秒解锁百度网盘资源:智能提取码查询工具完全指南 【免费下载链接】baidupankey 项目地址: https://gitcode.com/gh_mirrors/ba/baidupankey 还在为百度网盘分享链接的提取码而烦恼吗?每次看到心仪的学习资料、软件资源或影音文件,却…...
无感FOC方案怎么选?深入对比STM32F4上的滑膜、磁链与隆伯格观测器
无感FOC方案选型指南:STM32F4平台三大观测器深度对比 在电机控制领域,无传感器FOC(Field-Oriented Control)技术正逐渐成为主流选择。特别是在STM32F4这类高性能MCU平台上,工程师们面临着多种观测器方案的抉择。本文将…...



