活动用递归法求解“兔子问题”.ppt

1、2019年5月，学校：四川省建州中学，第3章，第4节，回归方法，算法与程序设计，上海科技教育与教育版学会，教师：张元福，首先介绍概念，有4个人排成一队。当被问及最后一个人的身高时，他说他比第三个人高2厘米；当被问到第三个人的身高时，他说他比第二个人高2厘米；当被问到第二个人的身高时，他说他比第一个人高2厘米；最后，我问第一个人的身高，他说是170厘米。第四个人的身高是多少？你有多高？我比她高2厘米，比他高2厘米，比她高2厘米，高170厘米。你能算出我的身高吗？要求第四个人的高度必须首先知道第三个人的高度，第三个人的高度取决于第二个人的高度，第二个人的高度又取决于第一个人的高度，每个人的高度比前

2、一个人高2厘米。这类问题是典型的递归问题。通过分析问题可以得到递推公式：3 .递归过程。递归问题由两部分组成：一部分可以直接处理，即递归的终止条件是问题的初始条件，如h(1)=170；另一部分不能直接处理，因此必须将原问题转化为与原问题相似且更接近终止条件的新问题。如果H(n)=H(n-1) 2，原问题是H(n)，新问题是H(n-1)，显然更接近于H(1)。递归过程可分为两个阶段：递归阶段的工作是不断地将原问题转化为另一个类似的新问题，直到一个新问题能够根据已知条件计算出结果。例如，图的左下角是递归过程。返回阶段是递归的逆过程，从递归结束开始，逐步计算结果，直到计算出原问题的结果。例如，图表右

3、侧的对角线上部是返回过程。2.基础活动：用递归的方法解决兔子问题，一个农民养了一对兔子，他发现兔子在出生后的第二个月就长成了大兔子，每对大兔子每个月可以繁殖一对兔子。如果一年内没有死亡，一年内农民将有多少对兔子？1。提问。试着列出每个月的兔子对数：假设Fn代表第n个月的兔子对数。如果F1=1，F2=1，F3=F1 F2，那么Fn=Fn-1，Fn-2。仔细观察并推断规则：2 .分析问题；3.设计算法。开始时，输入月数n，n=1或n=2，然后结束。结果=fi (n)，递归函数，递归调用，编程代码。专用子命令1 _单击()变暗n变暗结果变长n=文本1。文本结果=Fi(n)文本2。如果n=1或n=2，

4、则只要fi=1，否则fi=fi (n-1) fi (n-2)，如果结束函数，则结束4。写一个程序，建立一个新项目，完成界面设计。运行、5、调试并运行程序。按F8键逐句运行程序，观察程序的执行过程，记录递归函数的调用。根据观察和记录，完成以下原理图，了解递归执行过程。F (5)，F (4)，F (2)，F (3)，F (2)，(3)，(3)，(3)解决汉诺塔问题(体验活动提示)据说在古印度的一座寺庙里，僧侣们试图将一堆圆盘从一个木桩移到另一个木桩上。圆盘移动的规则是：一次只能移动一个圆盘，大圆盘不允许放在小圆盘上。你能通过编程展示僧侣的运动过程吗？1.问题分析：移动n个磁盘的问题可以转化为移动n

5、-1个磁盘的问题(发生递归):将n-1个磁盘从桩1移动到桩2，桩3作为临时存储区；将最后一个(最大的)圆盘移到木桩3上；将n-1个圆盘从木桩2移至木桩3，木桩1作为临时储存区；当n=1时，移动磁盘(递归终止条件)。这项任务完成了。使用具有四个参数的塔过程，这四个参数是：移动盘的数量；圆盘最初所在的木桩；要移动到的目标桩；临时存放磁盘的木桩。调暗为长专用子命令1 _单击()调暗为整数n=值(文本1。文本)列表1。如果n=1，则I=1列表1。另外，B I=11里斯特1。附录一附录一附录一附录一附录一附录二附录二附录一附录二附录一附录二附录三附录三附录三附录四附录四附录四附录五附录五附录六附录六附录六附录六附录六附录六附录六附录六附录六附录六附录七附录七附录七附录七附录八附录八附录七附录八附录八程序实现：运行，教学评估，4，1关于递归，下面的语句是正确的。关于递归函数