教科版 高二选择性必修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手工计算斐波那契数列用两张透明的卡片，用卡片依次盖住相邻的两项，并把盖住的两项求和可以得出下一项。深色单元格表示盖住的第1项，浅色单元格表示盖住的第2项，红色数字表示求出的项。 任务一 用迭代法解决斐波那契问题 活动1手工计算斐波那契数列用上面的方法来求斐波那契数列的第8项，共需要6轮。(1) 最开始只有两个初始的数;(2)每一轮都利用已经求出的最后两项计算出下一项斐波那契数;(3)为了求出第8项，需要依次求出第3项、第4项，直到第7项。每操作一轮，就离目标更近;(4)经过6轮求出第8项斐波那契数。请用上面的方法计算出更多斐波那契数，并写在横线上。1,1, 2,3, , , , , , , , , , 581321345589144233迭代迭代是从初始值出发，通过一系列步骤来逐步逼近问题最终解的过程。例如，在上面求斐波那契数的活动中，初始值为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项。 任务一 活动2利用迭代法解决斐波那契问题通过以上分析，用fib函数求第n项斐波那契数，代码如下。01.#求第n项斐波那契数02. def fib(n):03.#n小于3时04.if n<3:05.return 106.#n大于等于3时07.a=b=108.for i in range(3,n+1):09.c=a+b10.a=b11.b=c12.breturn c13.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。请在图中横线上填写各个任务的答案。递归函数直接或间接调用自身称为递归。递归把一个大问题分解为规模更小的同类问题来求解。因为是同一类问题，所以还是调用原来的函数，只是函数的调用参数有一些变化。通过递归，并在问题足够小的时候直接给出简单解，只需少量的代码就可以解决复杂的问题。 任务二用递归法解决斐波那契问题 活动1再探斐波那契数列求解第n个斐波那契数的任务可以分解为两个更小的任务。在函数执行时，通过函数的递归调用实现任务的分解与结果的合成。请补全下面的代码。 任务二 活动2用递归法解决斐波那契问题01. def fib(n):02. if n==1 or ： #n=1或n=2时03 .return 104.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 .return1lenOfNum(n//10)+13.拓展练习分解质因数是把一个合数写成几个质数相乘的形式，比如18=2*3*3。个数的质因数并不容易直接看出，手工分解质因数又比较麻烦，请用迭代和递归方法，分别编写程序，分解质因数。分解质因数是把一个合数写成几个质数相乘的形式，比如18=2*3*3。个数的质因数并不容易直接看出，手工分解质因数又比较麻烦，请用迭代和递归方法，分别编写程序，分解质因数。4.课堂小结迭代和递归是计算机解决问题的常用的方法，但不是计算机特有的方法，也是人类解决问题常用的方法，因而具有广泛的应用情境。迭代是直面问题，一次做一点。不断逼近，最终解决问题。递归是把大任务分解为更小的任务。请同学们认真完成教材中的拓展练习2哦！下节课见！