高中數(shù)學高中數(shù)學：14算法案例-2ppt課件

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

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

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

4、除法求a=204和和b=85的最大公約數(shù)。的最大公約數(shù)。;3428520434,852041，所以為余數(shù)r 分析：分析：;172348517,34852，所以為余數(shù)r. 217340,17341，所以為余數(shù)r因此，因此，204與與85的最大公約數(shù)是的最大公約數(shù)是r2=17. 歐幾里得輾轉相除法找出歐幾里得輾轉相除法找出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ù)

5、為直到余數(shù)為0,此時的除數(shù)即為此時的除數(shù)即為a,b的最大的最大公約數(shù)公約數(shù).l求求a,b(ab)的最大公約數(shù)的算法為：的最大公約數(shù)的算法為：S1 輸入兩個正整數(shù)輸入兩個正整數(shù)a,b;S2 如果如果Mod(a,b) 0,那么轉那么轉S3,否則轉否則轉S6;S3 r Mod(a,b) ;S4 ab;S5 br,轉轉S2;S6 輸出輸出b.rMOD(a , b)abbrr=0是否Read a,bWhile Mod(a,b) 0 rMod(a,b) ab brEnd WhilePrint bEndn流程圖與偽代碼流程圖與偽代碼回顧反思回顧反思 l輾轉相除法是當大數(shù)被小數(shù)除盡時，輾轉相除法是當大數(shù)被小數(shù)除盡時，結束除法運算，較小的數(shù)就是最大公結束除法運算，較小的數(shù)就是最大公約數(shù)約數(shù)l求三個以上求三個以上(含三個數(shù)含三個數(shù))的數(shù)的最大公的數(shù)的最大公約數(shù)時，