汉诺塔问题的两种解法(3)

第三节 汉诺塔的递归解法——移动两个盘子

一、用户界面

在App Inventor中创建一个项目,命名为汉诺塔,用户界面在手机中的样子如图11所示,在AppInventor设计视图中,为项目添加组件,如图12所示。各个组件的属性设置如表1所示。

图11 程序的用户界面

图12 设计视图中的汉诺塔项目

表1 组件的属性设置

屏幕顶部的标签用于跟踪移动步数,并提示任务完成时的移动步数。屏幕中部的水平布局组件中有三个标签,分别显示程序运行过程中起点、缓冲区及终点的数字。屏幕底部的水平布局组件中有三个组件,其中的文本输入框用于输入盘子的总数(命名为最大值),开始按钮用于从头开始移动盘子,暂停按钮可以在程序运行时,让程序暂停运行,再次点击该按钮时,程序将继续运行。

这里我们用数字来表示盘子,数字自上而下按照从小到大的顺序排列,数字从一个区域移动到另一个区域时,每次只能移动一个数字,且大的数字不能置于小的数字之上,这些符合汉诺塔游戏的规则。我们的目标是,将一串数字从屏幕的左边移动到屏幕的右边。用数字替代盘子,这是我们将物理世界的问题转化为数学问题的第一步。下面我们来编写移动两个盘子,也就是两个数字的程序。

二、数据模型及初始化

我们用三个列表来分别保存起点、缓冲区及终点的数字,通过对列表中第一个元素的移动,来模拟盘子的移动。假设有5个盘子,则最初左侧(起点)的列表中有5个元素,分别是1~5的整数,中间(缓冲区)及右侧(终点)的列表为空。

切换到App Inventor编程视图,声明3个全局变量——左、中、右,初始值为空列表。

接下来做一点准备工作,创建一个初始化过程,为三个全局变量列表赋初始值,代码如图13所示。在每次点击开始按钮时,都会首先执行该过程,为此,必须先将左中右三个列表清空,再对左列表赋值。

图13 初始化过程

再创建一个有返回值的过程——列表转字串,将由数字组成的列表转化为纵向排列的字符串,代码如图14所示。

图14 有返回值的过程——列表转字串

再创建一个过程——显示结果,将左中右三个列表的内容显示在标签中,代码如图15所示。

图15 过程——显示结果

最后,在开始按钮的点击事件中调用上述过程,代码如图16所示,程序测试结果如图17所示。

图16 在开始按钮的点击事件中初始化并显示列表内容

图17 测试:初始化并显示列表内容

三、移动一个数字

要将出发点列表中的第1项移动到落脚点列表的首位,需要判断落脚点列表中是否有列表项,如果有,那么第1项是否大于出发点的第1项,为此,先创建一个有返回值的过程——首项,代码如图18所示。

图18 有返回值的过程——首项

图18中的全局变量“空表最大值”远远超过了三个列表的长度,表明列表为空,可以移入左中右三个列表中的任何数字(这个方法是陶陶同学的主意)。

然后创建过程——移动1,实现列表之间数字的移动,代码如图19所示。

图19 移动数字的过程

这里先借用暂停按钮测试上面的程序,代码如图20所示。读者可以自行测试程序的运行效果。

图20 测试移动一个数字

四、移动两个数字

我们的目标是:从左侧的列表中将1和2移动到右侧列表中,按照我们此前的分析,2个元素(盘子或数字)从出发点移动到落脚点,需要三个步骤:

  1. 小的从出发点移至缓冲区;

  2. 大的从出发点移至落脚点;

  3. 小的再从缓冲区移至落脚点。

创建一个过程——移动2,来完成上述三个步骤。仍然借用暂停按钮实现移动操作,代码如图21所示。请读者自行测试程序的执行结果。

图21 连续移动两个数字

注意理解移动2过程的参数,S表示移动的出发点,B表示移动的缓冲区,T表示移动的落脚点,它们表示的都是相对位置。图21中,在暂停按钮的点击事件中调用移动2时,所提供的参数恰好与绝对位置相一致。不过在后面的程序中,移动2的出发点可能是绝对位置的起点、终点或缓冲区,同样,移动2的参数B可能是绝对的起点、终点或绝对缓冲区,参数T亦然。这一点希望读者能够明了。

== 未完待续 ==

(0)

