C语言修炼——汉罗塔问题与函数递归
目录一、汉罗塔问题1.介绍2.讲解二、编程中的汉罗塔问题1.代码概览2.详解代码一、汉罗塔问题1.介绍汉诺塔问题是一个经典的问题。汉诺塔Hanoi Tower又称河内塔源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把所有圆盘移到另一根柱子上。并且规定任何时候在小圆盘上都不能放大圆盘且一次只能搬动一个圆盘。问应该如何操作搬动次数最少2.讲解假设我们有A、B、C三根石柱其中A为起始石柱B为中转石柱C为目的石柱。如果A上有一个圆盘我们可以直接将A上圆盘移到C上即A-C共1步如果A上有两个圆盘我们需要借助中转石柱即B石柱先将A上小圆盘移到B上再将A上大圆盘移到C上最后将之前移到B上的小圆盘移到C上即A-B A-C B-C共3步如果A上有三个圆盘我们首先将小圆盘移到C上接着中圆盘移到B后小圆盘再次移到B然后大圆盘移到C接着小圆盘移到A后中圆盘移到C最后小圆盘移到C即A-C A-B C-B A-C B-A B-C A-C共7步。…以此类推最小移动次数总为2^n-1n为圆盘总个数。需注意为取最小移动次数在实际移动时当圆盘总数为偶数时我们将第一个圆盘即最小圆盘先移到B当圆盘总数为奇数时则先移到C。二、编程中的汉罗塔问题现在我们想要编写一个程序输入n值代表起始石柱上圆盘总数然后让程序打印出移动步骤来帮助我们完成搬运工作。1.代码概览#includestdio.hMove(charpos1,charpos3)//打印移动步骤{printf(%c-%c ,pos1,pos3);}Hanio(intn,charpos1,charpos2,charpos3)//pos1起始石柱pos2中转石柱pos3目的石柱{if(n1){Move(pos1,pos3);}else{Hanio(n-1,pos1,pos3,pos2);//交换pos2,pos3Move(pos1,pos3);Hanio(n-1,pos2,pos1,pos3);//交换pos1,pos2}}intmain(){intn0;scanf(%d,n);Hanio(n,A,B,C);return0;}运行结果2.详解代码我们来看看这段代码是如何实现的先来看一张动图以4个圆盘为例上图可以分为三个阶段借pos3将pos1最上面3个圆盘转移到pos2交换pos1、pos3将最大的圆盘从pos1移至pos3借pos1将pos2上3个圆盘移至pos3上。其实到此我们已经说出了这段代码的精髓了。上面我们提到1个圆盘是A-C2个圆盘是A-B | A-C | B-C3个圆盘是A-C A-B C-B | A-C | B-A B-C A-C4个圆盘是A-B A-C B-C A-B C-A C-B A-B | A-C | B-C B-A C-A B-C A-B A-C B-C…易知除了1个圆盘外我们都可以用|划分出这三个阶段。1Hanio(intn,charpos1,charpos2,charpos3)2{3if(n1)4{5Move(pos1,pos3);6}7else8{9Hanio(n-1,pos1,pos3,pos2);10Move(pos1,pos3);11Hanio(n-1,pos2,pos1,pos3);12}13}所以我们构造分支如果n1则直接将圆盘从A搬到C如果n1,则else第9行为第一阶段第10行为第二阶段第11行为第三阶段。以n3为例运行逻辑如下所谓大事化小事这是递归的意义所在可以化繁为简。而图片中的’小事‘就是前文的三个阶段即第一层递归的三个支线其中的两个Hanio支线又可以细分、往复下去。可以发现一开始从外到内Hanio函数一直都是在传递形参即‘递’ 直到n1时才进入‘归’这时这种循环往复从内到外继续进行。再深思这种循环往复归根其实是pos1、pos2、pos3的循环往复。建议大家对着运行逻辑图拿纸笔将每一次交换都按顺序写下来用心领悟试着去分析一下个例搞透了整体思想也就容易理解了最终递归我们也就拿捏了。其实简单地讲递归无非就是一个从外‘递’至内从内‘归’回外的过程我们需要的只是明确递的是什么归的是什么这样就很容易理解汉罗塔问题了。

相关新闻

游戏剧情本地化实战:从编码转换到字幕与字体适配

游戏剧情本地化实战:从编码转换到字幕与字体适配

最近在整理日服活动剧情相关的本地化资料时,发现很多同学第一次接触这类文本,卡得最多的并不是剧情翻译本身,而是“文件打不开”“打开后全是乱码”“中文字体显示成方块”。尤其在面对《Dive into Ocean》这种以活动剧情、角色对话和演出文本…

2026/11/21 8:47:07 阅读更多 →
VRChat密室解谜闯关指南:BACK-SPACE第1/2部完整通关与性能排查

VRChat密室解谜闯关指南:BACK-SPACE第1/2部完整通关与性能排查

这一期,我们来聊 VRChat 里一个比较耐玩的闯关世界:BACK-SPACE 的第 1 部和第 2 部。如果你对 VR 社交、密室解谜、以及和小伙伴一起在虚拟空间里合作通关感兴趣,这篇文章可以直接收藏。它不会跟你讲太多虚的,我会按“进世界前要准…

2026/11/18 16:18:21 阅读更多 →
ArcEngine栅格与矢量渲染原理及协同优化实战

ArcEngine栅格与矢量渲染原理及协同优化实战

1. 这不是“调个颜色”那么简单:ArcEngine栅格与矢量图层渲染的本质矛盾很多人第一次在ArcEngine里点开图层属性,看到“符号系统”选项卡时,下意识觉得:“不就是换个颜色嘛,拖个色块、选个渐变,三分钟搞定。…

2026/11/20 4:21:52 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