浙教版信息技术选修1 迭代和递归

4.3迭代和递归《支付宝积分兑豪礼》必修一《数据与计算》第四章计算与问题解决任务一：迭代求解积分数为了促进消费，支付宝平台开展消费赢积分活动。规则如下：从4月1日起至4月21日（每天只记一次），第1、2次消费积1分,第3次积2分，第4次积3分，第5次积5分，第6次积8分....以此类推，活动结束时最多能积多少积分？+2+1+1+37消费1次2次3次4次5次6次7次8次9次...积分112358132134...你发现了什么规律？问题分析意大利数学家列昂纳多·斐波那契（LeonardoFibonacci）《计算之书》斐波那契数列：1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始，每一项都等于前两项之和。f1=f2同时f2=f1+f2

像这种重复反馈的过程称之为迭代。每一次迭代的结果会被用作下一次迭代的初值。迭代——概念、三个关键步骤迭代变量：迭代关系（变量变化）：f1f2f1+f2112123235358f1,f2=f2,f1+f2

多重赋值：在同一行代码中同时为多个变量赋值。语法格式：变量名1,变量名2=表达式1,表达式2右边的表达式先计算出结果，再赋值给左边的变量。迭代控制（迭代范围）：1，1，2，3，5，8，13，21，34，55，89……n3~nf1；f2迭代算法的3个关键步骤迭代——代码、特点活动1：打开程序，根据流程图补充代码，输出活动结束时最多赢得的积分。思考：将活动次数修改为100，观察输出的数值特点及运行效率。迭代通常用来解决大规模的数学计算问题。迭代关系迭代控制迭代变量任务二：遍历积分兑豪礼此次活动推出的积分兑换项目如下表。请你编程查看所有消费次数对应的积分数。积分兑换商品最少消费次数积分10001000个花呗金1715973000哈啰单车30元骑行券1941815000菜鸟50元寄件优惠券20676510000100元话费抵扣券2110946活动2：参考“样例”补全代码,输出消费21次可获得的积分列表，并填表格。样例递归:直接或间接地调用自身的方法。递归思想:把规模较大问题转化为规模较小的同类问题，通过逐个解决小问题最终解决大问题。递归——概念德罗斯特效应分——治——合毕达哥拉斯树递归——两个要素递推f(1)=f(2)=1回归f(5)=5消费1次2次3次4次5次6次7次8次9次...积分112358132134...（1）递推关系：大问题通过递归关系分解为小问题。（2）结束条件：确定递归到何时终止。斐波那契数列递推式递归——代码、特点活动3：将活动2中的2个程序都修改为输出40项，分别运行程序，哪个效率高？为什么？递归重复调用建立的函数，耗费大量时间和内存。递推关系结束条件任务三：递归游戏赢积分参与闯关小游戏也可以获得积分。老师想玩汉诺塔游戏赢5000分，请你编程求解通关步骤。汉诺塔问题有3根相邻的柱子，标号为A,B,C，A柱上从下到上按金字塔状叠放着8个不同大小的圆盘，要把所有盘子一个个移动到柱子C上，并且每次移动同一根柱子上不能出现大盘子在小盘子上方，应该怎么移动呢？3个步骤：

（1）把n-1个盘子由A--B;递归——汉诺塔

（2）把1个盘子由A--C;

（3）把n-1个盘子由B--C;……重复以上步骤，直至剩1个盘子。结束条件递归——代码活动4：补全代码，输出8层汉诺塔的通关步骤。（1）结束条件：（2）递推关系：hanno（盘子个数，原柱，中间柱，目标柱）盘子个数是1实现简单代码可读性好课堂总结算法迭代递归概念要素特点实例相同点重复反馈重复调用自身迭代变量、迭代关系式、结束条件递推关系式、结束条件代码运行效率高实现简单、代码