資源簡介

(共20張PPT)
微項目3 用迭代算法探討數據變化的規律
學習目標
1、了解生活中的迭代現象
2、理解迭代算法的本質
3、掌握用迭代算法分析數據的變化規律
4、學會用迭代算法解決實際問題
先行組織
第一天往錢罐子里面投入1元，存錢罐總金額為1元
第二天往錢罐里面投入2元，存錢罐總金額為3元
第三天往存錢罐里面投入3元，存錢罐里面總金額為6元
那么第n天時存錢罐里面一共有多少錢？
n=int(input("存錢天數："))
s=0
for i in range(1,n+1):
___________
print("存錢罐的錢數：",s)
我們利用循環不斷執行累加求和，從原值s算出新值s，最終計算出存錢罐的錢數，這種將變量從原值遞推出一個新值的算法，我們稱之為迭代算法。
s=s+i
新知建構
迭代是重復反饋的過程，其目的通常是為了接近并達到所需的目標或結果。每一次對過程的重復被稱為一次迭代，而每一次迭代得到的結果會被用來作為下一次迭代的初始值。
·迭代的概念
·迭代的特性
迭代算法是用計算機解決問題的一種基本方法，它利用計算機運算速度快、適合做重復性操作的特點，讓計算機重復執行一組指令（或一定步驟），這組指令（或這些步驟）每執行一次，都會將變量從原值推出一個新值。
新知建構
利用迭代算法解決問題，需要做好三個方面：
·迭代算法的設計方法
·確定迭代變量
在能夠用迭代算法處理問題中，至少具有一個直接或間接地不斷有舊值推出新值的變量，這個變量就是迭代變量。
·建立迭代關系式
所謂迭代關系式，指如何從變量的前一個值推出下一個值的公式（或關系）。
·控制迭代過程
迭代過程在經過若干次重復執行以后要能結束，因此，要設定迭代結束的條件。
新知建構
n=int(input("存錢天數："))
s=0
for i in range(1,n+1):
___________
print("存錢罐的錢數：",s)
s=s+i
迭代算法：
①確定迭代變量
②建立迭代關系式
③控制迭代過程
思考：試分析上述程序的迭代變量？迭代關系式？如何控制迭代過程？
①確定迭代變量
②建立迭代關系式
③控制迭代過程
新知建構
【例1】阿福制訂了一個英語學習計劃,其中一項內容.是背單詞:第1天背1個單詞,第2天背2個單詞,第3天背3個單詞......即每天都比前一天多背1個單詞。則經過10天以后阿?？偣脖诚碌膯卧~總量為( )
A.10 B.45
C.55 D.66
新知建構
【例2】求解擴展后的正三角形個數?，F有若干邊長為1的正三角形,由多個這樣的正三角形可拼成邊長為2、3、4的正三角形，如圖所示。如果要拼合成邊長為n的正三角形，需要多少個邊長為1的正三角形呢
活動一
任務一：兔子問題（斐波那契數列）
假定我們有一雄一雌一對剛出生的兔子，它們在長到一個月大小時開始懷孕（真實情況是六個月左右），在第二月結束時，雌兔子產下另一對兔子，過了一個月后它們也開始繁殖，如此這般持續下去。每只雌兔在開始繁殖后每月都產下一對兔子，假定沒有兔子死亡，在n個月后總共有多少對兔子？
a1 = 1
a2 = 1
an=an-1+an-2(當n>2時)
時間 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1
成兔 0
總數 1
請列出求解兔子總對數an的數學表達式：
時間 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1 0 1 1 2 3 5
成兔 0 1 1 2 3 5 8
總數(an) 1 1 2 3 5 8 13
活動一
請編程實現：
a = [1,1]
n=int(input('請輸入月份：'))
for i in range(2,n+1):
_________________
a.append(x)
print(a[n])
x=a[-1]+a[-2]
時間 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1 0 1 1 2 3 5
成兔 0 1 1 2 3 5 8
總數 1 1 2 3 5 8 13
思考：試分析上述程序的迭代變量？迭代關系式？如何控制迭代過程？
數學關系式：
a1 = 1
a2 = 1
an=an-1+an-2(當n>2時)
活動二
任務二：歐幾里得算法——輾轉相除法
輾轉相除法求兩個數的最大公約數的步驟如下：
先用大的數除以小的數，得到第一個余數；
再用小的數除以第一個余數得到第二個余數；
再用第一個余數除以第二個余數，得到第三個余數；
這樣逐次用前一個余數除以后一個余數，直到余數是0為止。
那么,最后一個除數就是所求的最大公約數。
例如求1515和600的最大公約數：
第一次：用1515除以600，商2余315；
第二次：用600除以315，商1余285；
第三次：用315除以285，商1余30；
第四次：用285除以30，商9余15；
第五次：用30除以15，商2余0。故1515和600的最大公約數是15.
迭代思想是如何體現的？
自然語言 流程圖 程序設計語言
輸入兩個正整數m和n 以m除以n，相除得到余數為r 若r=0，則輸出n，算法結束；否則執行步驟 令m=n，n=r，返回步驟繼續執行 m=int(input(“請輸入正整數m：”))
n=int(input(“請輸入正整數n：”))
____________
while ____________:
r=m%n
____________
print(“最大公約數為，”,n)
活動二
r!=0
m,n=n,r
思考：試分析上述程序的迭代變量？迭代關系式？如何控制迭代過程？
r=m%n
遷移運用
任務三：校運動會求各班總分
每年的校運動會每個班級都會參加一些項目，最后會統計每個班級的總分進行排名，現假定每個班級都參加10個項目，每個項目的得分在0-7之間，我們如何來編程實現統計每個班級的總分？
每個班級都參加10個項目，每個項目的得分在0-7之間，并且每個項目分數之前添加班級序號，最后將各個班級的總分最后放在數組的最后。如3個班級的數據結構如下所示：
[[1, 3], [1, 4], ……, [2, 3], [2, 5], ……, [3, 0], [3, 7], ……, [1, 32], [2, 28], [3, 41]]
上述數據中1班總分為32,2班總分為28,3班總分為41。
第一步：獲得班級各項目的分數。
第二步：對它們累加求和。
利用隨機數函數獲得
利用循環實現求和
遷移運用
from random import randint
a=[]
n=int(input('請輸入班級數：'))
for i in range(1,n+1):
for j in range(1,11):
a.append( )
print('各班各項分數為：\n',a)
請編程實現：
第一步：利用隨機數函數產生各個班級各個項目的分數。
[i,randint(0,7)]
遷移運用
for i in range(1,n+1):
s=0
j=(i-1)*10
while __________:
#迭代求和，用變量的原值推算出變量的新值
s+=a[j][1]
j+=1
print(_________+"班同學的總分為"+str(s))
請編程實現：
第二步：利用循環編寫程序實現求各個班級各個分數的和。
jstr(i)
成果集成
迭代算法的概念
迭代算法的三要素
迭代算法的實現
迭代算法的數學原理與注意事項
當堂檢測
更相減損術
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續這個操作，直到所得的減數和差相等為止。則第一步中約掉的若干個2的積與第二步中等數的乘積就是所求的最大公約數。以18和8為例：18//2=9，8//2=4，9-4=5，5-4=1，5-1=4，4-1=3，3-1=2，2-1=1.減數和差相等。最大公約數為：1*2=2。
def gys(m, n): ys=1 while ____________________: ys=ys*2;m=m//2;n=n//2 while m!=n: if m>n: __________________ else: n=n-m ys=_________________ return ysa=[[12,4],[20,25],[32,48],[48,60]]b=[]for i in range(4): b.append(gys(a[i][0], a[i][1]))print("各組數為：",a) print("它們的最大公約數為：",b)
m%2==0 and n%2==0
m=m-n
ys*m
當堂檢測
1.Python從最初發布到現在的版本不斷更新的過程可以看出，一款
軟件從上市到最終框架的成型，是不斷試錯、不斷根據用戶體驗反饋
快速調整和完善得到的結果。這個例子體現的算法思想是（ ）
A.枚舉 B.解析 C.迭代 D.遞歸
C
當堂檢測
2.下列Python程序的功能是使用迭代算法求c的值（ ）
list1=[1,3,2,4,5,8,7,6,9,4,2,3]
c=0
n=int(input(‘請輸入n的值：’))
for i in range(2,n):
a=list1[i]-list1[i-1]
b=list1[i-1]-list1[i-2]
c=c+a+b
print(c)
D
THANK YOU
Speaker :wps powerpoint

展開更多......

收起↑