高中數(shù)學(xué)高中數(shù)學(xué)：14算法案例-2必修三ppt課件

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

2、碼格式： For I From “ For I From “初值初值” To “” To “終值終值” ” step “step “步長步長” End For End For3 59 15 在小學(xué)，我們學(xué)過求兩個正整數(shù)的最大公約在小學(xué)，我們學(xué)過求兩個正整數(shù)的最大公約數(shù)的方法，先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，數(shù)的方法，先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除一直到所得的商是互質(zhì)數(shù)為止，然后把所以的除數(shù)乘起來，例如，求數(shù)乘起來，例如，求18與與30的最大共約數(shù)：的最大共約數(shù)：18 3023 所以，所以，18與與30的最大共約數(shù)是：的最大共約數(shù)是：23=6.引入引入

3、 寫出求兩個正整數(shù)寫出求兩個正整數(shù)a,b(ab)的最大公約數(shù)的一個算法的最大公約數(shù)的一個算法案例案例2 2公元前公元前3世紀(jì)，歐幾里得在世紀(jì)，歐幾里得在第七篇中第七篇中介紹了求兩個正整數(shù)介紹了求兩個正整數(shù)a,b(ab)的最大公約數(shù)的最大公約數(shù)的方法，即求出一列數(shù)：的方法，即求出一列數(shù)：. 0 ,121nnrrrrba這列數(shù)從第三項開始，每一項都是前兩項相這列數(shù)從第三項開始，每一項都是前兩項相除所得的余數(shù)，余數(shù)為除所得的余數(shù)，余數(shù)為0的前一項的前一項rn,即是即是a和和b的最大公約數(shù)。這種方法稱為的最大公約數(shù)。這種方法稱為“歐幾里得輾歐幾里得輾轉(zhuǎn)相除法轉(zhuǎn)相除法”輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 例例1 用輾

4、轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求a=204和和b=85的最大公約數(shù)的最大公約數(shù)。;3428520434,852041，所以為余數(shù)r 分析：分析：;172348517,34852，所以為余數(shù)r. 217340,17341，所以為余數(shù)r因此，因此，204與與85的最大公約數(shù)是的最大公約數(shù)是r2=17. 歐幾里得輾轉(zhuǎn)相除法找出歐幾里得輾轉(zhuǎn)相除法找出a,b的最大公約的最大公約數(shù)的步驟是數(shù)的步驟是: （1計算計算ab的余數(shù)的余數(shù)r,若若r=0,則則b為為a,b的最大公約數(shù)；的最大公約數(shù)； （2若若r0,則把前面的除數(shù)則把前面的除數(shù)b作為新的作為新的被除數(shù)被除數(shù),把余數(shù)把余數(shù)r作為新的除數(shù)作為新的除數(shù),繼續(xù)運算繼續(xù)運算,直到余數(shù)為直到余數(shù)為0,此時的除數(shù)即為此時的除數(shù)即為a,b的最大的最大公約數(shù)公約數(shù).l求求a,b(ab)的最大公約數(shù)的算法為：的最大公約數(shù)的算法為：S1 輸入兩個正整數(shù)輸入兩個正整數(shù)a,b;S2 如果如果Mod(a,b) 0,那么轉(zhuǎn)那么轉(zhuǎn)S3,否則轉(zhuǎn)否則轉(zhuǎn)S6;S3 r Mod(a,b) ;S4 ab;S5 br,轉(zhuǎn)轉(zhuǎn)S2;S6 輸出輸出b.回顧反思回顧反思 l輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時，輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時，結(jié)束除法運算，較小的數(shù)就是最大公結(jié)束除法運算，較小的數(shù)就是最大公約數(shù)約數(shù)l求三個以上求三個以上(含三個數(shù)含三個數(shù))的數(shù)的最大公的數(shù)的最大公約數(shù)時，可依次通