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

1、輾轉(zhuǎn)相除法 與最大公約數(shù),最小公倍數(shù)問題情境 求18和30的最大公約數(shù) 結(jié)論18和30的最大公約數(shù)為618和30的最小公倍數(shù)為90 (牢記方法!)問題1 求204與85的最大公約數(shù) 問題2 求8251與6105的最大公約數(shù) 204與85的最大公約數(shù)是17 8251與6105的最大公約數(shù)是34 輾轉(zhuǎn)相除法: 我們可以證明，對(duì)于任意兩個(gè)正整數(shù)，上述步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除的方法求出最大公約數(shù) 算法設(shè)計(jì)算法設(shè)計(jì) : 如何用輾轉(zhuǎn)相除法找出兩個(gè)正整數(shù)如何用輾轉(zhuǎn)相除法找出兩個(gè)正整數(shù)a,b的最大公約數(shù)？的最大公約數(shù)？ (1)結(jié)合問題結(jié)合問題1和問題和問題2，應(yīng)該利用什么結(jié)構(gòu)實(shí)現(xiàn)該算法

2、，應(yīng)該利用什么結(jié)構(gòu)實(shí)現(xiàn)該算法? （循環(huán)結(jié)構(gòu)）（循環(huán)結(jié)構(gòu)） (2)每一次循環(huán)中所進(jìn)行的是什么樣的運(yùn)算？每一次循環(huán)中所進(jìn)行的是什么樣的運(yùn)算？ （求（求ab的余數(shù)）的余數(shù)） (3)下一次循環(huán)的輸入整數(shù)應(yīng)該是什么？循環(huán)何時(shí)結(jié)束？下一次循環(huán)的輸入整數(shù)應(yīng)該是什么？循環(huán)何時(shí)結(jié)束？ 設(shè)設(shè)ab,a除以除以b的余數(shù)為的余數(shù)為r(br),則下一次循環(huán)的兩則下一次循環(huán)的兩個(gè)數(shù)為個(gè)數(shù)為b,r. 直到直到r=0為止為止.算法算法 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

3、，轉(zhuǎn)，轉(zhuǎn)S2 流程圖流程圖 偽代碼偽代碼 Read a,b While Mod(a,b)0 0 rmod(a,b) ab brEnd WhilePrint b例例1 試畫出求正整數(shù)試畫出求正整數(shù)a,b最小公倍數(shù)的流程圖，并寫出最小公倍數(shù)的流程圖，并寫出其偽代碼。其偽代碼。 Read a,bcabWhile Mod(a,b)00 r Mod(a,b) ab br End While End While Print c/b例例2下面一段偽代碼的目的是求下面一段偽代碼的目的是求 10 Read a,b20 If a/bInt (a/b) Then Goto 70 30 30 caInt( (a/ /b) )b 40 40 ab50 bc60 Goto 2070 Print bA.求求a,b的最小公倍數(shù)的最小公倍數(shù) B.求求a,b的最大公約數(shù)的最大公約數(shù)C.求求a被被b整除的商整除的商 D.求求b除以除以a的余數(shù)的余數(shù) 分析：解題關(guān)鍵就是：分析：解題關(guān)鍵就是：aint(a/b)bmod(a,b) 回顧反思 1輾轉(zhuǎn)相除法的算法； 2如何實(shí)現(xiàn)當(dāng)型循環(huán)。