汉诺塔步数与层数的关系（侯瑞泽 刘一帆 张哲晨）.docx

《汉诺塔步数与层数的关系（侯瑞泽 刘一帆 张哲晨）.docx》由会员分享，可在线阅读，更多相关《汉诺塔步数与层数的关系（侯瑞泽 刘一帆 张哲晨）.docx（5页珍藏版）》请在第一文库网上搜索。

1、汉诺塔步数与层数的关系问题背景：汉诺塔是根据一个传说形成的一个问题。汉偌塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。传说将所有黄金圆片移完，宇宙就会爆炸关于汉诺塔的经典问题：有三根相邻的柱子，标号为A,B,C, A柱子上从卜.到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至

2、少需要多少次移动。题目要求：1.在小圆盘上不能放大圆盘。2 .在三根柱子之间一回只能移动一个圆盘。3 .只能移动在最顶端的圆盘。模型建立令f (x)为x个圆片时所需要的最少步数(1)当n=l时只需将A柱圆片移至C柱此时，f (1) =1第一层(2)当n=2时将A柱上第一个圆片移至B柱将A柱上第二个圆片移至C柱将B柱上的圆片移至C柱由此猜测，f (x) = 2(x)-1以下给出证明设A柱上有x个圆片，则移动x-1个圆片的步数为f(x-l)那么 f(x)=2f(x-l)+l(即先把(x-1)个圆盘移到B柱，再将最后一个圆盘移到C柱，再将(x-1)个圆盘移到C柱)等号两侧同时加1W： f(x)+l=

3、2(f(x-l)+l)令 F(x)=f(x)+1则 F(x)=2F(x-l)其中F=f+1=1+1=2所以，F(x)=2,4,8,2n所以 f(x)=F(x)-l=2八(x)-l以下给出汉诺塔二进制的解法拿从0记到十进制15为例0000- 0001 - 0010 - 0011 - 0100 - 0101 - 0110 - 0111- 1000- 1001 - 1010 - 1011 -1100 - 1101 - 1110 - 1111 1000 是数字 8,我们可以发现从 0 记到15的过程其实是对称的从0记到7, 一共经加了七次(可以数一下第一行的箭头数)加一，实现了由7加到8再从8记到15

4、,同样加了七次(数一下最后一行的箭头数)0000 - 0001即把0从第一根柱子移到右边的柱子上 1 IABC00010001 - 0010就将1号盘移动到剩余的柱子上1B00100010 - 0011个位数加一，将0号盘移动到右边柱子上0011-0100我们的数字又加了一0100位，将2号盘向右移动如果0已经在最右的柱子上了就把它移回第一根柱子0100-0101,又是个位数字加一，可是。号盘子没有可以继续右移的柱子了，起始柱子上X 1 1ABC01010101 -0110应该移动1号盘子，可是既没有可以右移的柱子，起始的放在中间柱子上吧.L1 IABC01100110 -0111又是个位数由

5、0加1,将它移动到右边的柱子I jlABC10000111 - 1000从7数到8 了,将3号盘子右移接下来的过程，就和刚才的一样，实质上是抛弃千位，从000记到111我们可以惊奇的发现，这个流程真的和我们正常做汉诺塔问题完全一致 实际上，这个做法是规定了二进制数加一时，应该进行什么样的模拟操作我们规定移动为向右移动一根柱子，检查条件，无法放下就换下一根，且末尾柱子的下一根，是起始柱子另外，某一位数，由。变为1,就挪动代表该位的盘子，比如”个位 00-01则移动0号盘子在这样的规则下，非常奇异地，它符合了汉诺塔最优解的流程现在我们再看背景中的问题如果有64个圆片则可64)=2八64-1=18446744073709551615 步如果一个人一秒钟可以移动一片那么全部移完需要584942417355年，显然以人类现在的水平是无法做到的