相关推荐

  • 汉诺塔问题,五个盘子具体走法

    我移了三盘的和四盘的,就是推不出五盘的...笨嘛...等指教 1个回答 满意答案 fatso1118 推荐于 2017.12.15 五个柱子!分别为1号 2号 3号 五个盘子 A B C D E 这样 ...

  • 关于C语言汉诺塔问题,当程序执行到001、002、003步时,不知道具体是个什么步骤,求大神解惑!

    关于C语言汉诺塔问题,当程序执行到001.002.003步时,不知道具体是个什么步骤,求大神解惑! 狼首破vtb8452016.06.12浏览17次其他分享举报 #include<stdio.h ...

  • Py:递归求解汉诺塔,简单的几行编程可以搞定很高层的三柱汉诺塔游戏

    Py:递归求解汉诺塔,简单的几行编程可以搞定很高层的三柱汉诺塔游戏 输出结果 核心代码 def hanoi(n,x,y,z): if n==1: print(x,'--→',z) else: hano ...

  • 如何玩八层的汉诺塔?

    8层汉诺塔共有: 2^8 - 1 = 255个步骤 以下是移动的过程:(说明: A表示第一个柱子   B表示第二个珠子  C表示第三个柱子  -->表示盘的移动方向) 对于汉诺塔问题的求解,可以 ...

  • 汉诺塔算法

    汉诺塔算法 ----C++语言递归实现 线上幽灵 2018-04-24 17:19:59 8159 收藏 26分类专栏:算法 文章标签:汉诺塔版权声明:本文为博主原创文章,遵循 CC 4.0 BY-S ...

  • 算24全分析:计算力最强的牌组是哪个?最好算的数字是哪个?

    有了Python语言,我们可以对算24游戏相关内容做一个比较彻底的分析.为什么必须python语言,其它语言不行么?当然也可以,只是python让很多算法可以比较简单地实现,让研究过程更有乐趣. 6/ ...

  • 汉诺塔问题的两种解法(1)

    汉诺塔是一种益智玩具,源自古老的印度.如图1.图2及图3所示,有三根柱子,若干个大小不等的圆盘按顺序依次叠落在起点(左侧)的柱子上,通过多次移动后,全部圆盘要叠落在终点(右侧)的柱子上.移动必需遵守两 ...

  • 汉诺塔问题的两种解法(2)

    第二节 关键性结论 通过反复实践与观察,我们发现了解决汉诺塔问题的思路.无论圆盘的数量有多少,我们都可以把它们当作2个盘子来处理.假设共有N个圆盘,我们把它们想象为两个圆盘,其中一个圆盘是整个塔的塔底 ...

  • 汉诺塔问题的两种解法(4)

    第四节 汉诺塔问题的递归解法--移动所有盘子 上一节我们实现了连续移动两个盘子(数字),现在我们发挥一点儿想象力,将上一节的两个盘子当作一个盘子来处理,从而得出移动3个盘子的过程,代码如图22所示. ...

  • 汉诺塔问题的两种解法(5)

    第五节 条件限定法--限定条件 限定条件法不关注移动过程的整体规律,而着眼于具体的移动路径(规定每一步移动的出发点及落脚点),对每一种可能的移动路径设置限定条件,通过对限制条件的设置及调整,逐渐找到最 ...

  • 汉诺塔问题的两种解法(6)

    第六节 条件限定法--变量与过程 在开始编写程序之前,首先将此前已经完成的项目另存为"汉诺塔2",并在汉诺塔2的基础上,编写新的程序.原有项目中需要保留的全局变量及过程如图30所示 ...

  • 汉诺塔问题的两种解法(7)

    第七节 条件限定法--演示移动过程 上一节完善了2个已有过程,并新增了6个有返回值的过程,完成了对出发点.落脚点的选择,有了这些结果,本节可以收获成果了. 一.两个无返回值过程 (1)不连续移动 出发 ...

  • 汉诺塔问题的两种解法(8)

    第八节 求解过程小结 我们已经完成了对数字(盘子)的移动,并成功地演示了数字的移动过程.阅读并理解前面几节中的程序并不难,就这个例子而言,难的不是程序,而是编写程序之前对移动规律的归纳与整理,这也正是 ...

  • 科目余额表,只取最明细一级数据?Power Query和Power Pivot两种解法!

    小勤:下面这个表里是从财务系统里导出来的科目表,怎么能只保留本币里的最底层明细数据?最终本币列结果如右侧所示: 大海:能通过判断下一行中的科目编码是否包含本行科目编码来判断当前行是否为非明细行吗? 小 ...

  • 分享一道圆,两种解法,一种倍长中线余弦定...

    分享一道圆,两种解法,一种倍长中线余弦定...