递归算法实例及程序实现(导学案).doc

山东省平度第一中学高二信息技术导学案撰稿：胡增军审核：朱业超55妙趣横生的算法递归教学目标知识与技能：1、 理解什么是递归算法，用递归算法的思想分析问题2、 能够应用自定义函数方法实现递归算法的编程过程与方法：参与讨论，通过思考、动手操作，体验递归算法的方法情感态度与价值：结合实例，激发数学建模的意识，培养多维度思考问题和解决问题，激发审美情感。重点与难点重点：理解什么是递归算法，会用递归算法思想分析问题；应用自定义函数方法实现递归算法的编程难点：应用自定义函数方法实现递归算法的编程学习思维导图：一、认识递归：1、小游戏：报数2、头脑风暴：举出你身边的递归的例子二、新知导学：问题：有甲、乙、丙、丁四人，从甲开始到丁（甲乙丙丁），一个比一个大1岁，已知丁10岁，问甲几岁？1分析问题：这是递归法的一道非常典型的题目因为我们可以很显然知道：假设要计算甲的年龄，那么必须知道乙的年龄；同样，算乙的必须知道丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（为方便我们给他们编号甲1，乙2，丙3，丁4），那么存在一个F(X)函数，X表示某人的编号，其规律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10这种按同一方法把问题的计算规模逐步变小的过程叫做“递归的展开”，然后要逐级代入直到求出结果，这一过程称为递归的返回 F(4)=10 F(3)=F(4)+1=11 F(2)=F(3)+1=12 F(1)=F(2)+1=132、写出递归表达式：显然，当n=4时，问题的解为10，而当n4时，问题的解可转换为：F(n)=f(n1)+13、编写程序：递归算法通常用自定义函数来实现，称为递归函数，如以上题可以写成如下函数：Function f(n as integer) as integer If n=4 then Else End ifEnd function4、调试运行程序：归结：解决递归问题的一般步骤：1 分析问题，写出递归与返回的过程2 建立数学模型（写出递归表达式） X=D 返回某个常数作为结果F（x）= F（X）返回一个自身嵌套的表达式，自身调用，直到F（X”）D作为条件终止。3 编写自定义函数代码(一般形式为)Function f(n as _ ) as _ Ifthen Else End ifEnd function4 调试运行程序三、合作探究：小猴吃桃问题: 有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?1分组讨论，推算10天吃桃的过程2、根据推算，得出的数据，填写下表：（建议先填写后四天，前六天通过调试程序，根据运行结果填写）天数12345678910桃子数3、根据推算10天吃桃的数据和本题大意讨论并写出递归表达式：假设第n天（n2) f(1)=0 f(2)=1六、课堂小结：（及时总结、不断提高!）七、课后作业：爱因斯坦的谜语1、在一条街上，有5座房子，喷了5种颜色。 2、每个房里住着不同国籍的人 3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物 问题是：谁养鱼？ 提示： 51、英国人住红色房子 2、瑞典人养狗 3、丹麦人喝茶 4、绿色房子在白色房子左面 5、绿色房子主人喝咖啡 6、抽Pall Mall 香烟的人养鸟 7、黄色房子主人抽Dunhill 香烟 8、住在中间房子的人喝牛奶9、 挪威人住第一间房 10、抽Blends香烟的人住在养猫的人隔壁 11、养马的人住抽Dunhi