递归的应用场景(3) 问题的求解过程是递归的
递归的应用场景（3） 问题的求解过程是递归的
示例1：Hanoi Tower(汉诺塔)问题 3问题描述：设有A、B、C3个塔座 ,在塔座A上有一叠共n个圆盘 ☑自上而下，由小到大地叠在一起 ☑自上而下依次编号为1,2，，n ·问题：要求将塔座A上的圆盘全部移到塔座C上，仍按同样 顺序叠置。在移动圆盘时遵守以下规侧： ☑每次只允许移动1个圆盘 ☑任何时刻都不允许将较大的圆盘压在较小的圆盘之上 ☑在规侧1和2的前提下，可将圆盘移至任何一塔座上
示例1：Hanoi Tower（汉诺塔）问题 问题描述：设有A、B、C3个塔座 • 在塔座A上有一叠共n个圆盘 自上而下，由小到大地叠在一起 自上而下依次编号为1,2,…,n • 问题：要求将塔座A上的圆盘全部移到塔座C上，仍按同样 顺序叠置。在移动圆盘时遵守以下规则： 每次只允许移动1个圆盘 任何时刻都不允许将较大的圆盘压在较小的圆盘之上 在规则1和2的前提下，可将圆盘移至任何一塔座上
用递归技术求解汉诺塔问题 3将3个盘子从A移至C,以B为辅助(7步完成) (1)1#A->C B A B (2)2#A->B (3)1#C->B A A B C (4)3#A->C (5)1#B->A (6)2#B->C (7)1#A->C
用递归技术求解汉诺塔问题 将3个盘子从A移至C，以B为辅助（7步完成） （1）1#A->C （2）2#A->B （3）1#C->B （4）3#A->C （5）1#B->A （6）2#B->C （7）1#A->C
用递归技术求解汉诺塔问题 R将4个盘子从A移至C,以B为辅助 B A A B
用递归技术求解汉诺塔问题 将4个盘子从A移至C，以B为辅助
汉诺塔问题的规模 3一般的Hanoil塔玩具不超过8片 ·如果n=8,需移动255次 ·如果n=10,需移动1023次 ·如果n=15,需移动32767次 ·如果n=20,需移动1048575次（超过一百万次） ·如果n=64,需移动264-1次（超过一百万次） ☑如果每秒移动一块圆盘，需5845.54亿年 ☑按照宇宙大爆炸理论推测，宇宙的年龄也仅为137亿年
汉诺塔问题的规模 一般的Hanoi塔玩具不超过8片 • 如果n=8，需移动255次 • 如果n=10，需移动1023次 • 如果n=15，需移动32767次 • 如果n=20，需移动1048575次（超过一百万次） • 如果n=64，需移动264-1次（超过一百万次） 如果每秒移动一块圆盘，需5845.54亿年 按照宇宙大爆炸理论推测，宇宙的年龄也仅为137亿年