算法案例1-輾轉(zhuǎn)相除法.ppt

1.3 算法案例,第一課時,問題提出,1.研究一個實際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計中基本的算法語句有哪幾種？,2.“求兩個正整數(shù)的最大公約數(shù)”是數(shù)學(xué)中的一個基礎(chǔ)性問題，它有各種解決辦法，我們以此為案例，對該問題的算法作一些探究.,輾轉(zhuǎn)相除法與 更相減損術(shù),復(fù)習(xí)引入,1、MOD 表示什么意思？ a MOD b ab (a b 是正整數(shù)),a=b*q+r,(0=rb),2、求 18與30的最大公約數(shù)。,先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù).,思考： 若求8251和6105的最大公約數(shù)呢？,注意到 8251=61051+2146 那么8251和6105這兩個數(shù)的公約數(shù)和 6105與2146的公約數(shù)有什么關(guān)系？,思考:又6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.重復(fù)上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),輾轉(zhuǎn)相除法 （歐幾里得算法）,例：用輾轉(zhuǎn)相除法求225和135的最大公約數(shù),思考：能不能把輾轉(zhuǎn)相除法設(shè)計成算法呢？ 關(guān)鍵步驟是什么邏輯結(jié)構(gòu)？,用程序框圖表示出右邊的過程,思考 其算法步驟如何設(shè)計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m除以n所得的余數(shù)r.,第三步，m=n，n=r.,第四步，若r=0，則m，n的最大公約數(shù)等 于m；否則，返回第二步.,思考:該程序框圖和的程序如何表述？,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,知識探究（二）:更相減損術(shù),思考1:設(shè)兩個正整數(shù)mn，若m-n=k，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等.反復(fù)利用這個原理，可求得98與63的最大公約數(shù)為多少？,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,二、更相減損術(shù),可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。,（1）、九章算術(shù)中的更相減損術(shù)：,（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：,1、用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù),練習(xí)：,思路分析：先約簡，再求21與18的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)4。,2、求324、243、135這三個數(shù)的最大公約數(shù)。,思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。,比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。 （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。,小結(jié),思考題,1、用當(dāng)型循環(huán)結(jié)構(gòu)寫出算法； 2、試寫出更相減損術(shù)的算法程序； 3、試寫出求兩個正整數(shù)m、n的最小公倍數(shù)的程序。,評價一個算法好壞