《高二數(shù)學必修3 算法案例2 ppt》由會員分享,可在線閱讀,更多相關(guān)《高二數(shù)學必修3 算法案例2 ppt(9頁珍藏版)》請在裝配圖網(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)相除法: 我們可以證明,對于任意兩個正整數(shù),上述步驟總可以在有限步之后完成,從而總可以用輾轉(zhuǎn)相除的方法求出最大公約數(shù) 算法設(shè)計算法設(shè)計 : 如何用輾轉(zhuǎn)相除法找出兩個正整數(shù)如何用輾轉(zhuǎn)相除法找出兩個正整數(shù)a,b的最大公約數(shù)?的最大公約數(shù)? (1)結(jié)合問題結(jié)合問題1和問題和問題2,應(yīng)該利用什么結(jié)構(gòu)實現(xiàn)該算法
2、,應(yīng)該利用什么結(jié)構(gòu)實現(xiàn)該算法? (循環(huán)結(jié)構(gòu))(循環(huán)結(jié)構(gòu)) (2)每一次循環(huán)中所進行的是什么樣的運算?每一次循環(huán)中所進行的是什么樣的運算? (求(求ab的余數(shù))的余數(shù)) (3)下一次循環(huán)的輸入整數(shù)應(yīng)該是什么?循環(huán)何時結(jié)束?下一次循環(huán)的輸入整數(shù)應(yīng)該是什么?循環(huán)何時結(jié)束? 設(shè)設(shè)ab,a除以除以b的余數(shù)為的余數(shù)為r(br),則下一次循環(huán)的兩則下一次循環(huán)的兩個數(shù)為個數(shù)為b,r. 直到直到r=0為止為止.算法算法 S1 輸入兩個正整數(shù)輸入兩個正整數(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如何實現(xiàn)當型循環(huán)。