《第三章-算法的程序实现35-用递归法解决问题课件》高中信息技术教科版选修1-算法与程序设计.ppt

1、从前有座山，山里有个庙，庙里从前有座山，山里有个庙，庙里有个老和尚讲故事，讲什么呢？有个老和尚讲故事，讲什么呢？从前有座山，山里有个庙从前有座山，山里有个庙从前有座山从前有座山你的眼睛你的眼睛他的眼睛他的眼睛函数函数A函数函数A函数函数B 如果一个函数在定义时，直接如果一个函数在定义时，直接或间接地调用了自己，这种算或间接地调用了自己，这种算法在程序设计中统称为递归法。法在程序设计中统称为递归法。和尚移盘和尚移盘 一个庙里有三个柱子（一个庙里有三个柱子（A，B，C），第一），第一个柱子（个柱子（A）有）有7 7个盘子，从上往下盘子越来越个盘子，从上往下盘子越来越大。要求庙里的老和尚把这大。要求

2、庙里的老和尚把这7 7个盘子全部移动到个盘子全部移动到第三个柱子（第三个柱子（C）上。）上。规则：规则：1、一次只能移动一个盘子、一次只能移动一个盘子 2、移动的时候始终只能小盘子压着大盘子、移动的时候始终只能小盘子压着大盘子 3、A柱和柱和C柱不能相互直接移动。柱不能相互直接移动。第一个第一个和尚想法和尚想法 要是有一个人能把前要是有一个人能把前6个盘子移动好，我移个盘子移动好，我移动最后一个盘子，我的任务就能完成了。动最后一个盘子，我的任务就能完成了。Pan(7)=2+pan(6)*3第二个第二个和尚想法和尚想法 要是有一个人能把前要是有一个人能把前5个盘子先移动好，我个盘子先移动好，我移

3、动最后一个盘子，我的任务也能完成了。移动最后一个盘子，我的任务也能完成了。Pan(6)=2+pan(5)*3 一直找下去，直到找到第六个一直找下去，直到找到第六个和尚为止和尚为止 pan(2)=2+pan(1)*3 第七个第七个和尚移盘和尚移盘 把第一个盘子先移动到第二个柱子上，然把第一个盘子先移动到第二个柱子上，然后再移动到第三个柱子上。后再移动到第三个柱子上。Pan(1)=2 第六个第六个和尚移盘和尚移盘Pan(2)=2+pan(1)*3=8 第五个第五个和尚移盘和尚移盘Pan(3)=2+pan(2)*3=26Pan(7)=2+pan(6)*3=2186 第一个第一个和尚移盘和尚移盘Pan

4、(7)=2+pan(6)*3Pan(6)=2+pan(5)*3Pan(5)=2+pan(4)*3Pan(4)=2+pan(3)*3Pan(3)=2+pan(2)*3Pan(2)=2+pan(1)*3Pan(1)=2递归算法的实现方式递归算法的实现方式:函数的调用函数的调用和尚移盘算法的实现方式和尚移盘算法的实现方式:自定义函数的调用自定义函数的调用和尚移盘算法的自定义函数：和尚移盘算法的自定义函数：pan(n)和尚移盘算法的实现：和尚移盘算法的实现：盘子个数123456789盘子移动数2826802427282186656019682Pan(n)=2+pan(n-1)*3Pan(1)练一练练一

5、练桌面桌面:作业作业和尚移盘和尚移盘和尚移盘和尚移盘.frm递归算法有什么特点递归算法有什么特点?1、递归法：函数直接或间接地调用了自己、递归法：函数直接或间接地调用了自己3、递归必需要有结束条件、递归必需要有结束条件2、递归分为递推（问题、递归分为递推（问题下下推）与回归（结推）与回归（结果回归）两个过程果回归）两个过程4、递归函数的调用方式相当耗费计算机资源，、递归函数的调用方式相当耗费计算机资源，因而其效率比较低因而其效率比较低想一想想一想1Public Function story(byval n as integer)as integer If n=0 then end else s

6、tory=story(n-1)end if end Function想一想想一想2public sub f(byval n as long)Dim a as long a=a+n print n end sub3Public Function f(byval a as integer)as integer dim b as integer f=f(a,b)end fuction 经典数学问题经典数学问题1）1+2+3+N2）N！试一试试一试 知识回顾知识回顾 2、下面哪个问题可以用递归法解决？、下面哪个问题可以用递归法解决？（1）钻石图案）钻石图案 （2）百鸡百钱）百鸡百钱（3）加密程序）加密

7、程序 （4）汉诺塔）汉诺塔1、递归分为、递归分为（）与（与（）两个过程。两个过程。3、只要调用函数都是递归法？、只要调用函数都是递归法？4、递归法必需要有结束条件？、递归法必需要有结束条件？现实生活现实生活 一层梦境一层梦境 二层梦境二层梦境 三层梦境三层梦境 四层梦境四层梦境 现实生活现实生活 一层梦境一层梦境 二层梦境二层梦境 三层梦境三层梦境 四层梦境四层梦境 课后思考课后思考 讨论本章学习的五种算法，从程序的执讨论本章学习的五种算法，从程序的执行效率、代码编写的方便性、可读性等方面，行效率、代码编写的方便性、可读性等方面，分析它们各自的特点，指出其适用范围。分析它们各自的特点，指出其适用范围。