最新消息:

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

App Inventor 少儿编程 1501浏览 0评论

第六节 条件限定法——变量与过程

在开始编写程序之前,首先将此前已经完成的项目另存为“汉诺塔2”,并在汉诺塔2的基础上,编写新的程序。原有项目中需要保留的全局变量及过程如图30所示。

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

图30 需要保留的全局变量及过程

一、新增变量与过程完善

图30中部分过程需要加以完善,为此要先添加两个全局变量,如图31所示。

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

图31 添加两个全局变量

全局变量“最后移动项”用来保存上一次移动的数字,“步数”用来保存已经移动的步数。

需要完善的过程有两个——移动1过程及初始化过程,如图32所示,在这两个过程中对新添加的全局变量进行设置,并在初始化过程中增加对显示结果过程的调用。

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

图32 完善过程,对新添加的全局变量进行设置

针对每一次移动,记录被移动的数字——最后移动项,以及移动的步数。在即将编写的程序中,最后移动项用来确定下一次移动的出发点。

 

二、创建新过程

 

(1)有返回值的过程——是偶数

根据第五节的结论c,在移动数字1时,如果塔高为奇数,则移动到落脚点,否则,移动到相对缓冲区,因此定义一个有返回值的过程——是偶数,以便根据塔高决定数字“1”的落脚点,代码如图33所示。

 

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

图33 有返回值过程——是偶数

 

(2)有返回值的过程——任务完成

如图34所示,当左侧的数字全部移动到右侧时,该过程的返回值为真。

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

图34 有返回值的过程——任务完成

 

(3)有返回值的过程——塔高

根据第五节的结论d计算塔高。在计算塔高时,需要留心一种可能存在的情况。举例说明,假设实际塔高为5,那么它可能是(1,2,3,4,5),但也可能是(1,2,3,7,8),我们需要识别出这两种情况,前者的塔高=5,而后者的塔高=3。实际上我们要求的塔高必须是列表中最小的、且连续差值为1的数字的个数,因此,一旦遇到两个连续项的差不等于1,则塔高的值就已经确定了。塔高过程的代码如图35所示,一旦两个连续项的差值≠1,则设索引值为空表最大值,立即退出循环,返回计算结果。

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

图35 有返回值过程——塔高

 

(4)有返回值的过程——出发点

根据第五节中给出的证明:每一次移动的出发点都是唯一的。如果不是第一次移动,则可以利用全局变量最后移动项,排除掉三分之一的选项(上一次移动的落脚点),然后在剩余的三分之二选项中,选择首项值较小者为出发点。(在上一节我们已经证明:如果选择首项值较大者为出发点,那么它将无法找到符合游戏规则的落脚点。)根据这一结论编写一个有返回值的过程——出发点,代码如图36所示。

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

图36 有返回值的过程——出发点

 

(5)有返回值的过程——落脚点

根据第五节的结论b,当出发点的数字≠1时,落脚点是唯一的。我们来定义过程,求出这个唯一的落脚点,代码如图37所示。

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

图37 有返回值的过程——落脚点

 

(6)有返回值的过程——塔尖落脚点

上面已经求出了被移动数字≠1时的落脚点,现在来解决被移动数字=1时的落脚点问题。根据第五节的结论c,“塔”的落脚点是唯一的,但塔尖的“1”落脚点不唯一,它与塔高有关,当塔高为奇数时,塔与塔尖(数字1)的落脚点相同,反之则不同。根据结论c,塔落脚点的首项值与出发点的塔底值相差1,据此确定塔尖的落脚点,相应的过程代码如图38所示。在判断S、T、B是否为出发点时,程序中使用了“S1=1”这样的条件,它等同于“S=出发点”这样的条件,但是前者是数值之间的比较,而后者是列表之间的比较,后者会消耗更多的计算力。

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

图38 有返回值的过程——塔尖落脚点

 

我们依据第五节中的4个条件及4个结论,确定了每一次移动的出发点及落脚点。如上所述,其实每一步移动都可以在前一步的基础上,确定唯一的移动路径,这样的结果得益于对物理世界中移动过程的观察、分析及归纳。运用人类自身的智能,可以极大地提高机器解决问题的效率,而这正是我们希望获得的能力。

 

有了上面的过程,我们就有了每次移动的出发点及落脚点,因此余下的事情就简单了。

 

== 未完待续 ==

您必须 登录 才能发表评论!