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

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

的數(shù)減去

的數(shù)，再用

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

減

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

：用

除以

所得的

和

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

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

501[解析]

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