图形化汉诺塔LOGO递归编程值得研究
厦门市教育局-市科协官方联办的2023年小学生LOGO语言竞赛复赛 “汉
诺塔”动态作图题为我们提供了一个非常好的研究课题。竞赛题目只要求画3层的图形，总共只有8个画面，所以在竞赛场上最合理的编程方式就是“依样画葫芦”直接画8个连续画面——这样做法的结果是：合乎题目要求，但非常省力省时。源程序之前已经介绍过了。这种“依样画葫芦”的编程其实也同样包含着相当巧妙的编程思维技巧。但是比较“正规”的“汉诺塔”编程用的必然是“递归”算法。因为层数稍多的汉诺塔的移动步骤非常多。3层的汉诺塔移动总次数是2的3次乘方减去1=
2^3-1=7。像上图中17层汉诺塔需要的移动次数是2^17-1=131072-1=131071次！汉诺塔移动了近2000次还远未达到移动完成的地步，用表数据储存这么多的移动过程数据是不可想象的操作。唯一的出路是使用递归算法，把移动步骤交给计算机程序来安排。
在LOGO语言编程中这一段“递归”核心程序如下面那一段程序所示。如果你有兴趣遍历过足够多的各种编程语言(LOGO、C、C++、PASCAL、PYTHON、VB、QB、，其汉诺塔编程核心程序段的结构都和LOGO编程的“递归”算法如出一辙或是极为相似。
to move_a
:n :aa :bb :cc
;LOGO编程递归实现盘的移动
if :n>0[
move_a :n-1 :aa :cc
:bb
make "bz :bz+1
pri_a
move_a :n-1 :bb :aa
:cc
]
end
在林老师编著的《MSWLogo讲义Plus》第10章第3节中所详细介绍的递归算法的汉诺塔非常可能是目前所有能够查到的公开资料中功能最强、且完美无缺的汉诺塔程序。林老师编写的这个LOGO程序具有以下特点：
1.
可以自由定义任意层数的汉诺塔。考虑到限于屏幕大小及过多层数的汉诺塔的运行时间长度可能无比地冗长，一般不要定义超过20层(2^20-1=1048567次，如果计算机每秒钟移动两次，需要超过6整天的漫长时间)。
2.
可以自由地选择或是用文字输出移动过程、也可以用图形实时输出的汉诺塔搬运过程。
3. 在指定使用图形输出时，还能够自由选择调整图形输出的速度为“高-中-低”三种速度。高速地显示所有图形搬动的耗时短，低速时更易于看清楚搬运运动的过程步骤。作为研究、演示，:n设定5～10层已经足够精彩，且耗时在可以容忍的范围之内。
4.
程序具有一定程度的“智能”，能够根据“塔”的层数的多少，自动调整一整串“盘”的宽度尺寸及单片的厚度，自动确定3根“杆”的高度。
5.
考虑到汉诺塔原传说故事中说的是用“金子”制成的空心圆盘，图形里设定的“盘”的颜色画成金黄色,输出图形的下方自动显示当前移动步骤累计的次数及当前移动的盘号及目标方向。
目前尚未找到有比林老师编写的更智能、更高级的汉诺塔程序。请你直接查阅林老师编著的《MSWLogo讲义Plus》时教程附件中有这个程序可直接调用。
从实战效果考虑，官方竞赛考场中编写类似这样的“递归”程序来解决竞赛题“汉诺塔”，编程量太大太复杂，在汉诺塔层数较少时，策略上选用“依样画葫芦”式的编程更有效率、更节约时间。但是如果真想学会编程、充分发挥计算机高速运算的潜能，空闲时把如下的“递归”编程彻底吃透，将真是会获益无穷。LOGO编程其实是能够“做”很多事情的，用LOGO编程输出图形化汉诺塔其精彩程度要比只输出文字过程的C++、PASCAL好得多。
源程序：
to hnt_a
:n ;运行命令HNT_A :n
;汉诺塔问题
:n是塔的层数 建议不超过20层
cs
ht
make "aa "a
;把杆号赋值给变量
make "bb "b make "cc "c
make "ag iseq 1 :n
;建立a杆初始盘号
make "bg [] make "cg [] ;建立bc杆空堆栈
make "hp []
;hp是画图输出时的数据中转堆栈
make "pk rseq 120/:n 120 :n
;计算1～:n号盘宽度
make "gg 25*:n+25
;计算杆的高度
make "gw (array 3 1)
;建立杆位置X坐标
for
[i 1 3][setitem :i :gw :i*125-250] ;杆的X位置
make "bz 0
;计算步骤数计数器清零
make "ms selectbox[请选择输出方式][数字输出模式 图形输出模式]
if
:ms=2[
;图形输出时画底座
make "sudu selectbox[选择显示速度][快速 中速
慢速]
setfc 1 pu setxy -200 -45 bitblock 400
43
;画底座
setpc 7 pu setxy -130 -10 seth 90 label
"a
;写abc
pu setx -3 label "b setx 121 label "c seth
0
make "hp :ag psx "a make "hp :bg psx
"b
make "hp :cg psx "c wait 30]
move_a :n :aa :bb :cc ;调用递归核心程序
end
to move_a :n :aa :bb :cc
;递归实现盘的移动
if :n>0[
move_a :n-1 :aa :cc
:bb
make "bz :bz+1
pri_a
move_a :n-1 :bb :aa
:cc
]
end
to
pri_a ;实现文字输出的子程序
make "sc []
;把文字输出答案串联在:SC变量中
make "sc lput :bz :sc make "sc lput "- :sc
make "sc lput "被移动盘 :sc make "sc lput :n :sc
make "sc lput :aa :sc make "sc lput "->
:sc
make "sc lput :cc :sc
ifelse :ms=1[
pr :sc][
;输出文本答案
setfc 7 pu setxy -120 -73 bitblock 260
25 ;在图形下面显示答案
seth 90 setpc 4 pu setxy -100 -50 label :sc seth
0
if :aa="a [
; :a:b:c数据出栈操作
make "chu first :ag make "ag
bf :ag make "hp :ag psx "a]
if :aa="b [
make "chu first :bg make "bg
bf :bg make "hp :bg psx "b]
if :aa="c [
make "chu first :cg make "cg
bf :cg make "hp :cg psx "c]
if :cc="a [make "ag fput :chu :ag make "hp :ag
psx "a] ;入栈操作
if :cc="b [make "bg fput :chu :bg make "hp :bg
psx "b]
if :cc="c [make "cg
fput :chu :cg make "hp :cg psx "c]
]
end
to psx
:name
;汉诺塔刷新子程序:name是杆号
make "hao (ascii :name)-96 ;求杆号数组索引
make "gwz item :hao :gw
;求杆的X位置
pu
setxy :gwz-65 0 pd
;刷新原杆盘
setfc 7 bitblock 130 :gg+10
pu
setxy :gwz 0 pd setpc 4 ;画杆
setpensize[4 4] fd :gg
make "len count :hp
;检测堆栈中盘子总数
if
:len > 0 [
;必须这个杆上有盘才开始画
setfc 14
;画每个盘
repeat :len[
make "whith_ item (item
(:len-repcount+1) :hp) :pk ;读出盘宽
pu setxy :gwz-:whith_/2
(repcount-1)*25+5
;画盘
bitblock int(:whith_)
20 ;这个命令只支持整数像素画图所以用int取整
]]
wait :sudu*:sudu*8
;延时控制
end
加载中…
(2024-06-11 10:04:13)