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