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

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

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

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

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. 歐幾里得輾轉(zhuǎn)相除法找出歐幾里得輾轉(zhuǎn)相除法找出a,b的最大公約的最大公約數(shù)的步驟是數(shù)的步驟是: （1計(jì)算計(jì)算ab的余數(shù)的余數(shù)r,若若r=0,則則b為為a,b的最大公約數(shù)；的最大公約數(shù)； （2若若r0,則把前面的除數(shù)則把前面的除數(shù)b作為新的作為新的被除數(shù)被除數(shù),把余數(shù)把余數(shù)r作為新的除數(shù)作為新的除數(shù),繼續(xù)運(yùn)算繼續(xù)運(yùn)算,直到余數(shù)

5、為直到余數(shù)為0,此時(shí)的除數(shù)即為此時(shí)的除數(shù)即為a,b的最大的最大公約數(shù)公約數(shù).l求求a,b(ab)的最大公約數(shù)的算法為：的最大公約數(shù)的算法為：S1 輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(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.rMOD(a , b)abbrr=0是否Read a,bWhile Mod(a,b) 0 rMod(a,b) ab brEnd WhilePrint bEndn流程圖與偽代碼流程圖與偽代碼回顧反思回顧反思 l輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時(shí)，輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時(shí)，結(jié)束除法運(yùn)算，較小的數(shù)就是最大公結(jié)束除法運(yùn)算，較小的數(shù)就是最大公約數(shù)約數(shù)l求三個(gè)以上求三個(gè)以上(含三個(gè)數(shù)含三個(gè)數(shù))的數(shù)的最大公的數(shù)的最大公約數(shù)時(shí)，