【高中數(shù)學(xué)必修一】1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)

人教版《普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書·數(shù)學(xué)》必修31.3.1輾轉(zhuǎn)相除法與更相減損術(shù).“求兩個(gè)正整數(shù)的最大公約數(shù)”是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問題，它有各種解決辦法，我們以此為案例，對(duì)該問題的算法作一些探究..解：2

1824

用公有質(zhì)因數(shù)2除，3

912

用公有質(zhì)因數(shù)3除，

343和4互質(zhì)不除了。

得：18和24最大公約數(shù)是：2×3＝6

例1.求18與24的最大公約數(shù)：短除法想一想，如何求8251與6105的最大公約數(shù)？.解：因?yàn)?251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0所以37是8251和6105的最大公約數(shù)例1.求8251與6105的最大公約數(shù)：為什么？輾轉(zhuǎn)相除法（歐幾里得算法）試試看：用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)思考：上面兩個(gè)例子中的算理是什么？.1：用大數(shù)除以小數(shù)2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)3：重復(fù)1、2，直到余數(shù)為0輾轉(zhuǎn)相除法（歐幾里得算法）定義：所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)。主要運(yùn)用的是哪種算法結(jié)構(gòu)？.m=n×q＋r8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0輾轉(zhuǎn)相除法（歐幾里得算法）(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.算法、框圖、程序.m=n×q＋r輾轉(zhuǎn)相除法（歐幾里得算法）(2)程序框圖：開始輸入m,nr=mMODnm=nr=0?是否n=r輸出m結(jié)束8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0.m=n×q＋r輾轉(zhuǎn)相除法（歐幾里得算法）(3)程序：INPUT“m,n=”;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0.例2.求98與63的最大公約數(shù).解：98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝1414－7＝7所以，98和63的最大公約數(shù)等于7這又是為什么？更相減損術(shù)思考：上面例子中的算理是什么？.定義：所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公約數(shù)。更相減損術(shù)

《九章算術(shù)》中的更相減損術(shù)：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。背景介紹：循環(huán)結(jié)構(gòu).1.用更相減損術(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ù)即為所求。.請(qǐng)比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別思考?（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字