汉诺塔问题串串烧

汉诺塔问题串串烧12009-05-1715:39汉诺塔问题串串烧1.相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆(编号A、B、C),A杆上自下而上、由大到小按顺序串上64个金盘(如图1)。游戏的目标是把A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出N个盘从A杆移到C杆的移动过程。图1N阶汉诺塔分析：这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：1.以C盘为临时杆，从A杆将1至N-1号盘移至B杆。2•将A杆中剩下的第N号盘移至C杆。3.以A杆为临时杆，从B杆将1至N-1号盘移至C杆。我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同，唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题(图4)。即：HANOI(N,A,B,C)可转化为HAN0I(N-1,A,C,B)与HAN0I(N-1,B,A,B)其中HANOI中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘，这种转换直至转入的盘数为0为止，因为这时已无盘可移了。这就是需要找的递归调用模型。图2N-1阶汉诺塔源程序如下:programex11_12;vara,b,c:char;n:byte;procedurehanoi(n:byte;a,b,c:char);beginifn>0thenbeginhanoi(n-1,a,c,b);writeln('Move',a,'to',c);hanoi(n-1,b,a,c);end;end;begina:='A';b:='B';c:='C';write('N=');readln(n);hanoi(n,a,b,c);end.一般的算法是很难解决这个问题的，而过程HONOI只用了4个语句就解决这个难题。不过要说明的是，按照汉诺塔的移动原则，将N个盘从A杆移动到C杆需要移动盘的次数是2的N次幂减1，那么64个盘移动次数就是18446744073709511615，近19亿亿次。这是一个天文数字，即使一台功能很强的现代计算机来解汉诺塔问题，恐怕也需要很长的时间，因此要想得到结果，在运行程序时，输入的N可不能太大。据说布拉玛婆罗门圣庙的僧侣声称，汉诺塔游戏结束就标志着世界末日的到来，现在看来确实是有道理的。因为如果每秒移动一次，64个盘则大约需近5800亿年，而据科学家以能源角度推算，太阳系的寿命只不过150亿年而已。非递归算法：定义从小到大的盘子序号分别为1,2,……n。可以用一个1到2九-1的2进制序列可以模拟出n个盘子的汉诺塔过程中被移动的盘子的序号序列。即给定一个n,我们通过0到2九-1序列可以判断出任意一步应该移动那个盘子。判断方法：第m步移动的盘子序号是m用二进制表示的最低位bit为1的位置。证明：n=1，显然成立。假设n=k成立。n=k+1时，对应序列1到2人(k+1)-1，显然这个序列关于2Ak左右对称。假设我们要把k+1个盘子从A移动C。那么2Ak可以对应着Move(k+1,A,C)。1到2Ak-1根据假设可以对应Hanoi(A,B,C,k)。至于2Ak+1至【」2A(k+1)-1把最高位的1去掉对应序列变成1到2Ak-1，显然2Ak+1至【」2A(k+1)-1和1到2Ak-1这两个序列中的对应元素的最低位bit为1的位置相同。因此2Ak+1到2A(k+1)-1可以对应Hanoi(B,C，A，k)。所以对n=k+1也成立。下面讨论第m步应该移动对应的盘子从哪到哪？定义顺序为A->B->C->A,逆序为C->B->A->C。性质对n个盘子的汉诺塔,任意一个盘子k(k<=n)k在整个汉诺塔的移动过程中要么一直顺序的，要么一直逆序的。而且如果k在n个盘子移动过程的顺序和k-1(如果k>1)以及k+1(如果k<n)的顺序是反序。比如：n=3TOC\o"1-5"\h\zA->CA->B1C->BA->CB->AB->C1A->C其中1的轨迹A->C->B->A>C逆序，2的轨迹A->B->C顺序，3的轨迹A->C逆序证明：假设n<=k成立对于n=k+1根据递归算法汉诺塔问题22009-05-1715:402•对于n(v=500)各盘子的经典汉诺塔问题，输出某一去诶的那个步骤的移动方案。输入文件中，只有一行，两个整数n,m，分别标识盘子数和移动方案中的第m步。输出文件中，只有一行，输出第m步移动方案。样例输入：100237684487542793012780631851008样例输出：BfC【问题分析】使用传统的解决汉诺塔问题的递归方法，我们只需要在源程序中添加一个全局变量记录当前的移动是第几步就可以解决这个问题，但这种方法显然不能解决500各盘子的问题，所以我们需要考虑其他的办法。这就需要对汉诺塔问题有深入的理解。我们知道，对于N个盘子的移动次数是可以得到递推公司的:f[n]=2n-1,所以我们可以考虑当前移动步骤是在移动第N个盘子之前还是之后，把问题规模缩小一个盘子，这样我们可以递归求解了。当然，由于n的数字较大，我们还要采用高精度来计算。递归求解部分的主要代码如下(高精度省略)：Proceduremain(n:integer;m:string;a,b,c:char);BeginK:=2n-1；｛第2n-1步是分界点，这一步的操作是将最大的盘子从a移到c上｝Ifmvkthenmain(n-1,k,a,c,b);｛如果最大的盘子还没有移动，问题变为将前n-1个盘子从a借助c移到b上的子问题｝Ifm=kthenwriteln(a,J，,c);Ifm>kthenmain(n-1,m-k,b,a,c)｛最大的盘子已经到位，问题变为将前n-1个盘子从b借助a移到c上的过程中，第m-k步的操作｝End;通过这个例子，我们可以进一步理解汉诺塔问题的递归过程，同时本题也可看做是二分法的应用。这个方法的效率是0(n)，而不是使用传统方法的O(2n)，效率有了非常大提高，而时间主要用在高精度计算上。3•问题描述：设有a,b,c三根柱子(称为三塔)，在a柱上由小到大的放置着n个盘子。今将a柱上的盘子移动到d柱上，移动的规则如下：(1)、每次仅能移动一个盘子。、小盘子只能放在大盘子的上面。、可以利用其他柱子做工作栈用。现在我们考虑一个更一般的问题，移动策略不变，仍然是一次只能移动一个盘子，同时，并不允许出现大盘在小盘上面的情况，但初始时，并不是所有的盘子都只能在第一个柱子上，目标状态也不一定所有盘子均在第三个柱子上。请找出一种移动次谁最少的方案。输入文件中，第1行是盘子总数；第2至4行分别是初始状态中三个柱子上的盘子个数和从上到下每个盘子的编号；第5行至7行分别是目标状态中三个柱子的盘子个数和从上到下每个盘子的编号。其中n个盘子从小到大编号为1，2,o°°。n.输出文件中，每行写一部移动方案，格式为'盘号：当前柱子号-移动到的柱子号”，最后一行输出最少的移动步数。【问题分析】我们不难发现这个问题的关键是：按编号从大到小依次将盘子移动到目标状态°因为编号最大的盘子位置固定后，对后面的移动将不再产生影响，从而将问题转换为规模更小的子问题，可以递归求解°其中移动的过程和主程序的主要代码如下：Proceduremove(k,i:byte);｛将第K号盘子移到I柱上们为了方便这里把三个柱子记为1，2，3｝Consta:arry[1..3]ofchar=(„A','B','C');Varj,temp:byte;BeginIfnow[k]=Ithenexit;｛递归出口，now[k]记录k号盘当前的位置｝Temp:=6-now[k]-I;｛temp为k当前位置和目标位置之外的柱子号｝Forj:=k-ldownto1domove(j,temp);｛把比k小的盘子都移到temp上｝Writeln(k,y,a[now[k]]Jf，,a[i]);Now[k]:=I;Inc(step);End;BeginInit;Fori:=ndownto1domove(I,goal[i]);｛从大到小依次把所有的盘子都移到目标状态｝Writeln(step);Close(output):End.思考：4塔呢？？？？？？4.汉诺四塔问题描述：设有a,b,c,d四根柱子(称为四塔)，在a柱上由小到大的放置着n个盘子。今将a柱上的盘子移动到d柱上，移动的规则如下：、每次仅能移动一个盘子°、小盘子只能放在大盘子的上面°(3)、可以利用其他柱子做工作栈用°输入n，输出最少次数的移动方式，存入文件中。参考程序programex;varn,n1:integer;varm,i:longint;vara:array[1..100]oflongint;proceduref(x,a,b,c:longint);beginifx=1thenwrite(a,\'->\',c,\'\')elsebeginf(x-1,a,c,b);write(a,\'->\',c,\'\');m:=m+1;f(x-1,b,a,c);m:=m+1;end;end;procedurerun;beginfori:=2ton-1doifa>=1thenbeginf(a,1,n,i);m:=m+1;end;write(\'1->\',n,\'\');fori:=n-1downto2doifa>=1thenbeginf(a,i,1,n);m:=m+1;end;end;beginm:=0;writeln(\'Input:\');writeln(\'Howmanyisthepost.\');readln(n);writeln(\'Howmanyisthedish.\');readln(n1);a[2]:=n1-1;fori:=3ton-1dobegina:=trunc((n1-1)/(n-2));a[2]:=a[2]-a;end;run;writeln(m+1);end.汉诺四塔问题我们知道经典的汉诺塔问题，对于n各盘子从A柱移到C柱最少需要2九-1步，其中移动过程中，我们呢借助了B柱，现在我们再添加一个柱子，那么要借助B、C两个柱子，把A柱上的n个柱子移到D柱上，最少需要移动的步数是多少？【问题分析】在这个问题中，多了一个柱子，我们仍然要从经典问题出发进行思考，我们考虑递推的方法。设f[i]表示四塔时i个盘子移动所需要的最少步数，那么我们可以把原无难题分解为三步：第一步：先把A柱子的前j各盘子移动到另外一个非目标柱(B或C柱均可，假设移到B柱）上，此时C和D柱可以作为中间柱。移动次数为：f[j]；第二步：再把原A柱上剩下的i-j个盘子在3根柱子（A,C,D）之间移动，最后移动到目标柱D上,因为此时B柱不能作为中间柱子使用，移动次数为：2i-i-1;第三步：最后把非目标柱B上的J个盘子移动到目标柱上，次数为：f[j].通过以上步骤我们可以初步得出：F[i]=2f[j]+2i-j-1,可取的范围是1v=jvl,所以对于不同的j,得到的f[j]可能是不同的，本题要求最少的移动次数，所以F[i]=min｛2f[j]+2i-j-1｝，主要代码如下：Fori:=1tondoFork:=1toIdoIf（f[i]>f[k]+f[k]+a[i-k]-1）thenf[i]:=f[k]+f[k]+a[i-k]-1;f[n]即为所求。本题采用了递推的策略，同时采用了动态规划的思想解决了问题。Hanoi（A，C，B，k+1）=Hanoi（A,B,C,k）+Move（A,C,k+1）+Hanoi（B,C，A，k）;整个过程中盘子k+1只移动一次A->C为逆序对应着2吐。对于任意盘子m<k+1,m盘子的移动由两部分组成一部分是前半部分Hanoi（A,B,C,k）以及后半部分的Hanoi（B,C，A，k）组成。显然有如果m在Hanoi（A,C,B,k）轨迹顺序的话，则m在Hanoi（A,B,C,k）以及Hanoi（B,C，A，k）都是逆序。反之亦然。这两部分衔接起来就会证明m在Hanoi（A，C，B，k）和Hanoi（A，C，B，k+1）中是反序的。同时有Hanoi塔中最大的盘子永远是逆序且只移动1步，A->C。这样的话：m=k+1，在Hanoi（A，C，B，k+1）中是逆序。m=k，由于在Hanoi（A，C，B，k）中是逆序的，所以Hanoi（A，C，B，k+1）中是顺序的。m=k-1，由于在Hanoi（A，C，B，k-1）是逆序的，所以Hanoi（A，C，B，k）是顺序的，所以Hanoi（A，C，B，k+1）是逆序的。依次下去……结论得证。总结：在n个汉诺中n，n-2,n-4 是逆序移动，n-1，n-3，n-5 是顺序移动。PROGRAMhanoi;｛樊塔问题的非递归解法｝varn:integer;procedurehanoi（n:integer;x,y,z:char）;label0,1,2,3;types=recordadr,np:integer;xp,yp,zp:charend;vart:s;stack:array[1..100]ofs;sp:integer;beginsp:=0;t.adr:=3;t.np:=n;t.xp:=x;t.yp:=y;t.zp:=z;sp:sp+1;stack[sp]:=t;0:t:=stack[sp];ift.np=1thenbeginwriteln(t.xp,\'--\',t.np,\'-->\',t.zp);caset.adrof0:goto0;1:goto1;2:goto2;3:goto3endend;t.adr:=1;t.np:=t.np-1;t.xp:=stack[sp].xp;t.yp:=stack[sp].zp;t.zp:=stack[sp].yp;sp:sp+1;汉诺双塔问题2009-05-1715:41汉诺双塔问题【问题描述】给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘足不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：每次只能移动一个圆盘；A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n,输出An。【输入】输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。【输入输出样例1】hanoi.inhanoi.out12输入输出样例2】hanoi.inhanoi.out26限制】对于50%的数据，1<=n<=25对于100%的数据，1<=n<=200提示】设法建立A与A』勺递推关系式。n n-1【试题分析】根据给定样例推算，可得最精简的算法如下当n=1时，An=(22-2)=2当n=2时，An=(23-2)=6当n=3时，An=(24-2)=14当n=4时，An=(25-2)=30当n=5时，An=(26-2)=62即：An=2(n+i)-2【飞鱼于斐提供的参考程序】PROGRAMEX4(Input,Output);VARn:Integer;an:Longint;Procedurehanoi(varn:Integer);VARi:Integer;Beginan:=1;Fori:=1ton+1Doan:=an*2;an:=an-2;End;BeginAssign(Input,'hanoi.in');Assign(Output,'hanoi.out');Reset(Input);Rewrite(Output);Readln(Input,n);hanoi(n);Write(Output,an);Close(Input);Close(Output);End.标准程序typeab=array[1..10000]oflongint;varlen,i,j,n:longint;a:ab;beginreadln(n);fillchar(a,sizeof(a),0);a[1]:=1;len:=1;fori:=1ton+1dobeginforj:=1tolendoa[j]:=a[j]*2;inc(len);forj:=1tolendobegininc(a[j+1],a[j]div10);a[j]:=a[j]mod10;end;if(a[len]=0)and(len>0)thendec(len);end;dec(a[1],2);fori:=lendownto1dowrite(a[i])end.考虑一下如果是四根柱子呢？stack[sp]:=t;goto0;1:sp:=sp-1;t:=stack[sp];writeln(t.xp,\'--\',t.np,\'-->\',t.zp);t.adr:=2;t.np:=t.np-1;t.xp:=stack[sp].yp:=stack[sp].xp;t.zp:=stack[sp].zp;sp:=sp+1;stack[sp]:=t;goto0;2:sp:=sp-1;t:=stack[sp];caset.adrof0:goto0;1:goto1;2:goto2;3:goto3end;3:sp:=sp-1end;BEGIN{Main}write(\'Inputn:\');read(n);hanoi(n,\'A\',\'B\',\'C\')END.6.汉诺双塔问题【问题描述】给定A、E、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘足不加区分的(下图为n=3的情形)。现要将这些圆盘移到c柱上，在移动过程中可放在B柱上暂存。要求：每次只能移动一个圆盘；A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设A为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n,输出A。n n【输入】输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数A。n输入输出样例1】hanoi.inhanoi.out12输入输出样例2】hanoi.inhanoi.out26限制】对于50%的数据，1<=n<=25对于100%