您的位置:首页 >生活 >

汉诺塔游戏口诀4层(汉诺塔游戏口诀)

大家好,我是小新,我来为大家解答以上问题。汉诺塔游戏口诀4层,汉诺塔游戏口诀很多人还不知道,现在让我们一起来看看吧!

1、汉诺塔算法介绍:

2、一位美国学者发现的特别简单的方法:只要轮流用两次如下方法就可以了。

3、把三根柱子按顺序排成“品”字型,把所有圆盘按从大到小的顺序放于柱子A上,根据圆盘数量来确定柱子排放的顺序:

4、n若为偶数的话,顺时针方向依次摆放为:ABC;而n若为奇数的话,就按顺时针方向依次摆放为:ACB。这样经过反复多次的测试,最后就可以按照规定完成汉诺塔的移动。

5、因此很简单的,结果就是按照移动规则向一个方向移动金片:

6、如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C。

7、扩展资料:

8、汉诺塔经典题目:

9、三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,且每次移动同一根柱子上都不可以出现大盘子在小盘子上方的情况。

10、至少需要几次移动的问题,我们设移动次数为H(n)。

11、把上面n-1个盘子移动到柱子C上,把最大的一块放在B上,把C上的所有盘子移动到B上,由此我们得出表达式:

12、H⑴ = 1

13、H(n) = 2*H(n-1)+1 (n>1)

14、很快我们就可以得到H(n)的一般式为:

15、H(n) = 2^n - 1 (n>0)

16、且这种方法的确是最少次数的,证明非常简单,可以尝试从2个盘子的移动开始证,可以试试。

17、进一步加深问题:

18、假如现在每种大小的盘子都有两个,并且是相邻的,设盘子个数为2n,问:⑴假如不考虑相同大小盘子的上下要几次移动,设移动次数为J(n);⑵只要保证到最后B上的相同大小盘子顺序与A上时相同,需要几次移动,设移动次数为K(n)。

19、⑴中的移动相当于是把前一个问题中的每个盘子多移动一次,也就是:

20、J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2

21、在分析⑵之前,我们来说明一个现象,假如A柱子上有两个大小相同的盘子,上面一个是黑色的,下面一个是白色的,我们把两个盘子移动到B上,需要两次。

22、盘子顺序将变成黑的在下,白的在上,然后再把B上的盘子移动到C上,需要两次,盘子顺序将与A上时相同,由此我们归纳出当相邻两个盘子都移动偶数次时,盘子顺序将不变,否则上下颠倒。

23、回到最开始的问题,n个盘子移动,上方的n-1个盘子总移动次数为2*H(n-1),所以上方n-1个盘子的移动次数必定为偶数次,最后一个盘子移动次数为1次。

24、讨论问题⑵:

25、综上可以得出,要把A上2n个盘子移动到B上,可以得出上方的2n-2个盘子必定移动偶数次,所以顺序不变,移动次数为:

26、J(n-1) = 2^n-2

27、然后再移动倒数第二个盘子,移动次数为2*J(n-1)+1 = 2^(n+1)-3,

28、最后移动最底下一个盘子,所以总的移动次数为:

29、K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5

30、参考资料:

31、汉诺塔(益智玩具)-百度百科

本文到此讲解完毕了,希望对大家有帮助。

免责声明:本文由用户上传,如有侵权请联系删除!