资源描述：
《hanoi塔问题的一个公式解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Hanoi塔问题的一个公式解2001年5月May,2001运筹学0RTRANSACTIONS第5卷第2期V01.5No.2HOWtoMovetheDiscsontheTowerofHanoiJIANGUOQIANFujiZHANGfDepartment.fMathematicsXiamenUniversity,Xiamen361005,China)AbstraetTheprimaryversionoftheTowerofHanoiproblemrpuzzle)w∞firstlyinventedbyE.Lucasin1883,andlaternumberedby'pr
2、oblem3918'(with3pegs).ThegeneralversionwasintroducedbyWood,GeretyandCul1.AspointedoutbyH.A.Simon,thetower(ofHanoi)wastocognitivesciencewhatthebacterE.coli,懈tomoderngenetics--aninvaluablestandardresearchsettiⅡg.Daringthepast100yearsormore,thispuzzlehasattractedmoreattentionsof,notonlyth
3、emathematicimas',butalsothecomputerscientists'.Alargenumb~ofvarious(recnrsive,iterative,cyclicandlooplessetc.,algorithmsforsolvingthispuzzlewereestablished.Reviewingthepreviousliteratures,itleadsnaturallytoaneleme~aryquestion:isitpcefibletofindanalgebraic如nnIafnon-algorithm)forthisprob
4、lem?HereweshowthattheanswerisYes'Keywords:TowerofHanoi,algebraicsolution,graph.Hanoi塔问题的一个公式解钱建国张福基(厦门大学教学系,厦门,361005)摘要Hanoi塔问题自提出以来已有一百多年的历史.其间.这一问题吸引了许多的研究者.正如H.A.Simon所指出的,Hanoi塔问题对于认知科学就象大肠杆菌对现代基因学那样,是一个无价的研究标本.事实上.它已成为组合数学,人工智能.计算机科学以及规划等中的递归问题的典型倒子,并由此产生了各种各样成熟的算法.回睡这些结果.我们提出一个基
5、本问题t能否对Hanoi塔问题给出一个公式解?本文就此给出了一十肯定的回答.在我们的研究中.图论将是一个有力的工具关■调Hanoi塔问题,公式解.图论1.IntroductionandmainresultsItisdifficulttoknowthetruthabouttheoriginoftheTowerofHanoiproblem(puzzle).Onest~ememisthatitodginatedfromanChineseorIndiangame.Acommonlyacceptedst~ememisthatit(theprimaryversion)wasfi
6、rstlyinventedbyLucasin1883[2,13],whoalsoinventedthestoryabouttheworldendingwhenthegameisover.In[291,thispuzzleReceived:October19,2000.ThisworkissupportedbyNSFC(69673042)andXMUF(Y070~I)JIANGUOQIAN.FuJIZHANGVb1.5wasnumberedby'problem3918'(with3pegs).Thegeneralversionofthisproblemwereintr
7、oducedbyWood,GeretyandCull【14,33】,respectively.TheTowerofHanoiproblem(generalversion).Wehavethreepegslabelled1,2and3,andndiscsnumbered1toninorderofincreasingsize.A(1ega1)configurationisadistributionofndiscsamongthepegsbystackingthemonthepegswithnodiscrestingonasmalleroneA(1ega1)movet
