《高二數(shù)學(xué)《算法案例》 課件必修3》由會(huì)員分享，可在線閱讀，更多相關(guān)《高二數(shù)學(xué)《算法案例》 課件必修3（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算法案例算法案例2 2廣義地說(shuō)：廣義地說(shuō)：為了解決某一問(wèn)題而為了解決某一問(wèn)題而采取的方法和步驟，就稱之為算法。采取的方法和步驟，就稱之為算法。算法的概念算法的概念: 一般而言，一般而言，對(duì)一類問(wèn)題的機(jī)械的、統(tǒng)一的求解方法稱為算法。知識(shí)回顧知識(shí)回顧 流程圖：是由一些圖框和流程線組成的，其中流程圖：是由一些圖框和流程線組成的，其中圖框表示各種操作的類型，圖框中的文字和符圖框表示各種操作的類型，圖框中的文字和符號(hào)表示操作的內(nèi)容，流程線表示操作的先后次號(hào)表示操作的內(nèi)容，流程線表示操作的先后次序。序。流程圖的概念流程圖的概念順序結(jié)構(gòu)及框圖表示順序結(jié)構(gòu)及框圖表示1.順序結(jié)構(gòu)順序結(jié)構(gòu): 依次依次進(jìn)行多個(gè)處理

2、的結(jié)構(gòu)進(jìn)行多個(gè)處理的結(jié)構(gòu)稱為稱為順序結(jié)構(gòu)順序結(jié)構(gòu).語(yǔ)句語(yǔ)句A語(yǔ)句語(yǔ)句B2.順序結(jié)構(gòu)的流程圖順序結(jié)構(gòu)的流程圖 順序結(jié)構(gòu)是最簡(jiǎn)單順序結(jié)構(gòu)是最簡(jiǎn)單、最基本最基本的算法結(jié)構(gòu)的算法結(jié)構(gòu), ,語(yǔ)句與語(yǔ)句與語(yǔ)句之間語(yǔ)句之間, ,框與框之間是按框與框之間是按從上到下的順序進(jìn)行的從上到下的順序進(jìn)行的. .它它是由若干個(gè)處理步驟組成是由若干個(gè)處理步驟組成的的, ,這這是任何一個(gè)算法都離是任何一個(gè)算法都離不開(kāi)的基本結(jié)構(gòu)不開(kāi)的基本結(jié)構(gòu). .選擇結(jié)構(gòu)選擇結(jié)構(gòu)也叫條件結(jié)構(gòu)，是指在算法中通過(guò)對(duì)條件的也叫條件結(jié)構(gòu)，是指在算法中通過(guò)對(duì)條件的判斷，根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)判斷，根據(jù)條件是否成立而選擇不同流向的算法

3、結(jié)構(gòu)右圖此結(jié)構(gòu)中包含一個(gè)判斷框，右圖此結(jié)構(gòu)中包含一個(gè)判斷框，根據(jù)給定的條件根據(jù)給定的條件P是否成立而選擇是否成立而選擇執(zhí)行執(zhí)行A框或框或B框無(wú)論框無(wú)論P(yáng)條件是否條件是否成立，只能執(zhí)行成立，只能執(zhí)行A框或框或B框之一，框之一，不可能同時(shí)執(zhí)行不可能同時(shí)執(zhí)行A框和框和B框，也不框，也不可能可能A框、框、B框都不執(zhí)行框都不執(zhí)行開(kāi)始開(kāi)始S 1結(jié)束結(jié)束輸出輸出Si1SSii1i100NYi1直到型循環(huán)直到型循環(huán)pAYN當(dāng)型循環(huán)當(dāng)型循環(huán)pAYN結(jié)束結(jié)束輸出輸出SS 0開(kāi)始開(kāi)始i i + 1S S + ii10YNi 0先執(zhí)行，后判斷：先執(zhí)行，后判斷：先判斷，后執(zhí)行：先判斷，后執(zhí)行：“N”進(jìn)入循進(jìn)入循環(huán)環(huán)“Y

4、”進(jìn)入循進(jìn)入循環(huán)環(huán)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)已學(xué)過(guò)的偽代碼中的幾種基本算法語(yǔ)句已學(xué)過(guò)的偽代碼中的幾種基本算法語(yǔ)句:(1)賦值語(yǔ)句賦值語(yǔ)句:變量變量表達(dá)式或變量或常數(shù)表達(dá)式或變量或常數(shù)(2)輸入語(yǔ)句輸入語(yǔ)句: Read a,b(3)輸出語(yǔ)句輸出語(yǔ)句:(4)條件語(yǔ)句條件語(yǔ)句:Print a,bIf A Then B Else CEnd If 當(dāng)型語(yǔ)句當(dāng)型語(yǔ)句:While p循環(huán)體循環(huán)體End while直到型語(yǔ)句直到型語(yǔ)句:Do循環(huán)體循環(huán)體Until pEnd Do(5)循環(huán)語(yǔ)句循環(huán)語(yǔ)句偽代碼中的偽代碼中的:pAYNpAYN當(dāng)循環(huán)的次數(shù)已經(jīng)確定，可用當(dāng)循環(huán)的次數(shù)已經(jīng)確定，可用“For”語(yǔ)句表語(yǔ)句表示示“Fo

