輾轉(zhuǎn)相除法與更相減損術(shù) 完整版課件

1．3算法案例1．用兩數(shù)中

的數(shù)減去

的數(shù)，再用

構(gòu)成新的一對數(shù)，再用

減

，以同樣的操作一直做下去，直到所得的兩數(shù)相等為止，這個數(shù)就是這兩個數(shù)的最大公約數(shù)．這個方法稱作“更相減損術(shù)”，用它編寫的算法稱作“等值算法”．較大較小所得差和較小數(shù)大數(shù)小數(shù)2．古希臘求兩個正整數(shù)的最大公約數(shù)的方法是

：用

除以

所得的

和

構(gòu)成新的一對數(shù)，繼續(xù)做上面的除法，直到大數(shù)被小數(shù)除盡，這個較小的數(shù)就是最大公約數(shù)．據(jù)此編寫的算法，也稱作“歐幾里得算法”．輾轉(zhuǎn)相除法較大數(shù)較小數(shù)余數(shù)較小數(shù)3．對于正整數(shù)m與n(m>n)，總能找到整數(shù)q和r(0≤r<n)使得m＝nq＋r成立，這個除法稱為帶余除法．通常記r＝mMODn.重點：算法案例的原理、算法設(shè)計及算法思想的體會．難點：理解算法案例的內(nèi)容及具體算法設(shè)計的關(guān)鍵步驟．一、弄清算法原理，掌握算法程序，經(jīng)歷算法設(shè)計過程，體會算法設(shè)計的關(guān)鍵環(huán)節(jié)，領(lǐng)悟算法思想．1．輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除的原理：設(shè)m，n是兩個整數(shù)(不妨設(shè)m>n)，用m除以n，若商為q1，余數(shù)為r1(0≤r1<n)，則m＝n·q1＋r1，顯然若x是m和n的公約數(shù)，即x能整除m和n，則x也必然能整除r1，這樣x也是n和r1的公約數(shù)，故求m和n的公約數(shù)就是求n和r1的公約數(shù)；同理，用n除以r1，得n＝r1·q2＋r2(0≤r2<r1)，故求m和n的公約數(shù)就是求r2和r1的公約數(shù)，…，依次下去，由于m>n>r1>r2>…，所以到某一步必然有ri＝ri＋1·qi＋2，即ri恰能被ri＋1整除，這時ri＋1是ri和ri＋1的最大公約數(shù)，它也必然是ri－1和ri、ri－2和ri－1、…、r1與r2、n和r2、m和n的最大公約數(shù)．(2)輾轉(zhuǎn)相除法的算法分析：由以上輾轉(zhuǎn)相除法的原理可以發(fā)現(xiàn)，輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)，考慮到算法中的賦值語句可以對同一變量多次賦值，我們可以把較大的數(shù)用變量m表示，把較小的數(shù)用變量n表示，這樣式子m＝n·q＋r(0≤r<n)就是一個反復(fù)執(zhí)行的步驟，因此可以用循環(huán)結(jié)構(gòu)實現(xiàn)算法．如圖．(3)用輾轉(zhuǎn)相除法求任意兩個正整數(shù)最大公約數(shù)的程序框圖．由于輾轉(zhuǎn)相除法總是用較大的數(shù)去除以較小的數(shù)，所以首先要對一開始給定的兩數(shù)的大小進(jìn)行判斷，并將大數(shù)賦給m，小數(shù)賦給n，然后再執(zhí)行下面的過程．程序框圖如圖．(4)用輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)的程序設(shè)計：2．更相減損術(shù)(1)更相減損術(shù)求兩數(shù)最大公約數(shù)的過程與算法設(shè)計．對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，接著把得到的差與較小的數(shù)比較，用這時兩個數(shù)中較大的數(shù)減去較小的數(shù)，繼續(xù)這樣的操作(大數(shù)減小數(shù))，直到所得的數(shù)相等為止，那么這個數(shù)(相等數(shù))就是所求的最大公約數(shù)．顯然，上述過程中大數(shù)減去小數(shù)是一個重復(fù)執(zhí)行的過程，因此只需將大數(shù)賦給變量a，小數(shù)賦給變量b，那么就可以通過循環(huán)結(jié)構(gòu)實現(xiàn)算法．或當(dāng)a>b時，將a－b賦給a，b＝b，當(dāng)a<b時，a＝a，將b－a賦給b然后再進(jìn)行比較，依次類推用循環(huán)結(jié)構(gòu)實現(xiàn)．(2)更相減損術(shù)求最大公約數(shù)的程序設(shè)計如下：請自行將其直到型循環(huán)結(jié)構(gòu)算法寫出來．3．輾轉(zhuǎn)相除法與更相減損術(shù)有著相同的算法依據(jù)，但要注意運算過程的差別，輾轉(zhuǎn)相除法的上一次運算的除數(shù)和余數(shù)分別作為下一次運算的被除數(shù)和除數(shù)，其結(jié)果直至余數(shù)為零得出．更相減損術(shù)在上一次運算結(jié)束后，比較減數(shù)和差的大小，將大的作為下一次運算的被減數(shù)，小的作為減數(shù)，直至出現(xiàn)相等數(shù)時得到結(jié)果．由此可見，二者算法是相似的．主要區(qū)別在于，輾轉(zhuǎn)相除法進(jìn)行的是除法運算，即輾轉(zhuǎn)相除，更相減損術(shù)進(jìn)行的是減法運算，即輾轉(zhuǎn)相減，但其實質(zhì)都是一個不斷的遞歸過程．另外兩者在算法設(shè)計上有一個重要的區(qū)別點，輾轉(zhuǎn)相除法，下一次進(jìn)行相除時，由上一次的除數(shù)和余數(shù)直接相除即可．而更相減損術(shù)下一次相減前必須有一個判斷大小的過程，以區(qū)別誰做被減數(shù)．這些內(nèi)容都是應(yīng)特別注意的關(guān)鍵環(huán)節(jié)．4．用更相減損術(shù)求兩正整數(shù)的最大公約數(shù)時，若兩數(shù)為偶數(shù)，可先約去2，這時莫忘記求得的相等兩數(shù)乘以約簡的數(shù)才是所求最大公約數(shù)．一、填空題1．在對16和12求最大公約數(shù)時，整個操作如下：(16,12)―→(4,12)―→(4,8)―→(4,4)，由此可以看出12和16的最大公約數(shù)是________．[答案]

42．1443與999的最大公約數(shù)是________．[答案]

111[解析]

(999,1443)―→(999,444)―→(555,444)―→(111,444)―→(111,333)―→(111,222)―→(111,111)或1443－999＝444,999－444＝555,555－444＝111,444－111＝333,333－111＝222,222－111＝111.自己用輾轉(zhuǎn)相除法寫出解答過程．3．運算速度快是計算機一個很重要的特點，而算法好壞的一個重要標(biāo)志是________．[答案]

運算次數(shù)4．2004與4509的最大公約數(shù)為________．[答案]

501[解析]

∴4509＝33×167，∴2004與4509的最大公約數(shù)為3×167＝501.自己用輾轉(zhuǎn)相除法和更相減損術(shù)寫出解答．二、解答題5．寫出從鍵盤任