当前位置：首页 > 编程日记 > 正文

技术图文：如何实现汉诺塔问题？

编程日记 2024-09-29 01:30:00

背景

最近在辅导小孩们学习编程，在介绍函数递归时，最典型的就是汉诺塔问题了。

我在这里总结一下，以方便大家的学习。

汉诺塔问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

技术分析

如果我们要思考每一步怎么移可能会非常复杂，但是可以将问题简化。

我们可以先假设除 a 柱最下面的盘子之外，已经成功地将 a 柱上面的 63个盘子移到了 b 柱，这时我们只要再将最下面的盘子由 a 柱移动到 c 柱即可。

当我们将最大的盘子由 a 柱移到 c 柱后，b 柱上便是余下的 63 个盘子，a 柱为空。因此现在的目标就变成了将这 63 个盘子由 b 柱移到 c 柱。这个问题和原来的问题完全一样，只是由 a 柱换为了 b 柱，规模由 64 变为了 63。因此可以采用相同的方法，先将上面的 62 个盘子由 b 柱移到 a 柱，再将最下面的盘子移到 c 柱。

以此内推，再以 b 柱为缓冲，将 a 柱上面的 62 个圆盘最上面的 61 个圆盘移动到 b 柱，并将最后一块圆盘移到 c 柱。

我们已经发现规律，我们每次都是以 a 或 b 中一根柱子为缓冲，然后先将除了最下面的圆盘之外的其它圆盘移动到辅助柱子上，再将最底下的圆盘移到 c 柱子上，不断重复此过程。

这个反复移动圆盘的过程就是递归，例如我们每次想解决 n 个圆盘的移动问题，就要先解决（n-1）个盘子进行同样操作的问题。

于是可以编写一个函数，move(n, a, b, c)。可以这样理解：move(盘子数量, 起点, 缓冲, 终点)。

1. a 上只有一个盘子的情况，直接搬到 c，代码如下:

if n == 1:print(a, '-->', c)

2. a 上不止有一个盘子的情况:

首先，需要把 n-1 个盘子搬到 b 柱子缓冲。打印出的效果是：a --> b。

move(n - 1, a, c, b)

再把最大的盘子搬到 c 柱子，也是最大尺寸的一个。打印出：a–>c。

move(1, a, b, c)

最后，把剩下 b 柱的 n-1 个盘子搬到 c 上，此时缓冲变成了起点，起点变成了缓冲。

move(n - 1, b, a, c)

代码实现

Python 实现汉诺塔问题

i = 0def move(n, a, b, c):global iif (n == 1):i += 1print('移动第 {0} 次 {1} --> {2}'.format(i, a, c))returnmove(n - 1, a, c, b)move(1, a, b, c)move(n - 1, b, a, c)move(3, "a", "b", "c")  # 移动第 1 次 a --> c
# 移动第 2 次 a --> b
# 移动第 3 次 c --> b
# 移动第 4 次 a --> c
# 移动第 5 次 b --> a
# 移动第 6 次 b --> c
# 移动第 7 次 a --> c

C# 实现汉诺塔问题

class Program
{private static int i = 0;static void Move(int n, string a, string b, string c){if (n == 1){Console.WriteLine("移动第 {0} 次 {1}-->{2}", ++i, a, c);return;}Move(n - 1, a, c, b);Move(1, a, b, c);Move(n - 1, b, a, c);}static void Main(string[] args){Move(3, "a", "b", "c");}
}

输出结果

总结

我发现，把自己积累的知识教给小孩们还是很有意思的。等我们的小会议室装修好，我会开展更多的分享活动。欢迎大家来参加呀。今天就到这里吧！See You！

相关图文：

资料分享：数学建模资料分享 – 图论部分
资料分享：数学建模资料分享 – 神经网络部分
如何利用 C# 实现 K 最邻近算法？
如何利用 C# 实现 K-D Tree 结构？
如何利用 C# + KDTree 实现 K 最邻近算法？
如何利用 C# 对神经网络模型进行抽象？
如何利用 C# 实现神经网络的感知器模型？
如何利用 C# 实现 Delta 学习规则？
如何利用 C# 实现误差反向传播学习规则？
如何利用 C# 爬取带 Token 验证的网站数据？
如何利用 C# 向 Access 数据库插入大量数据？
如何利用 C# + Python 破解猫眼电影的反爬虫机制？

