选修1算法与程序设计《第三节第三节递归法与问题解决》公开课PPT课件优质课下载

选修1算法与程序设计《第三节第三节递归法与问题解决》公开课PPT课件优质课下载

把原问题转化为规模缩小了的同类问题的子问题。然后调用自己（函数或过程）来表示问题的解。

递归的两个过程：1.递推（递推公式） 2.回归（边界条件）

问题1——猴子吃桃

有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?

分析问题1

由题意可知第10天桃子数量为1

递推关系为

编写程序

运行程序，求出结果。

问题2——下楼梯

有一段楼梯，有10级台阶，你每次可以下1-2级台阶，问下完这10级台阶一共有多少种下法。

分析问题2

1.由n级台阶（n>=3）往下下只有两种可能，下到n-1级台阶或者下到n-2级台阶。

2.只有1级台阶的时候，下法只有1种。

3.只有2级台阶的时候，下法只有2种。

编写程序

运行程序，查看结果。

问题3——汉诺塔

在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

汉诺塔问题：

问题1：请编写程序输出移动步骤。

问题2：请计算移动64片金片需要多少步。

汉诺塔

汉诺塔问题分析

汉诺塔问题分析