河内塔问题讲解.ppt

河内塔问题 河内塔问题 传说中开天辟地的神勃拉玛在贝拿勒斯的圣庙里留下了三根金刚石的棒，第一根上面套着64个金环，最大的一个在底下，其余的一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。相传神同时发了咒语，当所有的金环全部移完时，就是世界末日到来的时候。那么，众僧们要移动多少次呢？ 三个珠子的移动图解：三个珠子的移动只有两种移动方法：如果第一次移动时，把最小红珠子放到③号杆上是优选法。如下： （一）原题图：?????????????????? （二）移动第一次： ???????? （三）移动第二次：?????????????（四）移动第三次： ??? （五）移动第四次：??????????????（六）移动第五次： ??? ??? （七）移动第六次：??????????????（八）移动第七次： ??? 四个珠子的移动图解：??? 四个珠子：开始第一个珠子要放在②号杆上： （一）原题图：??????????????????（二）第一次移动： ???? ??? （三）第二次移动：??????????????（四）第三次移动： （五）第四次移动：??????????????（六）第五次移动： ?????? （七）第六次移动：??????????????? （八）第七次移动： （九）第八次移动：??????????????（十）第九次移动： ?? ???? （十一）第十次移动：??????? （十二）第十一次移动： （十三）第十二次移动：??????（十四）第十三次移动： ??? （十五）第十四次移动：??????????（十六）第十五次移动： ??? 河内塔问题移动次数最少的规律 珠子的个数∕个 最少移动的次数∕次 1个珠子 1 2 3 3 7 4 15 5 31 6 63 ┋ ┋ 64个金环，众僧们要移动18446744073709511615次 * “河内塔问题” 1、河内有①号、②号、③号三个柱子，你能借助②号柱把①号柱上的珠子移到③号柱而不改变珠子的上下顺序吗？ 最少移动多少次？ 移动规则如下： ??? （1）每次只能移动一个珠子； ??? （2）大珠子不能放到小珠子上面。 一年有多少秒？（ 60×60×24×365）秒 需要多少年？[18446744073709511615÷ (60×60×24×365)] ≈5846亿年 *