1.3.1算法案例輾轉(zhuǎn)相除法和更相減損術(shù)市公開課金獎市賽課一等獎課件

1.3.1算法案例(一)—輾轉(zhuǎn)相除法與更相減損術(shù)必修③第一章算法初步咸豐一中楊金煜第1頁35915[問題1]：在小學，我們已經(jīng)學過求最大條約數(shù)知識，你能求出18與30最大條約數(shù)嗎？〖創(chuàng)設情景，揭示課題〗183023∴18和30最大條約數(shù)是2×3=6.方法：先用兩個數(shù)公有質(zhì)因數(shù)連續(xù)去除,一直除到所得商是互質(zhì)數(shù)為止,然后把全部除數(shù)連乘起來.練習1(1)求25和35最大條約數(shù),(2)求49和63最大條約數(shù).25（1）5535749（2）77639所以，25和35最大條約數(shù)為5所以，49和63最大條約數(shù)為7第2頁〖創(chuàng)設情景，揭示課題〗[問題2]:我們都是利用找條約數(shù)方法來求最大條約數(shù)，假如條約數(shù)比較大而且依據(jù)我們觀察又不能得到一些條約數(shù)，我們又應該怎樣求它們最大條約數(shù)？比如求8251與6105最大條約數(shù)?思緒1：試值？！何時結(jié)束？有何好方法？第3頁案例一：輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和6105最大條約數(shù)過程第一步

用兩數(shù)中較大數(shù)除以較小數(shù)，求得商和余數(shù)

8251=6105×1+2146結(jié)論：8251和6105條約數(shù)就是6105和2146條約數(shù)，求8251和6105最大條約數(shù)，只要求出6105和2146條約數(shù)就能夠了.第二步對6105和2146重復第一步做法

6105=2146×2+1813

同理6105和2146最大條約數(shù)也是2146和1813最大條約數(shù).第4頁完整過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0比如，用輾轉(zhuǎn)相除法求225和135最大條約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37最大條約數(shù)，也就是8251和6105最大條約數(shù)顯然45是90和45最大條約數(shù)，也就是225和135最大條約數(shù)思索：從上面兩個例子能夠看出計算規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復S1，直到余數(shù)為0第5頁問題提出：你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？算法分析：從上面對輾轉(zhuǎn)相除法認識中能夠看出，輾轉(zhuǎn)相除法中包含重復操作步驟，所以能夠用循環(huán)結(jié)構(gòu)來結(jié)構(gòu)算法。算法步驟：第一步，給定兩個正整數(shù)m，n(m>n)。第二步，計算m除以n所得余數(shù)r。第三步，m=n，n=r。第四步，若r=0，則m,n最大條約數(shù)等于m；不然，返回第二步。第6頁否思索：畫出輾轉(zhuǎn)相除法程序框圖并設計其程序開始輸入兩個正數(shù)整m,nr=mMODnr=0?輸出m結(jié)束m=nn=r是INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND第7頁思索：你能用當型循環(huán)結(jié)構(gòu)結(jié)構(gòu)算法，求兩個正整數(shù)最大條約數(shù)嗎？試寫出算法步驟、程序框圖和程序。分析：在使用當型循環(huán)結(jié)構(gòu)時，因為在輸入兩個正數(shù)后，直接進入判斷r>0,這里沒有一個最初r值，因而在設計過程中，可先令r=1。算法步驟：第一步，給定兩個正整數(shù)m，n(m>n)。第二步,令r=1.第三步，若r>０，則執(zhí)行第四步；不然，m，n最大條約數(shù)等于m,結(jié)束算法.第四步，計算m除以n所得余數(shù)r。第五步，m=n，n=r,返回第三步.第8頁開始輸入m,nr=1r>0?輸出m結(jié)束n=r求m除以n余數(shù)rm=n是否程序框圖以下：程序以下：INPUTm,nr=1WHILEr>0r=mMODnm=nn=rWENDPRINTmEND第9頁知識探究（二）:更相減損術(shù)

1:設兩個正整數(shù)m>n，若m-n=d，則m與n最大條約數(shù)和n與k最大條約數(shù)相等.重復利用這個原理，可求得98與63最大條約數(shù)為多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，第10頁《九章算術(shù)》——更相減損術(shù)