5、r”For”語(yǔ)句偽代碼格式：語(yǔ)句偽代碼格式： For I From “初值初值” To “終值終值” step “步步長(zhǎng)長(zhǎng)” End For(6)For語(yǔ)句語(yǔ)句:3 59 15 在小學(xué)，我們學(xué)過(guò)求兩個(gè)正整數(shù)的最大公約在小學(xué)，我們學(xué)過(guò)求兩個(gè)正整數(shù)的最大公約數(shù)的方法，先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，數(shù)的方法，先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除數(shù)乘起來(lái)，例如，求數(shù)乘起來(lái)，例如，求18與與30的最大共約數(shù)：的最大共約數(shù)：18 3023 所以，所以，18與與30的最大共約數(shù)是：的最大共約數(shù)是：23=6.引入課題引入課題 利

6、用找公約數(shù)的方法來(lái)求最大公約數(shù)，利用找公約數(shù)的方法來(lái)求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如的最大公約數(shù)？比如求求82518251與與61056105的最大公的最大公約數(shù)約數(shù)？ 觀察上面的式子，你有什么發(fā)現(xiàn)？你的發(fā)現(xiàn)，觀察上面的式子，你有什么發(fā)現(xiàn)？你的發(fā)現(xiàn)，對(duì)我們解決對(duì)我們解決“求求8251與與6105的最大公約數(shù)的最大公約數(shù)”的的問(wèn)題有什么幫助？問(wèn)題有什么幫助？8251610512146;求求8251與與6105最大共約數(shù)最大共約數(shù) 求求6105與與

7、2146最大共約數(shù)最大共約數(shù)化歸化歸6105214621813;214618131333;18133335148;333148237;1483740. 148與與37的最大共約數(shù)是的最大共約數(shù)是37 8251與與6105的最大共約數(shù)是的最大共約數(shù)是37 以上我們求最大公約數(shù)以上我們求最大公約數(shù)的方法就是的方法就是輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法，也，也叫歐幾里德算法，它是由歐叫歐幾里德算法，它是由歐幾里德在公元前幾里德在公元前300年左右年左右首先提出的首先提出的.練習(xí)練習(xí): :用用輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法求求204與與85的最大公約數(shù)的最大公約數(shù) 你能把輾轉(zhuǎn)相除法求最大共約數(shù)的過(guò)程，寫成算法嗎？你能把輾轉(zhuǎn)相

8、除法求最大共約數(shù)的過(guò)程，寫成算法嗎？ l該算法中，要用到什么主要的算法結(jié)構(gòu)？該算法中，要用到什么主要的算法結(jié)構(gòu)？ l每一次循環(huán)中所進(jìn)行的是什么樣的運(yùn)算每一次循環(huán)中所進(jìn)行的是什么樣的運(yùn)算 ？ l循環(huán)何時(shí)結(jié)束？下一次循環(huán)的輸入整數(shù)應(yīng)該是什么？循環(huán)何時(shí)結(jié)束？下一次循環(huán)的輸入整數(shù)應(yīng)該是什么？ 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) rmod(a，b) r =0abbrl這樣交換數(shù)據(jù)的方式，前面我們學(xué)習(xí)過(guò)嗎？這樣交換數(shù)據(jù)的方式，前面我們學(xué)習(xí)過(guò)嗎？ 在求斐波拉契數(shù)列中的數(shù)在求斐波拉契數(shù)列中的數(shù)請(qǐng)用自然語(yǔ)言描述該算法請(qǐng)用自然語(yǔ)言描述該算法! S1 輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(shù)a,b（ab）；）；S2 若若Mod（a,b）0，則輸

9、出最大公約數(shù)，則輸出最大公約數(shù)b，算法結(jié)束；，算法結(jié)束； 否則否則r Mod（a,b），），a b，br，轉(zhuǎn)，轉(zhuǎn)S2S1 輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(shù)a，b（ab）；）；S2 r Mod（a,b）S3 a bS4 br，S5 若若r不等于不等于0，轉(zhuǎn)，轉(zhuǎn)S2S6 輸出最大公約數(shù)輸出最大公約數(shù)a.Y開(kāi)始開(kāi)始Mod(a,b)0rMod(a，b)輸出輸出b結(jié)束結(jié)束Nabbr輸入輸入a,bN開(kāi)始開(kāi)始r0rMod(a，b)輸出輸出a結(jié)束結(jié)束Yabbr輸入輸入a,b將自然語(yǔ)言描述的算法改寫為偽代碼將自然語(yǔ)言描述的算法改寫為偽代碼! Read a,b While Mod(a,b)0 0 rmod(a,b) ab brEnd WhilePrint bRead a,b Do rmod(a,b) ab brUntil r=0Print a