https://www.dkcj.cn/info/20778.html

Unity----Scene加载问题

Unity官方提供了4种加载场景（scene）的方法，分别是： 1. Application.LoadLevel()：同步加载 2. Application.LoadLevelAsync():异步加载 3. Application.LoadLevelAddictive():同步附加式加载 4. Application.LoadLevelA…

编程日记2024/09/29 01:20:00

基于Google Reader的个人知识管理方案

来源月光博客:http://www.williamlong.info/archives/2172.html. 先前我写的《基于Dropbox的个人知识管理平台》讲述了使用Dropbox在个人知识管理的保存知识方面的技巧，而个人知识管理的另一个重要环节是获取知识，今天月光博客就介绍一下如何通过Google …

编程日记2024/09/29 01:10:00

学习java一定会用到的应用软件

想要成为一名合格的java程序猿，基础知识一定是要非常牢固的，扎实的基本功不仅可以快速的吸收新的知识，也会避开一些基本的语法错误，为了帮助程序员们减少一点工作压力，小编在此汇总了一些各大网络平台上推荐的程序员必…

编程日记2024/09/29 01:00:00

题目英文 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums [2, 7, 1…

编程日记2024/09/29 00:50:00

忘记mysql 密码的取回方法

如果 MySQL 正在运行，首先杀之： killall -TERM mysqld(如果是windows,直接调出进程管理器,结束之) 以安全模式启动 MySQL ：/usr/bin/safe_mysqld --skip-grant-tables & (windows 下 mysql安装所以盘/mysql/bin/safe_mysqld --skip-grant…

编程日记2024/09/29 00:40:00

《社交网站界面设计（原书第2版）》——2.13　不要中断电子邮件

2.13　不要中断电子邮件如果你将电子邮件作为广播媒介（例如，发送提醒或通知）却不让用户回复他们收到的消息，就比较差劲了。你也没理由不处理这些回复，你可以把这些回复当作通知转发给正确的收件人。这需要你在方便沟通…

编程日记2024/09/29 00:30:00

学习Python遇到的热门问题整理

什么是Python?它可以做什么用?学习Python还是java?哪个比较好?Python适用于哪些场景?关于python，你是不是还有很多问题?那今天小编就来给大家答疑解惑了，给大家整理了学习Python遇到的热门问题，看完这篇文章，你会对Python有…

编程日记2024/09/29 00:20:00

WinRM设置信任主机

启动https需要证书，所以只能用信任主机的方式。适应没有域的环境。 enable-psremoting winrm s winrm/config/client {TrustedHosts"XXX.XXX.XXX.XXX"} 转载于:https://www.cnblogs.com/flysoft/archive/2011/03/12/1982494.html

编程日记2024/09/29 00:10:00

LeetCode实战：快乐数

题目英文 Write an algorithm to determine if a number is “happy”. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until t…

编程日记2024/09/29 00:00:00

idea的优秀博客推荐

2019独角兽企业重金招聘Python工程师标准>>> http://blog.csdn.net/qq_27093465/article/details/63683873 http://www.cnblogs.com/whc321/p/5669804.html 转载于:https://my.oschina.net/u/3621360/blog/1528716

编程日记2024/09/28 23:50:00

花钱参加UI设计培训值得吗?

最近有很多人都想要学习UI设计，大家都比较看好UI设计行业的好前景，高薪资，那么花钱参加UI设计培训值得吗?这是目前很多人都比较关心的问题，下面小编就为大家做下详细的介绍。花钱参加UI设计培训值得吗?对于零基础或者转行的人…

编程日记2024/09/28 23:40:00

零基础自学用Python 3开发网络爬虫(一)

原文出处： Jecvay Notes （Jecvay） 由于本学期好多神都选了Cisco网络课, 而我这等弱渣没选, 去蹭了一节发现讲的内容虽然我不懂但是还是无爱. 我想既然都本科就出来工作还是按照自己爱好来点技能吧, 于是我就不去了. 一个人在宿舍没有点计划…

编程日记2024/09/28 23:30:00

用什么心态对待水平糟糕的程序员[不靠谱的程序员、思路紊乱的程序员]？

这些年遇到了很多糟糕的程序员，其实真正是写程序料的人，普通IT公司大概只占1/3左右吧，其实有2/3的人都太适合当程序员，还不如早点儿改行该干啥就干啥了，其中有1/10的人往往是相对比较糟糕的。 01：招聘时&am…

编程日记2024/09/28 23:20:00

LeetCode实战：三数之和

题目英文 Given an array nums of n integers, are there elements a, b, c in nums such that a b c 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array n…

编程日记2024/09/28 23:10:00

女生做软件测试需要学习什么技术?

软件测试在近几年的发展前景是非常好的，加上软件测试对于想要零转型的学员来说是在合适不过的，有很多女性也开始学习软件测试，目前大家都比较关心女生做软件测试需要学习什么技术呢?下面我们就来看看详细的介绍。女生做软件测试需要学习什么…

编程日记2024/09/28 23:00:00

一、Axis2 WebService开发准备工作

上次介绍了axis1.x的用法，这次继续上次的，将叙述axis2的用法。 Axis1.x在线博文：http://www.cnblogs.com/hoojo/archive/2010/12/20/1911349.html 1、开发准备首先需要下载axis2的相关jar包，到axis的官方网站即可获得开发的依赖包…

编程日记2024/09/28 22:50:00

LeetCode实战：求众数

题目英文 Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: […

编程日记2024/09/28 22:40:00

oracle数据库导入导出

2019独角兽企业重金招聘Python工程师标准>>> 1、利用 sqlplus 登录数据库之后键入: 文件名全路径即可执行*.sql 文件例假设有一个 test.sql 文件所在路径是/home/oracle/ 现在要执行它 1 登录数据库 sqlplus system/m…

编程日记2024/09/28 22:30:00

学习Python编程开发可以从事的岗位有哪些?

Python编程技术在人工智能领域的发展有目共睹，很多人都想学习Python技术，而且从事Python开发，所从事的工作机会和工作岗位及工作内容可选择的余地很多，未来发展空间也很大。下面我们就来详细的了解一下学习Python编程开发可以从事…

编程日记2024/09/28 22:20:00

2010前半年

一直都想抽时间写些什么，但都是由于自己的懒惰，使得自己很少静下心来。 2010平淡的一年就这样在指缝中悄悄溜走了，我甚至都还没来得及仔细回味以往发生的一些事情，2011就已经过了好几个月。2010总体来说很平淡，我也没有…

编程日记2024/09/28 22:10:00

LeetCode实战：缺失的第一个正数

题目英文 Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3Example 2: Input: [3,4,-1,1] Output: 2Example 3: Input: [7,8,9,11,12] Output: 1Note: Your algorithm should run in O(n) time and u…

编程日记2024/09/28 22:00:00

ubuntu 下mysql导入出.sql文件

2019独角兽企业重金招聘Python工程师标准>>> 1.导出整个数据库 mysqldump -u 用户名 -p 数据库名 > 导出的文件名 mysqldump -u wcnc -p waf> /home/waf.sql 2.导出一个表 mysqldump -u 用户名 -p 数据库名表名> 导出的文件名 mysqldump -u wcnc -p waf u…

编程日记2024/09/28 21:50:00

UI设计师培训入门都需要学习什么技术?

UI设计在如今的IT行业是非常火热的，它的发展前景是非常可观的，想要进入到这个行业的小伙伴越来越多，那么UI设计师培训入门都需要学习什么技术呢?小编下面为大家做下详细的介绍。 UI设计师培训入门都需要学习什么技术? 一、视觉设计基础&…

编程日记2024/09/28 21:40:00

[C#1] 9-委托

委托揭秘编译器和CLR在后台做了很多工作来隐藏委托本身的复杂性，如下一句委托声明： //编译器为我们产生了一个同名的类 public delegate void MyDelegate(int i); 看看IL: 可以看出它默认继承自System.MulticastDelegate[所有委托都继承此类&#xff0c…

编程日记2024/09/28 21:30:00

LeetCode实战：环形链表

题目英文 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycl…

编程日记2024/09/28 21:20:00