汉诺塔问题的两种解法(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个元素(盘子或数字)从出发点移动到落脚点,需要三个步骤:
小的从出发点移至缓冲区;
大的从出发点移至落脚点;
小的再从缓冲区移至落脚点。
创建一个过程——移动2,来完成上述三个步骤。仍然借用暂停按钮实现移动操作,代码如图21所示。请读者自行测试程序的执行结果。
图21 连续移动两个数字
注意理解移动2过程的参数,S表示移动的出发点,B表示移动的缓冲区,T表示移动的落脚点,它们表示的都是相对位置。图21中,在暂停按钮的点击事件中调用移动2时,所提供的参数恰好与绝对位置相一致。不过在后面的程序中,移动2的出发点可能是绝对位置的起点、终点或缓冲区,同样,移动2的参数B可能是绝对的起点、终点或绝对缓冲区,参数T亦然。这一点希望读者能够明了。
== 未完待续 ==