【doc】关于Hanoi塔问题

【doc】关于Hanoi塔问题 关于Hanoi塔问题 f 摘要 关键词 分类号 0引言 嘲譬一}l{ ,it,?1.…...1…【11… Vo1【3cI{ 【1It,c.19l_ 关于Hanoi塔问题 周尚超徐保根乙/学松 (基础谭部) 业 /4,.;谤问落 ?{传17l}}术远尔禁,r火哂I}].钉?根佳救瞢中心有孔的64个咖盘.姆盘的直 f}'1,?l.?hnl融的"任总J比f:的直径^=.违就址tIanoi塔.Hanoi塔问题昆.将所 『f0剖舭f#刮3!J.姆演}1能髂'}i一个髓于.4:能将夫盘移刮小盛之.移动过髭中可 将齄临时救第2讯},产.在许多有关计算机的籍上.介绍了瑁计算机解该问题的方 法.例如.将31,艇从1号柱移到3往.计算机给出的解是(用1号,2号…表示盘子大小, 号数太rJI1盈子大) 将1号髓从1号柱移到3号柱; 将2呼盛从1号柱移到2号; 将1号蕊从3号柱移到2号柱; 将3号盘从1柱移到3号柱; 将1号盘胰2号柱移到l号柱; 将2号盘从2号柱移到3号柱; 将I号盘从I号拄移到3号往 戢抟照计机给出的辩进}操作.将是很笨拙的.且随昔盘子敬的增加操作的难度将越 求越.卿如.l仃10十船f时.需要移动盘子1023次.用计算机解决问题有很大的局限性. 它:t融决j敏敏无增人的情况.当盘子数?1330时.计算机就给出内存不够的信息. 假泄计算机的内存七限夫.邪么当,:=100万时.计算机至少颁运行150秒以后才能告诉你第 1次怎样传动缸.汁机秆决此强的方法垃:如要解决必{f解决一1.要解决一1.必 ;解决2…….如f{n1'机敏数.从1数列l00万.在486微饥七一般要150秒.因此.汁 收稿闷l明:1q(j_10尚趣.男.1948年七.教授 *I竹门然科学资HH渫题 , ,,EV ,6 66华丰交通太学学毒【 算机将移动方法计算出来的时间不低于150秒. 我们从理论上对Hano~塔问题进行研究.得到了准确无误的操作简单的解决办法.无论 有多大,都可以立即进行,不需要计算时间.如果将个蕊子从一个柱子移到另一个柱需要移 动的盘子次数最少是COUnt(n),那么我们的操作方法将一定在COUnt(")次之后完成. 1操作方法 一个盘子用l号盘,2号盘一?n号盘表示,号数大则盘子大.不是1号盘的盘称为非1号盘. 在操作开始以前和操作完成之后,只有1个柱子上有盘子,两个柱子上无盘子.在第1次移动 盘子之后到完成以前,至少有两个柱子上有盘子,没有盘子的柱子,我们假设有一个虚盘,且虚 盘是晟大的盘.由于1号盘最小,l号盘总是在某柱的最上面.在第1次移动盘到完成之前,在3 根柱子最上面的3个盘子是 l号盘号盘号盘(<) 其中号盘可能是虚盘.为叙述与操作方便,把i号盘称为小盘,』号盘称为大盘.这是因为,在 操作过程,我们只需要知道一个盘是否1号盘,在两个非l号盘中,其要知哪个大哪个小就行 了,不需知道它是第几号盘.这样3根柱子最上面的3个盘子是 l号盘小盘大盘 将一个盘子从1号柱移往3号柱的方法. 方法1.1第1次移动的盘子是1号盘,如果上次移动了l号盘,则本次移动非l号盘;如 果上次移动了非1号盘.则本次移动l号盘. 方法1.2移动非l号盘的方法恳把小盘移到大盘上. 方法1.3移动l号盘的方法.按H为奇偶数分为两种.设1号盘在A号柱上. 方法lI3.1设"为奇数,把l号盘从A号柱移往A+2号柱(如^>l则移往A一1号 柱).即1号盘的移动路线是:1号柱一3号柱一2号柱一l号柱. 方法1.3.2设n为偶数,把1号盘从』4号柱移往A+l号柱(如A>2则移往A一2号 柱).即l号盘的移动路线是:l号柱一2号柱3号柱一l号柱. 移动l号盘是按柱子号来移动的.在实际操作中,盘子数不会太多,下面我们给出移1号 盘的另一种方法,它是按盘子号来移动的. 方法1.3移动l号盘的方法.如果是第1次移动1号盘,按方法1.8进行.注意到在第 1次移动之后,3根柱子最上面的3个盘子是:l号盘.小盘和大盘.方法是;如果小盘号是偶数, 把l号盘移到小盘上,否则移到大盘上. 2操作方法的证明 将"个盘子从1号柱移到3号拄,可按如下3步进行. 步l将1号柱上的"一1个盘移往2号柱. 步2将1号柱上的号盘髂往3号柱. 步3将2号柱上的1个盘移往3号拄或移到,号盘之上 幕期周由超等关于Hart,塔问道67 我们用]表示把1,2,…,号共个盘从l柱移往另一拄,用^表示把号盘从1拄移往 另一柱,用A—表示从A弓柱移往B号柱.J表示n—,表示一.上述3步可记为 [卅]:[n1]n1] 1—31一2l一32—3 或简记为[,1]=1]1].设count(n)表示移动的最小次数,则count(n);2count(n1)+ 1.用递推法又可得 [1]一2]nl[2] ["2]=3]n23] [3]=[2]1[2] [2]一[1]2[1] [1]=1 由count(1)=1,易知count(n)=2一一1.H号盘在整个移动过程p只移动1次.nl号盘其移 动2次,一般地,号盘移动的次数是+1号盘的两倍.上述3步详记如下; []一[一1]一[n1] 1—3l一2l一,3.2—3 第l到第一1次第1到第一i次第次第十1蓟第2-一1次 我们把l,2,3号柱分别称为l凹3的源,中,目.相应地l[和]3的源,中,目分别是 1,3,2和2,1,3.设第次移盘是从厂()柱到g()柱(1??2一1),如厂()是的源 (中和目),则厂(十)也是2L — nJ 3的源(中和目),两者的源(中和目)相差1.因此,厂(2.'+) 一 /'()+1,g(2+):F(』)+1.如加i后大于3.则将其值减3.如果将]一l1] 改为]=1[正1],也有类似的结论,但也不完全相同.例如前者"号盘是在第次移动 的,只移动一次,对号盘则是:第i次移动号盘是在第2"次,以后每隔次移动一次.下面 推证第一次是怎样移动盘子的. 第1次到第一1次:[hi1—3i 第1次到第2一1次:1]l一2; 第1次到第2一1次:[,12]1—3; 第次到第z"J)一次即第次[]一{:翥萎,即厂c-,=,c,=scz," 奇(偶).整理得如下结果. 2.1Count()一2"一1. 2.2 次. 2.3 =01 号盘被髂动的次数是2.特别地.n号盘只移动1次,1号盘移动次数最多,为2 , 如果r被2整除.但不被2整除,则第i次移动的是号盘即当:2'1_-2, … , 2…一1时移动的是号盘.特别地第奇数次移动的是1号盘.第一次移动号盘 华东交通太学 拒第2次.每隔2次移动1次号舷. 2.d设群i次是将fu)号性子上的盛移刮(枉.分勾假敬阿"t 2.4,Il】为奇数 ,=.gc./c!'=.:= ,{ ' ( f茸{ l厂( 一1.2.…. 24.2为偶数 j| ' ( { lt 为奇数 为偶数 为奇数 为偶数 :.,cz一;凳蠹羹 为奇数 为偶数 ^为奇数 k为偶数 ^=I.2.…一1;一1—2.….2'一I. 如,和大于3.则将其减3. 由2.4可得2.5, 2,5如i是奇数.则g()一,()I{1)一r/(1),当,f是奇数.g(i)一(i)十2,即1 盘的移动路线是1号柱3号柱2号柱1号柱,当是偶数.g(f)/()_一1.1号盘的移 动路线是1号柱一2号柱一3号柱一l号柱. 上述2,3是对方法1,1的证明.2,5是对方法1,3的证明.方法1.2屉显然的.FjE方密1. 3'. 设1号盘下是2.3.….1号盘.号盘不在1盘r.则盘娃哥外附根性上二的艇小龀,3 恨柱子最上的3个盘是1号.号和号盘.<,.这是处于矗盘移动之后要传动1艋时的 情况按前面的论述.移动号盘前后的若干次操作是…f1乞(,{一?.醴【]F--步蟹 将B柱上的1个盘移到号盘所在的C柱上.若足仙数.刚1奇数.镬将奇敬个箍从,{fE 移往f往.第1次颁将1号盘移刮C柱的盘之上.如琏曲数.I删将1号盘移副号盘之i 参考文献 1金志枉.陈飘厢.人工智能程序南京:南京大学出板吐,H186 OnHanoiTowerProblem zhuShangchaoXuBaogenZhouXucsoag (BasicCoursesDcparln1cI1t) AbstractThispaperintroducesasimplemelhndt'orI{anoitowerpr(IhlLIllb Keywords:Hanoitower;rccursion