資源簡(jiǎn)介

(共27張PPT)
5.2 迭 代 與 遞 歸 （一）
—— 迭 代
冊(cè) 別：選擇性必修1
學(xué) 科：高中信息技術(shù)（浙教版）
學(xué)習(xí)目標(biāo)：
能理解迭代的算法思想。
能合理選用數(shù)據(jù)結(jié)構(gòu)，理清迭代初值，迭代式及結(jié)束迭代。
能用自然語言、流程圖、Python語言描述迭代算法。
能分析迭代算法的效率高低。
能熟練應(yīng)用迭代算法，解決生活、學(xué)習(xí)中的問題。
引入：兔子有多少對(duì)？
意大利數(shù)學(xué)家裴波那契（L．Fibonacci）在他的1228年版的《算經(jīng)》一書中記述了有趣的兔子問題：假定我們有一雄一雌一對(duì)剛出生的兔子，它們?cè)陂L(zhǎng)到一個(gè)月大小時(shí)開始懷孕（自然狀態(tài)是六個(gè)月左右），在第二月結(jié)束時(shí)，雌兔子產(chǎn)下另一對(duì)兔子，過了一個(gè)月后它們也開始繁殖，如此這般持續(xù)下去。每只雌兔在開始繁殖后每月都產(chǎn)下一對(duì)兔子，假定沒有兔子死亡，在一年后總共有多少對(duì)兔子？
時(shí)間（月） 1 2 3 4 ……
兔子（對(duì)） 1 1
2
3
算一算:
時(shí)間（月） 1 2 3 4 5 6 7 ……
兔子（對(duì)） 1 1 2 3 5
找出規(guī)律
時(shí)間 1 2 3 4 5 6 7 ……
總數(shù) 1 1 2 3 5 8
成年兔子 0 1 1 2 3 5
新小兔子 1 0 1 1 2 3
a1=1
a2=1
an=an-1+an-2(當(dāng)n>2時(shí))
算一算:
月份 成年兔 新小兔 共有的兔子
1 1 1
2 1 1
3 1 1 2
4 2 1 3
5 3 2 5
6 5 3 8
7 8 5 13
8 13 8 21
9 21 13 34
10 34 21 55
11 55 34 89
12 89 55 144
答案：
一年后總共有144對(duì)兔子。
裴波那契數(shù)列：
裴波那契數(shù)為：1，1，2，3，5，8，13 其規(guī)律是：數(shù)列中第1，2個(gè)數(shù)都是1，從第三個(gè)數(shù)起，該數(shù)是前面2個(gè)數(shù)之和，此數(shù)列稱為Fibonacci數(shù)列。
第n項(xiàng)計(jì)算公式為：Fib(n)=1 (n<=2)
Fib(n)=Fib(n-1)+Fib(n-2) (n>2)
因此從第三個(gè)元素開始循環(huán)，
Fib(3)=Fib(1)+Fib(2)
Fib(4)=Fib(2)+Fib(3)
Fib(5)=Fib(3)+Fib(4)
……
程序?qū)崿F(xiàn)(一）:
a=[1,1]
for i in range(2,12):
a.append(0)
a[i]=a[i-1]+a[i-2]
print(a[11])
#定義列表a為每個(gè)月的兔子對(duì)數(shù)，第1,2月的兔子數(shù)量為1對(duì)
#對(duì)第3個(gè)月至第12月逐一計(jì)算兔子對(duì)數(shù)
#a最后添加一個(gè)初值為0的元素，存第i個(gè)月兔子數(shù)
#求出第i個(gè)月的兔子對(duì)數(shù)(迭代表達(dá)式)
#輸出第12月的兔子對(duì)數(shù)
12個(gè)月的兔子對(duì)數(shù)用a數(shù)組（a列表）來存儲(chǔ)
程序?qū)崿F(xiàn)（二）:
a = 1
b = 1
for i in range(2,12):
c = a + b
a = b
b = c
print(c)
#定義a，b為第1月,第2月的兔子數(shù)量為1對(duì)
#對(duì)第3個(gè)月至第12月每月計(jì)算兔子對(duì)數(shù)
#當(dāng)前一個(gè)月的值b迭代前兩個(gè)月的值a
#當(dāng)月的值c迭代前一個(gè)月的值b
#輸出第12月的兔子對(duì)數(shù)
#從第3個(gè)月起兔子對(duì)數(shù)為前面兩個(gè)月的兔子對(duì)數(shù)之和
a,b,c三個(gè)變量存儲(chǔ)近三個(gè)月的兔子數(shù)
迭代算法的概念:
迭代是重復(fù)反饋的活動(dòng)，其目的通常是為了使結(jié)果符合目標(biāo)需求。
開發(fā)產(chǎn)品
反復(fù)修改
符合客戶需求
讓計(jì)算機(jī)重復(fù)執(zhí)行一組指令(或步驟)，這組指令(或步驟)每執(zhí)行一次時(shí)，都會(huì)讓變量從原值遞推出一個(gè)新值。
迭代算法三個(gè)方面：
1、確定迭代變量
2、建立迭代關(guān)系
3、控制迭代過程
一個(gè)直接或間接地不斷由舊值遞推出新值的變量；
將變量從前一個(gè)值推出其下一個(gè)值的公式(或關(guān)系)；
設(shè)定迭代結(jié)束的條件。
a = 1
b = 1
for i in range(3,13):
c = a + b
a = b
b = c
print(c)
1、確定迭代變量
a( 前2個(gè)月),b（前1個(gè)月）
2、建立迭代關(guān)系：從第3個(gè)月
起兔子對(duì)數(shù)為前面兩個(gè)月的兔
子對(duì)數(shù)之和。
1、確定迭代變量
a( 前2個(gè)月),b（前1個(gè)月）
3、設(shè)定迭代第3至第12月
迭代法求a的平方根： 教材P119
基本思路：先估測(cè)一個(gè)近似值x，然后不斷令x等于x和的平均數(shù)（迭代公式為： (n≥0)），經(jīng)過若干次迭代后，x的值將逐漸接近a的平方根（當(dāng)與值無限接近時(shí)，可看作= ，則公式 可以化簡(jiǎn)為=, 就是a的平方根）
迭代式：是什么
可終止的條件是什么
1、確定迭代變量：
2、建立迭代關(guān)系:
3、控制迭代過程:
X,初始值：是什么
迭代法求a的平方根： 教材P119
基本思路：先估測(cè)一個(gè)近似值x，然后不斷令x等于x和的平均數(shù)（迭代公式為： (n≥0)），經(jīng)過若干次迭代后，x的值將逐漸接近a的平方根（當(dāng)與值無限接近時(shí)，可看作= ，則公式 可以化簡(jiǎn)為=, 就是a的平方根）
迭代式：是什么
可終止的條件是什么
1、確定迭代變量：
2、建立迭代關(guān)系:
3、控制迭代過程:
X,初始值：是什么
=
迭代變量x的迭代過程：
迭代次數(shù) xn xn+1 ▏xn+1-xn ▏
1 1 1.5 0.5
2 1.5 1.416667 0.083333
3 1.416667 1.414216 0.002451
4 1.414216 1.414214 0.000002
當(dāng)前后兩次求出的x值（xn+1和xn）的差的絕對(duì)值（ ▏xn+1-xn ▏）
為0.000002時(shí)（即 ▏xn+1-xn ▏<=0.00001） 停止迭代，得出結(jié)果。如2的平方根約為1.414214。
（1）抽象建模
x0
x1
x1
x2
x2
x3
x3
x4
（2）設(shè)計(jì)算法
求平方根迭代程序流程圖
開始
（1）輸入a, 求x估測(cè)近似值
x0=a；x1=(x0+a/x0)/2
①若〡x1-x0〡>10-5
②迭代式x0=x1
x1=(x0+a/x0)/2
③否則〡x1-x0〡<=10-5
④輸出a 的平方根x1
〡x1-x0〡>0.00001
輸入a
輸出平方根x1
x0=x1;x1=(x0+a/x0)/2
結(jié)束
N
Y
（2）迭代求平方根
x0=a；x1=(x0+a/x0)/2
編寫求平方根迭代程序并上機(jī)調(diào)試：
#程序一：
a=int(input("請(qǐng)輸入一個(gè)需要求其平方根的數(shù)："))
x0=a
x1=(x0+a/x0)/2
while (abs(x1-x0))>0.00001:
x0=x1
x1=(x0+a/x0)/2
print(a,"的平方根約為",round(x1,6))
（3）編寫程序并調(diào)試
牛頓迭代法計(jì)算正數(shù)a的算術(shù)根
#X0,初始值a
#X1,迭代式
#X1與x0無限接近，相差0.00001
#X0由X1迭代
#X1,迭代式
#X1為a的平方根
在保留小數(shù)位數(shù)不同的情況下，程序效率差異也大
#程序二：
a=int(input("請(qǐng)輸入一個(gè)需要求其平方根的數(shù)："))
x=a/2
while ((abs((x+a/x)/2-x))>0.00001):
x=(x+a/x)/2
print(a,"的平方根約為",round((x+a/x)/2,6))
（3）編寫程序并調(diào)試
#X0,初始值a/2
#X1與x0無限接近，相差0.00001
#X0迭代式
#(x+a/x)/2為a的平方根
編寫求平方根迭代程序并上機(jī)調(diào)試：
#程序三：
a=int(input("請(qǐng)輸入一個(gè)需要求其平方根的數(shù)："))
x=a/2
while abs(x*x-a) > 1e-5:
x=(x+a/x)/2
print(a,"的平方根約為",round((x+a/x)/2,6))
（3）編寫程序并調(diào)試
#平方根X的初始值a/2
#X*X與a無限接近，相差0.00001
#X迭代式
#(x+a/x)/2為a的平方根
影響迭代算法的因素：
終止條件的設(shè)置
初始值不同
x0=a或x0=a/2
(abs(x1-x0))>0.00001
（保留5位小數(shù)位數(shù)）
(abs(x1-x0))>0.000001
（保留6位小數(shù)位數(shù)）
初始值、終止條件等直接影響算法效率
課堂小練：
利用歐幾里得算法求最大公約數(shù)的python程序，其中m和n是迭代變量，迭代關(guān)系是n→m和m%n→n，由舊值推出新值，然后循環(huán)執(zhí)行，直到余數(shù)為0，結(jié)束迭代。
m=int(input("請(qǐng)輸入數(shù)m:"))
n=int(input("請(qǐng)輸入數(shù)n:"))
while n!=0:
t=n
m=t
print( )
1.完善劃線處代碼：
n=m%n
m
課堂小練：
一個(gè)樓梯有n階，上樓可以一步上一階，也可以一步上二階。要求：編寫一個(gè)程序，輸入一個(gè)正整數(shù)n(表示樓梯階數(shù))，輸出共有多少種不同的走法可以到達(dá)第n階。
2.程序設(shè)計(jì)并調(diào)試：
f(n)=
1 n=1
2 n=2
f(n-1)+f(n-2) n>=3
課堂小練：
2.程序設(shè)計(jì)并調(diào)試：
n=int(input("請(qǐng)輸入臺(tái)階數(shù)量："))
a=1;b=2
for i in range(3,n+1):
c=a+b
a=b
b=c
if n==1 or n==2:
print(n)
else:
print(c)
生活實(shí)戰(zhàn)應(yīng)用：秋游安排車輛
某班家委會(huì)根據(jù)參加秋游的同學(xué)到達(dá)指定上車點(diǎn)時(shí)間和每位同學(xué)可以等待的時(shí)間信息，安排車輛接送參加秋游活動(dòng)同學(xué)去秋游點(diǎn)白云山腳（考慮車子座位數(shù)量<=4人）。參加秋游活動(dòng)同學(xué)到達(dá)上車點(diǎn)的時(shí)間和可以等待的時(shí)間用長(zhǎng)度為7的字符串表示，例如out.txt中第一行“ 08:11 4 xixi”表示xixi同學(xué)當(dāng)天8點(diǎn)11分到達(dá)上車點(diǎn)，最多等待4分鐘(每個(gè)同學(xué)的等待時(shí)間都小于10)，那么最晚8點(diǎn)23分出發(fā)去秋游點(diǎn)(若8點(diǎn)23分剛到的同學(xué)也一同出發(fā))。編寫 Python 程序，統(tǒng)計(jì)接送n個(gè)參加秋游活動(dòng)同學(xué)所需的最少車輛數(shù)。運(yùn)行程序，顯示所有同學(xué)提交的信息，數(shù)據(jù)已經(jīng)按到達(dá)時(shí)間先后排列，程序運(yùn)行結(jié)果顯示所需的最少車輛數(shù)。
A
（1）若將圖中第 1 行“08:11 4”數(shù)據(jù)改為“08:11 2”，程序輸出的結(jié)果是否會(huì)發(fā)生改變 （A.會(huì)改變 B.不會(huì)改變）
生活實(shí)戰(zhàn)應(yīng)用：安排車輛
（2）實(shí)現(xiàn)上述功能的部分 Python 程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
a=[];b=[];c=[];xz=4 #每輛車最多坐4人
#從文件out.txt中讀取每一行數(shù)據(jù)在列表a中，n為參加秋游人數(shù)，代碼略
for i in range(n):
b.append(0);c.append(0)
b[i]=int(a[i][:2])*60+int(a[i][3:5])
c[i]=b[i]+int(a[i][6:8])
tot=0;i=0;k=1
while i#①
j=i+1
while jif b[j]<=t:
k+=1;j+=1
else:
break
if k==xz:k=0;break
#②
tot+=1
for i in range(n):print(a[i])
print("接送所有參加秋游同學(xué)最少需要",tot,"輛車")
②i=j
①t=c[i]
這個(gè)for循環(huán)求出到指定地點(diǎn)的時(shí)間b列表，最遲離開時(shí)間c列表
tot為接送所有參加秋游同學(xué)最少需要車輛數(shù)
外循環(huán)求出當(dāng)前i同學(xué)最遲離開時(shí)間c[i]前與最早離開j同學(xué)同一輛車拼車過程
內(nèi)循環(huán)求出當(dāng)前i同學(xué)最遲離開時(shí)間c[i]前與最早離開j同學(xué)b[j]同一輛車不超過4人的拼車過程,若拼不成，j同學(xué)為另起一輛車
課堂小結(jié)
迭代算法的概念
算法思想 算法描述
迭代算法的三要素
迭代算法的數(shù)學(xué)原理與注意事項(xiàng)
程序?qū)崿F(xiàn)
學(xué)習(xí)評(píng)價(jià)
對(duì)自己的表現(xiàn)進(jìn)行客觀的評(píng)價(jià)，并思考后續(xù)完善的方向。（3=優(yōu)秀，2=一般，1=仍需加油）
評(píng)分項(xiàng) 自我評(píng)價(jià)
能計(jì)算兔子對(duì)數(shù)問題并總結(jié)迭代算法的基本思想 3 2 1
掌握迭代算法的三要素 3 2 1
能自主學(xué)習(xí)教材并用自然語言、流程圖描述迭代算法 3 2 1
能夠用Python語言描述迭代算法 3 2 1
能夠編程實(shí)現(xiàn)牛頓迭代法求根 3 2 1
能理解牛頓迭代法的數(shù)學(xué)原理、注意事項(xiàng) 3 2 1
能用迭代算法完成學(xué)習(xí)、生活中的應(yīng)用 3 2 1
課后作業(yè)
1.操作系統(tǒng)從win xp、win7、win10……,不斷更新過程可以看出,一款產(chǎn)品是不斷試錯(cuò),不斷根據(jù)用戶體驗(yàn)反饋,快速調(diào)整和完善得到的。這個(gè)例子體現(xiàn)的算法思想是 ( )
A.枚舉 B.迭代 C.解析 D.遞歸
2.利用迭代算法處理問題，需要考慮以下三個(gè)方面：
①確定迭代變量：一個(gè)直接或間接地不斷由舊值遞推出新值的變量；
② ：將變量從前一個(gè)值推出其下一個(gè)值的公式(或關(guān)系)；
③控制迭代過程：設(shè)定迭代結(jié)束的條件。
建立迭代關(guān)系式
B
課后作業(yè)
3.在程序劃線處填空題：圓周率其實(shí)就是一個(gè)圓周長(zhǎng)與直徑的比值我們通常用希臘字母π表示，其中用萊布尼茨公式是這樣的：
小新用迭代法編寫了一個(gè)Python程序用于求圓周率Pi,請(qǐng)完善程序(精確到小數(shù)點(diǎn)后6位)。
i=1；s=0;k=1
ans=0
while ① :
ans+=1
s+=k*1/i
i+=2
②
print("pi=",s*4）
print（迭代次數(shù):",ans)
1/i>＝0.00000001　
1/i>=0.000001
k＝－k
若要精確到小數(shù)點(diǎn)后8位，①空如何填寫？

展開更多......

收起↑