算法案例算法案例2 2廣義地說：廣義地說：為了解決某一問題而為了解決某一問題而采取的方法和步驟，就稱之為算法。采取的方法和步驟，就稱之為算法。算法的概念算法的概念: 一般而言，一般而言，對(duì)一類問題的機(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è)處理的結(jié)構(gòu)進(jìn)行多個(gè)處理的結(jié)構(gòu)稱為稱為順序結(jié)構(gòu)順序結(jié)構(gòu).語句語句A語句語句B2.順序結(jié)構(gòu)的流程圖順序結(jié)構(gòu)的流程圖 順序結(jié)構(gòu)是最簡(jiǎn)單順序結(jié)構(gòu)是最簡(jiǎn)單、最基本最基本的算法結(jié)構(gòu)的算法結(jié)構(gòu), ,語句與語句與語句之間語句之間, ,框與框之間是按框與框之間是按從上到下的順序進(jìn)行的從上到下的順序進(jìn)行的. .它它是由若干個(gè)處理步驟組成是由若干個(gè)處理步驟組成的的, ,這這是任何一個(gè)算法都離是任何一個(gè)算法都離不開的基本結(jié)構(gòu)不開的基本結(jié)構(gòu). .選擇結(jié)構(gòu)選擇結(jié)構(gòu)也叫條件結(jié)構(gòu)，是指在算法中通過對(duì)條件的也叫條件結(jié)構(gòu)，是指在算法中通過對(duì)條件的判斷，根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)判斷，根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)右圖此結(jié)構(gòu)中包含一個(gè)判斷框，右圖此結(jié)構(gòu)中包含一個(gè)判斷框，根據(jù)給定的條件根據(jù)給定的條件P是否成立而選擇是否成立而選擇執(zhí)行執(zhí)行A框或框或B框無論框無論P(yáng)條件是否條件是否成立，只能執(zhí)行成立，只能執(zhí)行A框或框或B框之一，框之一，不可能同時(shí)執(zhí)行不可能同時(shí)執(zhí)行A框和框和B框，也不框，也不可能可能A框、框、B框都不執(zhí)行框都不執(zhí)行開始開始S 1結(jié)束結(jié)束輸出輸出Si1SSii1i100NYi1直到型循環(huán)直到型循環(huán)pAYN當(dāng)型循環(huán)當(dāng)型循環(huán)pAYN結(jié)束結(jié)束輸出輸出SS 0開始開始i i + 1S S + ii10YNi 0先執(zhí)行，后判斷：先執(zhí)行，后判斷：先判斷，后執(zhí)行：先判斷，后執(zhí)行：“N”進(jìn)入循進(jìn)入循環(huán)環(huán)“Y”進(jìn)入循進(jìn)入循環(huán)環(huán)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)已學(xué)過的偽代碼中的幾種基本算法語句已學(xué)過的偽代碼中的幾種基本算法語句:(1)賦值語句賦值語句:變量變量表達(dá)式或變量或常數(shù)表達(dá)式或變量或常數(shù)(2)輸入語句輸入語句: Read a,b(3)輸出語句輸出語句:(4)條件語句條件語句:Print a,bIf A Then B Else CEnd If 當(dāng)型語句當(dāng)型語句:While p循環(huán)體循環(huán)體End while直到型語句直到型語句:Do循環(huán)體循環(huán)體Until pEnd Do(5)循環(huán)語句循環(huán)語句偽代碼中的偽代碼中的:pAYNpAYN當(dāng)循環(huán)的次數(shù)已經(jīng)確定，可用當(dāng)循環(huán)的次數(shù)已經(jīng)確定，可用“For”語句表語句表示示“For”For”語句偽代碼格式：語句偽代碼格式： For I From “初值初值” To “終值終值” step “步步長(zhǎng)長(zhǎng)” End For(6)For語句語句:3 59 15 在小學(xué)，我們學(xué)過求兩個(gè)正整數(shù)的最大公約在小學(xué)，我們學(xué)過求兩個(gè)正整數(shù)的最大公約數(shù)的方法，先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，數(shù)的方法，先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除數(shù)乘起來，例如，求數(shù)乘起來，例如，求18與與30的最大共約數(shù)：的最大共約數(shù)：18 3023 所以，所以，18與與30的最大共約數(shù)是：的最大共約數(shù)是：23=6.引入課題引入課題 利用找公約數(shù)的方法來求最大公約數(shù)，利用找公約數(shù)的方法來求最大公約數(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ù)”的的問題有什么幫助？問題有什么幫助？8251610512146;求求8251與與6105最大共約數(shù)最大共約數(shù) 求求6105與與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ù)的過程，寫成算法嗎？你能把輾轉(zhuǎn)相除法求最大共約數(shù)的過程，寫成算法嗎？ 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í)過嗎？這樣交換數(shù)據(jù)的方式，前面我們學(xué)習(xí)過嗎？ 在求斐波拉契數(shù)列中的數(shù)在求斐波拉契數(shù)列中的數(shù)請(qǐng)用自然語言描述該算法請(qǐng)用自然語言描述該算法! S1 輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(shù)a,b（ab）；）；S2 若若Mod（a,b）0，則輸出最大公約數(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開始開始Mod(a,b)0rMod(a，b)輸出輸出b結(jié)束結(jié)束Nabbr輸入輸入a,bN開始開始r0rMod(a，b)輸出輸出a結(jié)束結(jié)束Yabbr輸入輸入a,b將自然語言描述的算法改寫為偽代碼將自然語言描述的算法改寫為偽代碼! 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