算理：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之.算法分析：第一步、任意給定兩個正整數(shù)，判斷他們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步。第二步、以較大數(shù)減較小數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得減數(shù)和差相等為止，則這個等數(shù)就是所求最大條約數(shù).第11頁例2、用更相減損術(shù)求98與63最大條約數(shù)（自己按照步驟求解）解：因為63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。=7所以，98和63最大條約數(shù)等于7。（98，63）=（63，35）98-63=35

63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）第12頁練習：用更相減損術(shù)求以下兩數(shù)最大條約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417思索：更相減損直到何時結(jié)束？利用是哪種算法結(jié)構(gòu)？更相減損是一個重復執(zhí)行直到減數(shù)等于差時停頓步驟，這實際也是一個循環(huán)結(jié)構(gòu)第13頁2:上述求兩個正整數(shù)最大條約數(shù)方法稱為更相減損術(shù).普通地，用更相減損術(shù)求兩個正整數(shù)m，n最大條約數(shù)，能夠用什么邏輯結(jié)構(gòu)來結(jié)構(gòu)算法？其算法步驟怎樣設計？第一步，給定兩個正整數(shù)m，n(m>n).

第三步，計算m-n所得差d.第四步，判斷“d不等于n”是否成立，若是，則將n，d中大者用m表示，小者用n表示，返回第三步；不然，2^k*d(k是約簡整數(shù)2個數(shù))為所求最大條約數(shù)。第二步，若m、n都是偶數(shù)，則不停用2約簡，使他們不一樣時是偶數(shù)，約簡兩個數(shù)仍記為m，n。第14頁討論：

你能依據(jù)更相減損術(shù)算法步驟畫出其程序框圖并寫出程序語句嗎?第15頁其算法步驟也能夠這么設計第一步，給定兩個正整數(shù)m，n(m>n).

第二步，計算m-n所得差d.第三步，比較n與d大小，其中大者用m表 示，小者用n表示.

第四步，若m=n，則m，n最大條約數(shù)等于 m；不然，返回第二步.第16頁其程序框圖和程序語句以下：

INPUT“m,n=”;m,nIFm<nTHENa=mm=nn=aENDIFd=m-nWHILEd<>nIFd>nTHENm=dELSEm=nn=dENDIFd=m-nWENDPRINTdENDm第17頁思索：輾轉(zhuǎn)相除法與更相減損術(shù)有什么區(qū)分和聯(lián)絡？區(qū)分：計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為?。辉谟嬎愦螖?shù)上，輾轉(zhuǎn)相除法計算次數(shù)相對較少，尤其當兩個數(shù)大小差異較大時計算次數(shù)區(qū)分較顯著；從結(jié)果輸出時候看，輾轉(zhuǎn)相除法當余數(shù)為0時輸出除數(shù)，更相減損術(shù)當差和減數(shù)相等時輸出差。聯(lián)絡：都是求最大條約數(shù)方法。因為做一次除法與做若干次減法效果相同，商就是減法次數(shù)，余數(shù)就是最終差，由此可知二者是完全統(tǒng)一！第18頁練習：1，以下說法中正確是（）A輾轉(zhuǎn)相除法是中國古代數(shù)學中算法B更相減損術(shù)與輾轉(zhuǎn)相除法算理完全不一樣C輾轉(zhuǎn)相除法與更相減損術(shù)相比較，用輾轉(zhuǎn)相除法求最大條約數(shù)最優(yōu)越D輾轉(zhuǎn)相除法與更相減損術(shù)，在設計程序時，都要用到循環(huán)結(jié)構(gòu)。D第19頁

2，4830與3289最大條約數(shù)為_______3，用更相減損術(shù)求87與27最大條約數(shù)時，重復相減，直至求出最大條約數(shù)，需要進行減法運算次數(shù)是______4，用輾轉(zhuǎn)相除法求87與27最大條約數(shù)，需要進行除法運算次數(shù)是_____5，46，115，276最大條約數(shù)是____238323第20頁

6，下面是求115與276最大條約數(shù)程序，把程序補充完整。a=115b=276DOr=__________a=bb=rLOOPUNTILr=____PRINTaEN