輾轉相除法和更相減損術.pptVIP

1.3.1 輾轉相除法 和更相減損術,臨高中學 李吉傳 2013年5月8日,復習,1.研究一個實際問題的算法，主要從哪幾方面展開？,2.在程序框圖中算法的基本邏輯結構有哪幾種？,3.在程序設計中基本的算法語句有哪幾種？,算法步驟、程序框圖和編寫程序三方面展開.,順序結構、條件結構、循環(huán)結構,輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句,一、輾轉相除法,思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？,先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù).,思考2:對于8251與6105這兩個數(shù)，它們的最大公約數(shù)是多少？你是怎樣得到的？,由于它們公有的質因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.有沒有其它的方法可以較簡單的找出它們的最大公約數(shù)呢？,思考3：注意到8251=61051+2146，那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關系？,我們發(fā)現(xiàn)6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.,思考4：重復上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉相除法或歐幾里得算法.,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m除以n所得的余數(shù)r.,第三步，m=n，n=r.,第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.,思考5:你能把輾轉相除法編成一個計算機程序嗎？,程序框圖,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,思考6:如果用當型循環(huán)結構構造算法，則用輾轉相除法求兩個正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？,INPUT m，n,WHILE r0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,二、更相減損術,九章算術是中國古代的數(shù)學專著，其中的“更相減損術”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”,意思是：,第一步：任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù). 若是，用2約簡；若不是，執(zhí)行第二步.,第二步：以較大的數(shù)減去較小的數(shù)，接著把差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個等數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).,例1：用更相減損術求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.,例2 分別用輾轉相除法和更相減損術求168與93的最大公約數(shù).,168=931+75， 93=751+18， 75=184+3， 18=36.,輾轉相除法：,更相減損術:,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.,例3 用更相減損術求80與36的最大公約數(shù).,例4 求325，130，270三個數(shù)的最大公約數(shù).,因為325=1302+65，130=652，所以325與130的最大公約數(shù)是65.,因為270=654+10，65=106+5，10=52，所以65與270最大公約數(shù)是5.,故325，130，270三個數(shù)的最大公約數(shù)是5.,練習:用更相減損術求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結構來構造算法？其算法步驟如何設計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m-n所得的差k.,第三步，比較n與k的大小，其中大者用m表示，小者用n表示.,第四步，若m=n，則m，n的最大公約數(shù)等于m；否則，返回第二步.,討論:該算法的程序框圖如何表示？,討論:該程序框圖對應的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk T