(必修三)131算法案例(第一課時)(人教B版)

算法案例(第一課時)案例1輾轉(zhuǎn)相除法與更相減損術(shù)2.思考：

小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.1、求兩個正整數(shù)的最大公約數(shù)〔1〕求25和35的最大公約數(shù)〔2〕求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為72、除了用這種方法外還有沒有其它方法？算出8256和6105的最大公約數(shù).輾轉(zhuǎn)相除法〔歐幾里得算法〕觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。第二步對6105和2146重復(fù)第一步的做法

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。為什么呢？思考：從上述的過程你體會到了什么？完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)思考1：從上面的兩個例子可以看出計算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0

輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？1、輾轉(zhuǎn)相除法〔歐幾里得算法〕〔1〕算理：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。假設(shè)余數(shù)不為零，那么將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，那么這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)?！?〕算法步驟第一步：輸入兩個正整數(shù)m,n(m>n).第二步：計算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：假設(shè)r＝0,那么m,n的最大公約數(shù)等于m；否那么轉(zhuǎn)到第二步.第五步：輸出最大公約數(shù)m.〔3〕程序框圖〔4〕程序INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND開始輸入m,nr=mMODnm=nr=0?是否n=r輸出m結(jié)束算理：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。假設(shè)是，那么用2約簡；假設(shè)不是那么執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，那么這個等數(shù)就是所求的最大公約數(shù)。解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝2114－7＝7所以，98和63的最大公約數(shù)等于7用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù)．練習(xí)：先約簡，再求21與18的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)4〔2〕算法步驟第一步：輸入兩個正整數(shù)a,b(a>b);第二步：假設(shè)a不等于b,那么執(zhí)行第三步；否那么轉(zhuǎn)到第五步；第三步：把a-b的差賦予r;第四步：如果b>r,那么把b賦給a,把r賦給b;否那么把r賦給a，執(zhí)行第二步；第五步：輸出最大公約數(shù)b.〔3〕程序框圖〔4〕程序INPUT“a,b=“;a,bWHILEa<>br=a-bIFb>rTHENa=bb=rELSEa=rENDIFWENDPRINTbEND開始輸入a,ba≠b?是否輸出b結(jié)束b=ra=