《算法案例-輾轉(zhuǎn)相除法與更相減損術(shù)》課件（1）（新人教A版必修3）

算法案例第一課時(shí)輾轉(zhuǎn)相除法與11.回顧算法的三種表示方法：（1）、自然語(yǔ)言（2）、程序框圖（3）、程序語(yǔ)言（三種邏輯結(jié)構(gòu)）（五種基本語(yǔ)句）復(fù)習(xí)引入22.思考：

小學(xué)學(xué)過的求兩個(gè)數(shù)的最大公約數(shù)的方法？先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái).3例：求下面兩個(gè)正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7思考：除了用這種方法外還有沒有其它方法？例：如何算出8251和6105的最大公約數(shù)？4新課講解：一、輾轉(zhuǎn)相除法（歐幾里得算法）1、定義：所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)。5

2、步驟（以求8251和6105的最大公約數(shù)的過程為例）第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

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

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。

為什么呢？6完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例：用輾轉(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：從上面的兩個(gè)例子中可以看出計(jì)算的規(guī)律是什么？

S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為07

輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。m=n×q＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+08(1)、算法步驟：第一步：輸入兩個(gè)正整數(shù)m,n(m>n).第二步：計(jì)算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：若r＝0,則m,n的最大公約數(shù)等于m；否則轉(zhuǎn)到第二步.第五步：輸出最大公約數(shù)m.思考：你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？9(2)、程序框圖：開始輸入m,n

r=mMODn

m=nr=0?是否

n=r輸出m結(jié)束10(3)、程序：INPUT“m,n=”;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND11二、更相減損術(shù)

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。（1）、《九章算術(shù)》中的更相減損術(shù)：1、背景介紹：（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：122、定義：

所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)。13例:用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝1414－7＝7所以，98和63的最大公約數(shù)等于73、方法：141、用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)．

練習(xí)：思路分析：先約簡(jiǎn)，再求21與18的最大公約數(shù),然后乘以兩次約簡(jiǎn)的質(zhì)因數(shù)4。2、求324、243、135這三個(gè)數(shù)的最大公約數(shù)。思路分析：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。15(1)、算法步驟第一步：輸入兩個(gè)正整數(shù)m,n(m>n);第二步：若m,n都是偶數(shù),則不斷用2約簡(jiǎn),使它們不同時(shí)是偶數(shù),約簡(jiǎn)后的了兩個(gè)數(shù)仍記為m,n.第三步：d=m-n.第四步：判斷d≠n是否成立.若是,則將n,d中較大者記為m,較小者記為n,返回第三步;否則,2＾k*d為所求的最大公約數(shù).思考：你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，16INPUTm,nIFm<nTHENa=mm=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+1WENDd=m-nWHILEd<>n

IFd>nTHENm=d

ELSEm=nn=d

ENDIFd=m-nWENDd=2k*dPRINTdEND17比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求