1、求兩個(gè)正整數(shù)最大條約數(shù)（1）求25和35最大條約數(shù)（2）求49和63最大條約數(shù)2、求8251和6105最大條約數(shù)25（1）5535749（2）77639所以，25和35最大條約數(shù)為5所以，49和63最大條約數(shù)為7

輾轉(zhuǎn)相除法與更相減損術(shù)講義第1頁(yè)輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和6105最大條約數(shù)過(guò)程第一步用兩數(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ù)。為什么呢？思考：從上述的過(guò)程你體會(huì)到了什么？第2頁(yè)完整過(guò)程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：從上面兩個(gè)例子能夠看出計(jì)算規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0第3頁(yè)利用輾轉(zhuǎn)相除法求最大條約數(shù)步驟以下：第一步：用較大數(shù)m除以較小數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；(m=n×q0+r0)第二步：若r0＝0，則n為m，n最大條約數(shù)；若r0≠0，則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1；(n=r0×q1+r1)第三步：若r1＝0，則r0為m，n最大條約數(shù)；若r1≠0，則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；(r0=r1×q2+r2)……依次計(jì)算直至rn＝0，此時(shí)所得到rn-1即為所求最大條約數(shù)。第4頁(yè)

輾轉(zhuǎn)相除法是一個(gè)重復(fù)執(zhí)行直到余數(shù)等于0停頓步驟，這實(shí)際上是一個(gè)循環(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用程序框圖表示出右邊過(guò)程r=mMODnm=nn=rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？第5頁(yè)輾轉(zhuǎn)相除除法程序框圖與程序

否是第6頁(yè)《九章算術(shù)》——更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。第二步：以較大數(shù)減較小數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求最大條約數(shù)。第7頁(yè)例3用更相減損術(shù)求98與63最大條約數(shù)解：因?yàn)?3不是偶數(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ù)等于7練習(xí)2：用更相減損術(shù)求兩個(gè)正數(shù)84與72最大條約數(shù)。(12)第8頁(yè)第一步,給定兩個(gè)正整數(shù),不妨設(shè)m>n,第二步,若m,n都是偶數(shù),則不停用2約簡(jiǎn),使他們不一樣時(shí)是偶數(shù),約簡(jiǎn)后兩個(gè)數(shù)仍記為m,n第三步,d=m-n第四步,判斷”d<>0”是否成立,若是,則將n,d中較大者記為m,較小記為n,返回第三步;不然,2^k*d(k是約簡(jiǎn)整數(shù)2個(gè)數(shù))為所求最大條約數(shù).更相減損術(shù)算法第9頁(yè)開(kāi)始輸m,n(m>n)K=0m,n為偶數(shù)?K=k+1m=m/2n=n/2d=m-nd<>n?d>n?是否m=nn=dd=m-nm=d是輸出2^kd結(jié)束是否否第10頁(yè)INPUT“m,n=“;m,nIFm<nTHENa=mm=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+1WENDd=m-nWhiled<>nIFd>nthenm=dELSEm=nn=dEndifd=m-nWendd=2^k＊dPRINTdEnd

第11頁(yè)輾轉(zhuǎn)相除法與更相減損術(shù)比較: （1）都是求最大條約數(shù)方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更