輾轉(zhuǎn)相除法和更相減損術(shù)課件

1、1.3.1 輾轉(zhuǎn)相除法和更相減損術(shù)臨高中學(xué) 李吉傳 2019年5月8日第1頁，共20頁。復(fù)習(xí)1.研究一個(gè)實(shí)際問題的算法，主要從哪幾方面展開？2.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？3.在程序設(shè)計(jì)中基本的算法語句有哪幾種？算法步驟、程序框圖和編寫程序三方面展開.順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句第2頁，共20頁。一、輾轉(zhuǎn)相除法 思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？ 先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù). 第3頁，共20頁。 思考2:對于8251與6105這兩個(gè)數(shù)，它們的

2、最大公約數(shù)是多少？你是怎樣得到的？ 由于它們公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.有沒有其它的方法可以較簡單的找出它們的最大公約數(shù)呢？第4頁，共20頁。 思考3：注意到8251=61051+2146，那么8251與6105這兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？ 我們發(fā)現(xiàn)6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等. 思考4：重復(fù)上述操作，你能得到8251與6105這兩個(gè)數(shù)的最大公約數(shù)嗎？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+

3、2146，6105=21462+1813，第5頁，共20頁。 上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.第一步，給定兩個(gè)正整數(shù)m，n(mn).第二步，計(jì)算m除以n所得的余數(shù)r. 第三步，m=n，n=r. 第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步. 思考5:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？第6頁，共20頁。程序框圖開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND第7頁，共20頁。 思考6:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法

4、求兩個(gè)正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？第8頁，共20頁。開始輸入m，n求m除以n的余數(shù)rm=nr0？否輸出m結(jié)束是n=rINPUT m，nWHILE r0r=m MOD nm=nn=rWENDPRINT mEND第9頁，共20頁。二、更相減損術(shù) 九章算術(shù)是中國古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”也可以用來求兩個(gè)數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”意思是： 第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù). 若是，用2約簡；若不是，執(zhí)行第二步. 第二步：以較大的數(shù)減去較小的數(shù)，接著把差與較小的數(shù)比較，并以大

5、數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).第10頁，共20頁。例1：用更相減損術(shù)求98與63的最大公約數(shù).98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因?yàn)?3不是偶數(shù)，所以所以最大公約數(shù)是7.第11頁，共20頁。 例2 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù). 168=931+75， 93=751+18， 75=184+3， 18=36.輾轉(zhuǎn)相除法：第12頁，共20頁。更相減損術(shù): 168-93=75， 93-75=18， 75-18=57， 57-18=39， 3

6、9-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.第13頁，共20頁。例3 用更相減損術(shù)求80與36的最大公約數(shù).第14頁，共20頁。 例4 求325，130，270三個(gè)數(shù)的最大公約數(shù). 因?yàn)?25=1302+65，130=652，所以325與130的最大公約數(shù)是65. 因?yàn)?70=654+10，65=106+5，10=52，所以65與270最大公約數(shù)是5. 故325，130，270三個(gè)數(shù)的最大公約數(shù)是5.第15頁，共20頁。 練習(xí):用更相減損術(shù)求兩個(gè)正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？ 第一步，給定兩個(gè)正整數(shù)m，n(mn). 第二步，計(jì)算m-n所得的差k. 第三步，比較n與k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，則m，n的最大公約數(shù)等于m；否則，返回第二步. 討論:該算法的程序框圖如何表示？第16頁，共20頁。開始輸入m，nnk？m=n是輸出m結(jié)束mn？k=m-n是否n=km=k否 討論:該程序框圖對應(yīng)的程序如何表述？第17頁，共20頁。INPUT m，nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND開始輸入m