教科版（2019） 高二选择性必修1信息技术第3单元第1课《迭代与递归》课件

3.1迭代与递归 高中信息技术/教科版/选择性必修1 目录 1.问题导入 2.新课讲授 3.拓展练习 4.课堂小结 1.问题导入 同学们，对于不能一次性解决的问题，比如要清扫一遍操场，你怎样做呢？ 一次扫一点，积少成多，最终完成操场的清扫 把操场划分成不同区块，分派给各个班级，各班级再分派给各位同学，各位同学完成后报告给班级，班级再报告给你，你最终确认完成操场的清扫。 愚公移山法 不断做某种操作，直到完成任务。 任务分解法 通过不断分解任务，直到任务容易解决为止。 在计算机中，解决一个比较大的问题时也可以用两种方法：一种是不断完成任务的一小部分，直到最后完成任务；另一种是不断分解问题，直到问题容易解决为止。 找钥匙开门和将大象装进冰箱分别属于什么方法？ 以上两种解决问题的方法，是人类解决大问题的两种常用方法，计算机解决问题也会用到这两种方法，它们分别叫迭代法和递归法。下面来学习这两种方法。 2.新课讲授 任务一 用迭代法解决斐波那契问题 活动1手工计算斐波那契数列 螺旋曲线可以由一系列正方形内90° 的圆弧连接而成，如图所示。假设最小的两个正方形的边长为1，则这一系列正方形的边长依次为1,1，2，3，5，8，……。你能发现数列的规律吗？ 想一想 通过观察发现，第1项是1，第2项是1，从第3项开始每项等于前两项的和，这个数列就是斐波那契数列。 任务一 用迭代法解决斐波那契问题 活动1手工计算斐波那契数列 自然界中的许多现象都与斐波那契数列数列相关，甚至前后两项的比值也逐渐接近0.618的黄金比例。 用两张透明的卡片，用卡片依次盖住相邻的两项，并把盖住的两项求和可以得出下一项。 如何知道第8个斐波那契数是什么？ 深色单元格表示盖住的第1项，浅色单元格表示盖住的第2项，红色数字表示求出的项。 任务一 用迭代法解决斐波那契问题 活动1手工计算斐波那契数列 填一填 用上面的方法来求斐波那契数列的第8项，共需要6轮。 (1) 最开始只有两个初始的数; (2)每一轮都利用已经求出的最后两项计算出下一项斐波那 契数; (3)为了求出第8项，需要依次求出第3项、第4项，直到第7项。每操作一轮，就离目标更近; (4)经过6轮求出第8项斐波那契数。 请用上面的方法计算出更多斐波那契数，并写在横线上。 1,1, 2,3, , , , , , , , , , 5 8 13 21 34 55 89 144 233 迭代 迭代是从初始值出发，通过一系列步骤来逐步逼近问题最终解的过程。 例如，在上面求斐波那契数的活动中，初始值为1、1两项，从这两项出发，依次求出第3项、第4项··..··，每轮通过最后两项相加得到新的一项，每一轮都更接近第8项并最终达到第8项 任务一 用迭代法解决斐波那契问题 活动1手工计算斐波那契数列 任务一 活动2利用迭代法解决斐波那契问题 分析上面的手工操作，使用了两张透明卡片。我们把前一张透明卡片称为变量a，把后一张透明卡片称为变量b，把待计算的斐波那契数称为变量c。 求斐波那契数第8项过程中变量值的变化规律如图所示。 任务一 活动2利用迭代法解决斐波那契问题 通过上面的算法分析可知，计算斐波那契数列的过程就是不断做以下操作的过程。 用代表后两项的变量a和b计算出新的项c: a+b →c 然后让a和b指向新的最后两项，以便下一轮还可以使用a和b计算出新的c。 整个程序就是控制以上过程从第3项依次计算到第8项。 想一想 想一想，下面两步的先后顺序可以交换吗? b→a c→b 任务一 活动2利用迭代法解决斐波那契问题 通过以上分析，用fib函数求第n项斐波那契数，代码如下。 01.#求第n项斐波那契数 02. def fib(n): 03.#n小于3时 04.if n<3: 05.return 1 06.#n大于等于3时 07.a=b=1 08.for i in range(3,n+1): 09.c=a+b 10.a=b 11.b=c 12.breturn c 13.print(fib(8)) 利用迭代法解决问题的要点 (1)确定代的起点。 (2)确定逼近最解的操作。 (3)控制代过程 任务一 活动3利用迭代法解决问题 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。 我国古代的《九章算术》中记载了“更相减损术”，即求两个整数最大公约数的方法: (1)如果两个数相等，则找到了最大公约数; (2)否则，从大的数中减去小的数: (3)重复操作(2)，直到条件 (1) 满足，得到最大公约数 请补全下面的代码。 任务一 活动3利用迭代法解决问题 01.#求两个整数a，b的最大公约数 02.def gxjs(a,b): 03.while .#a和b不等 04.if a>b: 05.a=a-b #大数减小数 06.else: 07. . 08.return a #a与b相等时，找到最大公约数 a!=b: b=b-a 再探斐波那契数列 任务二用递归法解决斐波那契问题 活动1再探斐波那契数列 小梅研究了迭代法的算法及程序，感到非常有趣。她提出了这样的猜想：既然一个大的斐波那契数由两个更小的数构成，那么计算斐波那契数的任务也可以通过任务的分解来完成。 比如求fib(6)可以分解为求fib(5)和fib(4)，它们又可以继续分解，最终都可以分解为求fib(1)或fib(2)。 任务二用递归法解决斐波那契问题 活动1再探斐波那契数列 如图所示，小梅用这种方法来求第6个斐波那契数，箭头表示任务分解的方向。当分解到fib(1)或fi(2)时，得到答案1，然后再依次向回计算大一些任务的答案。比如fib(3)=fib(1)+fib(2)，得到fib(3)=2。fib(4)=fib(2)+fib(3)，得到fb(4)=3。请在图中横线上填写各个任务的答案。 可以看到，小梅提出的这种方法确实能计算出第n项斐波那契数。小梅把求第n项斐波那契数的任务表示如下: 递归 函数直接或间接调用自身称为递归。递归把一个大问题分解为规模更小的同类问题来求解。因为是同一类问题，所以还是调用原来的函数，只是函数的调用参数有一些变化。通过递归，并在问题足够小的时候直接给出简单解，只需少量的代码就可以解决复杂的问题。 任务二用递归法解决斐波那契问题 活动1再探斐波那契数列 求解第n个斐波那契数的任务可以分解为两个更小的任务。在函数执行时，通过函数的递归调用实现任务的分解与结果的合成。请补全下面的代码。 任务二 活动2用递归法解决斐波那契问题 01. def fib(n): 02. if n==1 or ： #n=1或n=2时 03 .return 1 04.else: 05.return fib(n-1)+fib( ） #否则，分解任务 06.print(fib(6)) n==2 n-2 使用递归法解决问题的要点 (1)确定问题最小规模的简单解。 (2)把问题表示为更小规模的相同问题的组合。 (3)通过调用自身来解决问题。 想知道一个正整数n由几个数字组成吗?这个问题有一个最简单的情况，当正整数n小于10时，答案为1。否则，答案为整数n去掉个位数后的位数加1。如果用lenOfNum(n)表示求正整数n的位数，以上的递归法可以表示为： 任务二 活动3用递归法解决问题 01.#求正整数n的位数 02..def lenOfNum(n): 03.if n<10: #小于10时 04. . 05.else: #大于等于10时 06.return . return1 lenOfNum(n//10)+1 3.拓展练习 分解质因数是把一个合数写成几个质数相乘的形式，比如18=2*3*3。个数的质因数并不容易直接看出，手工分解质因数又比较麻烦，请用迭代和递归方法，分别编写程序，分解质因数。 def fj(n): i=2 while n!=1: if n% i==0: if n!=i: print(i,"*“,end="") else: print(i) n=n//i else: i=i+1 n=12 print(n,"= ",end="") fj(n) 迭代法 分解质因数是把一个合数写成几个质数相乘的形式，比如18=2*3*3。个数的质因数并不容易直接看出，手工分解质因数又比较麻烦，请用迭代和递归方法，分别编写程序，分解质因数。 def fj(n): i=2 while n% i! =0: i=i+l if i==n: print(i) else: print(i,"*“,end="") fj(n//i) n=123456 print(n,"=",end=“") fj(n) 递归法 4.课堂小结 迭代和递归是计算机解决问题的常用的方法，但不是计算机特有的方法，也是人类解决问题常用的方法，因而具有广泛的应用情境。迭代是直面问题，一次做一点。不断逼近，最终解决问题。递归是把大任务分解为更小的任务。 请同学们认真完成教材中的拓展练习2哦！ 下节课见！ $$