又做游戏三则|狼第三则

　　今天,我们再做三个游戏。 　　 　　台球桌上的数学 　　如图1―1,在设定长宽比m:n的台球桌上,划分出mxn个小方格。四个角上有球袋。若从左下角A开始,沿小格对角线方向击球。几步之后球将落袋(每通过一格对角线称作一步)?
　　
　　
　　键入整数m和n的值后,画出分成m×n格的桌面,其左上角坐标是(x0,yo),然后通过点击按钮(C0mmandl)来操作球的行走。动态球的坐标用(x,y)表示。桌面的四个边框简称为上下左右,k的4个值代表了左往上,上往右,右往下,下往左四种方向。每点击一次按钮即画出球走一步的路径,直到球进某一袋子,所用步数统计于变量js。台球运行的全过程见图1―2,输入时设定了Ⅱ1=5和n=3,最后输出is=15。
　　尝试过不同的长宽比后你会发现,台球落袋之前所走的步数应该是m和n的最小公约数。
　　
　　金字塔的魔法数
　　
　　金字塔是底面为正方形的棱锥。关于它,有这样一道数学题:给它的底面四条边和四条侧棱不重复地标上连续8个自然数中的各数,若安排恰当,会使任一交汇点处(底面四角及一个顶点)相交于该点的所有边上数字之和都等于同一个数,即24。对此我们很想知道,这个题目有解吗?那8个自然数是什么又是如何安排的呢?
　　其实,刚才的“台球桌问题”用笔在纸上一写一画就能解决。研究本题时,只要有很好的耐性,经过大量地设数和笔算也终会得到结果。但我们编程上瘾,用计算机来玩这些游戏的乐趣更大!处理本题时采用穷举算法,一比就知道,它完成速度之快是人工试算不可比拟的!
　　
　　
　　最外层的n循环进行0-4共5次,由i循环完成5组连续8个自然数的产生(如1-8,……5～12,领头的数若大于5将不符要求,排除它们可减少许多运算量),并存人数组x。对其中的每一组数,通过内层的八重循环(a循环至h循环),对四条边和四条棱有序井然地穷举配数,每配一次就将该次的8个数记入数组s,然后计算和判断,只要通过某交汇点的各边数字之和不是24就进行下一次选配。一旦满足条件就输出结果,跳出八重循环,再进行下一组数的考查。
　　从图2给出的输出数据6、10、9、11、8、5、4、7可以看出,它是本题唯一的答案。符合条件被选中的自然数是4～11,它们经过分析处理,按输出数据的排列次序配送于四边四棱,其位置示意于图中的金字塔上。在此游戏中,24被称为魔法数。还有另一版本称16是魔法数,不过8个自然数不一定连续,它们可以是1-10数字中任取的8个(不重复),你要不要再来做一遍?
　　
　　
　　
　　汉诺塔
　　
　　有三根柱子A、B、C,在A柱上有64个大小不同的盘子,小盘在上大盘在下,摞成一个塔形。若要把所有的盘子从A移到c(可借助B,每次只可移1个盘,且小盘必须始终在大盘之上),应怎样搬动盘子,最少需要搬动多少次?
　　我们从较少盘子的情况入手研究一下算法。若A柱只有1个盘,A――C搬1次解决。2个盘时,应该有A――B(小)、A――C(大)、B――C(小),需搬3次(若第一、第二次改为A――C(小)和A――B(大),下一次只能是C――B(小)或C――A(小),取前者如同回到初态,前几次白搬了;取后者再经B――C(大)、A――C(小),共需5次搬完,不是次数最少方案)。用草图画一下(示意如图3),可以发现搬动3个盘的最佳方案是A――C(小)、A――B(中)、C――B(小)、A――C(大)、B――A(小)、B――C(中)、A――C(小)共7次。这是3个盘从A借助B搬到C完成的过程,那么搬4个盘呢?就应该是较小的3个盘从A借助C先搬到B,然后A――C(最大),再将3个较小盘从B借助A搬到C,共需7+1+7=15次,注意不要搞错,这15次中的第一搬是A――B(小)。
　　我们猜想,可能存在以下规律:
　　(1)盘子由小到大按1、2、3、4……编号。设盘子总数为m,当m为奇数,第一次搬动时奇数号盘为A――C,偶数号盘为A――B;而当m为偶数,第一次搬动时奇数号盘为A――B,偶数号盘为A――C。
　　(2)第一次都要搬动最小的1号盘,它每隔一次(逢奇数次)被搬一次。逢偶数次,搬动最小盘以外的其他盘。
　　(3)无论对哪一个盘,比如上次是从A――B的,下次就应从B――C,而不要返回A。
　　(4)正确的搬动次数应该是s=2m-1次。
　　再看图4,带下横线的数字1-5为盘号,圆盘中的1-31标出该盘在第几次被搬动。实际上此图不仅反映m=5的情况,它包含着m取1-4,并可以逐步类推至m>5的所有情况。
　　
　　
　　
　　为游戏实用和运行时动态图清晰,建议盘数m不大于8。到带[*]的语句止,显示出搬运开始前的图像,并给下标为各个盘号的数组q$都赋以字符“A”。在单重n循环内操作每一次搬动,算法依前面分析出的四条规律而生,请读者仔细体会。这里n代表正在搬第几次,k代表盘号,q$数组内存入的是运行中每一次新的搬动前各盘所在的位置(用字符A、B、C表示)。每确定一次搬动的起终位置(比如A和B),就将这两个字符存入下标为n值的数组s1$和s2$中,想要随时或者最后输出结果都行。图5为m=5时的运行结果(为省篇幅,程序中略去了打印输出语句)。
　　子程序subl用来完成盘子搬运的动画过程。数组x记入三根柱子的水平方向坐标,而数组p记人每次搬动前各个柱上的盘子数目,为了运算操作,用u1和u2代表每次搬动时起终位置的柱号(1、2和3,对应于A、B和C),通过计算找到每次应搬动的盘,抹去于原位,添加于新位。
　　汉诺塔问题是一个数学名题。相传在古印度北方的一座圣殿中,僧侣们忙碌地在三个塔柱间搬运着64个金盘。据称,当任务完成时,喜马拉雅山将变为金山。算一算,他们搬动金盘的总次数应该为264-1=18446744073709551615次,即使快捷到1秒钟搬一次,也需要5800亿年!
　　求解汉诺塔问题用递归算法最佳,程序简单解题迅速,但游戏味不够。在许多高级语言的教材中可以见到,读者应该找来看看。要是你能把今天我们的程序改动一番,使得每次盘的移动可以人为掌控。做出一个汉诺塔玩具来,那就更有意思啦!