算法案例1-輾轉(zhuǎn)相除法與相減損術(shù)市公開課一等獎省賽課微課金獎?wù)n件

1.3算法案例第1頁1.3.4十進(jìn)制化K進(jìn)制1.3.1輾轉(zhuǎn)相除法和更相減損術(shù)1.3.2秦九韶算法1.3.3K進(jìn)制化十進(jìn)制1.3算法案例第2頁1.3.1輾除法和更相減損術(shù)第3頁一、輾轉(zhuǎn)相除法

思索1:18與30最大條約數(shù)是多少？你是怎樣得到？

先用兩個數(shù)公有質(zhì)因數(shù)連續(xù)去除，一直除到所得商是互質(zhì)數(shù)為止，然后把全部除數(shù)連乘起來即為最大條約數(shù).第4頁

思索2:對于8251與6105這兩個數(shù)，它們最大條約數(shù)是多少？你是怎樣得到？

因為它們公有質(zhì)因數(shù)較大，利用上述方法求最大條約數(shù)就比較困難.有沒有其它方法能夠較簡單找出它們最大條約數(shù)呢？第5頁

思索3：注意到8251=6105×1+2146，那么8251與6105這兩個數(shù)條約數(shù)和6105與2146條約數(shù)有什么關(guān)系？

我們發(fā)覺6105=2146×2+1813，同理，6105與2146條約數(shù)和2146與1813條約數(shù)相等.

思索4：重復(fù)上述操作，你能得到8251與6105這兩個數(shù)最大條約數(shù)嗎？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，第6頁

上述求兩個正整數(shù)最大條約數(shù)方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.第一步，給定兩個正整數(shù)m，n(m>n).第二步，計算m除以n所得余數(shù)r.第三步，m=n，n=r.

第四步，若r=0，則m，n最大條約數(shù)等于m；不然，返回第二步.

思索5:你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？第7頁程序框圖開始輸入m，n求m除以n余數(shù)rm=nn=rr=0？是輸出m結(jié)束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND第8頁

思索6:假如用當(dāng)型循環(huán)結(jié)構(gòu)結(jié)構(gòu)算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m、n最大條約數(shù)程序框圖和程序分別怎樣表示？第9頁開始輸入m，n求m除以n余數(shù)rm=nn>0？否輸出m結(jié)束是n=rINPUTm，nWHILEn>0r=mMODnm=nn=rWENDPRINTmEND第10頁二、更相減損術(shù)

《九章算術(shù)》是中國古代數(shù)學(xué)專著，其中“更相減損術(shù)”也能夠用來求兩個數(shù)最大條約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”意思是：

第一步：任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡；若不是，執(zhí)行第二步.

第二步：以較大數(shù)減去較小數(shù)，接著把差與較小數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得數(shù)相等為止，則這個等數(shù)或這個數(shù)與約簡數(shù)乘積就是所求最大條約數(shù).第11頁例1：用更相減損術(shù)求98與63最大條約數(shù).98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因為63不是偶數(shù)，所以所以最大條約數(shù)是7.第12頁

例2分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93最大條約數(shù).168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.輾轉(zhuǎn)相除法：第13頁更相減損術(shù):168-93=75，

93-75=18，

75-18=57，

57-18=39，

39-18=21，

21-18=3，

18-3=15，

15-3=12，

12-3=9，

9-3=6，

6-3=3.第14頁

練習(xí):用更相減損術(shù)求兩個正整數(shù)m，n最大條約數(shù)，能夠用什么邏輯結(jié)構(gòu)來結(jié)構(gòu)算法？其算法步驟怎樣設(shè)計？

第一步，給定兩個正整數(shù)m，n(m>n).

第二步，計算m-n所得差k.

第三步，比較n與k大小，其中大者用m表示，小者用n表示.

第四步，若m=n，則m，n最大條約數(shù)等于m；不然，返回第二步.

討論:該算法程序框圖怎樣表示？第15頁開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否

討論:該程序框圖對應(yīng)程序怎樣表述？第16頁INPUTm，nWHILEm≠nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n