搜索
汉诺塔游戏汉诺塔游戏是一个看起来简单的游戏，实际玩起来却不那么简单，类似九连环一样。关于汉诺塔，法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31556952秒，而2^64-1=18446744073709551615秒,换算成年等于18446744073709551615/31556952=584554049252。这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。我们玩几个盘子还是没问题的，开始吧！程序不大，但是用这个程序，既可以手动一步一步玩，也可以让计算机自动快速玩，每一步都会打印出当前状态。//陈宗权#includeiostream#includevectorusingnamespacestd;classHanoTowers{vectorintplaces[3];//abc三个位置size_theight;//目前各个位置的最大高度unsignedintsteps;//步数public:voidStart(){//输入盘子数量intn=-1,mode=-1;cout请输入盘子数量(1~9)和游戏方式(0自动1手动):;cinnmode;//检查有效性if(n9||n1||mode0||mode1){cout输入无效endl;return;}places[0].clear();places[1].clear();places[2].clear();height=n;steps=0;while(n0)places[0].push_back(n--);Show();//进入游戏if(mode==1)Play();elseAutoPlay();}//显示各个位置盘子的情况，towers表示3个位置上的盘子数及其各个盘子编号voidShow(){//高度递减，从高到低for(size_ti=height;i0;i--){//依次查看3个位置for(intj=0;j3;j++){//画每个位置的左分界线cout|;//如果这个位置的高度不够就显示空白if(places[j].size()i)cout;//高度足够就显示这个位置当前这个高度的盘子编号elsecout-places[j][i-1]-;}//画位置的右分界线cout|endl;}//画底部位置名abccout^=a=^=b=^=c=^endl;}//移动盘子，towers表示3个位置上的盘子数及其各个盘子编号，index_from表示源位置下标，index_to表示目标位置下标boolCanMove(charfrom,charto){//计算源位置和目标位置的下标intindex_from=from-'a',index_to=to-'a';//如果源位置上有盘子，而且目标位置为空位置或者源位置顶上的盘子编号比目标位置顶上的盘子编号小就可以这样移动return(!places[index_from].empty()&&(places[index_to].empty()||places[index_from].back()places[index_to].back()));}//移动盘子，from表示源位置，to表示目标位置voidMove(charfrom,charto){//计算源位置和目标位置的下标intindex_from=from-'a',index_to=to-'a';inttower=places[index_from].back();places[index_from].pop_back();places[index_to].push_back(tower);//设置目标位置顶上的盘子编号cout第++steps步:盘子tower从from移动到toendl;//显示一下移动后各个位置上盘子的情况Show();}//游戏函数voidPlay(){//为玩家显示游戏任务和游戏规则cout**请想办法把a位置的height个盘子移动到c位置，\n**每一步移动只能把一个位置最上面的盘子移到另一个空位置或者另一个顶上盘子编号比这个大的位置。endl;//只要a、b位置还有盘子就表示还没有完成，反复：while(!places[0].empty()||!places[1].empty()){//提示玩家操作cout请输入移动盘子方向（用abc中的两个字母表示）:;//接收玩家的操作charfrom,to;cinfromto;//检查操作的有效性if(from'a'||from'c'||to'a'||to'c'||!CanMove(from,to)){cout无效的移动方向endl;continue;}//按玩家的操作移动盘子Move(from,to);}//游戏结束cout~~~恭喜你完成任务!!!~~~endl;}//从一个位置移动若干个盘子到另一个位置//from表示源位置，n表示要移动的盘子个数，to表示目标位置，tmp表示另一个位置，用来当成临时位置用voidMoveTowers(charfrom,intn,charto,chartmp){//0个盘子自然什么都不用做if(n=0)return;//如果只需要移动1个盘子就直接移动到目标位置if(n==1){Move(from,to);}//如果要移动的是多个盘子，无法一步直接移动过去，拆分一下else{//先把上面n-1个盘子移动到临时位置MoveTowers(from,n-1,tmp,to);//现在把剩下的1个盘子移动到目标位置Move(from,to);//再把临时位置上那n-1个盘子移动到目标位置MoveTowers(tmp,n-1,to,from);}}//自动玩游戏voidAutoPlay(){//自动把全部盘子从a位置移动到c位置MoveTowers('a',height,'c','b');}};intmain(){HanoTowersgame;game.Start();return0;}