1.3算法案例第1頁1.3.4十進制化K進制1.3.1輾轉相除法和更相減損術1.3.2秦九韶算法1.3.3K進制化十進制1.3算法案例第2頁1.3.1輾除法和更相減損術第3頁一、輾轉相除法

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

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

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

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

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

我們發覺6105=2146×2+1813，同理，6105與2146條約數和2146與1813條約數相等.

思索4：重復上述操作，你能得到8251與6105這兩個數最大條約數嗎？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頁

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

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

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

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

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

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

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

例2分別用輾轉相除法和更相減損術求168與93最大條約數.168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.輾轉相除法：第13頁更相減損術: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頁

練習:用更相減損術求兩個正整數m，n最大條約數，能夠用什么邏輯結構來結構算法？其算法步驟怎樣設計？

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

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

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

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

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

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