數(shù)學(xué)13算法案例輾轉(zhuǎn)相除法與更相減損術(shù)新人教A版必修3省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

算法案例(第一課時)第1頁ks5u精品課件案例1輾轉(zhuǎn)相除法與更相減損術(shù)第2頁ks5u精品課件1.回顧算法三種表述：自然語言程序框圖程序語言（三種邏輯結(jié)構(gòu)）（五種基本語句）第3頁ks5u精品課件2.思索：

小學(xué)學(xué)過求兩個數(shù)最大條約數(shù)方法？先用兩個公有質(zhì)因數(shù)連續(xù)去除，一直除到所得商是互質(zhì)數(shù)為止，然后把全部除數(shù)連乘起來.第4頁ks5u精品課件1、求兩個正整數(shù)最大條約數(shù)（1）求25和35最大條約數(shù)（2）求49和63最大條約數(shù)25（1）5535749（2）77639所以，25和35最大條約數(shù)為5所以，49和63最大條約數(shù)為72、除了用這種方法外還有沒有其它方法？算出8256和6105最大條約數(shù).第5頁ks5u精品課件輾轉(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重復(fù)第一步做法

6105=2146×2+1813

同理6105和2146最大條約數(shù)也是2146和1813最大條約數(shù)。為什么呢？思考：從上述的過程你體會到了什么？第6頁ks5u精品課件完整過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用輾轉(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ù)思索1：從上面兩個例子能夠看出計算規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0第7頁ks5u精品課件

輾轉(zhuǎn)相除法是一個重復(fù)執(zhí)行直到余數(shù)等于0停頓步驟，這實際上是一個循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框圖表示出右邊過程r=mMODnm=nn=rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？第8頁ks5u精品課件1、輾轉(zhuǎn)相除法（歐幾里得算法）（1）算理：所謂輾轉(zhuǎn)相除法，就是對于給定兩個數(shù)，用較大數(shù)除以較小數(shù)。若余數(shù)不為零，則將余數(shù)和較小數(shù)組成新一對數(shù)，繼續(xù)上面除法，直到大數(shù)被小數(shù)除盡，則這時較小數(shù)就是原來兩個數(shù)最大條約數(shù)。第9頁ks5u精品課件（2）算法步驟第一步：輸入兩個正整數(shù)m,n(m>n).第二步：計算m除以n所得余數(shù)r.第三步：m=n,n=r.第四步：若r＝0,則m,n最大條約數(shù)等于m；不然轉(zhuǎn)到第二步.第五步：輸出最大條約數(shù)m.第10頁ks5u精品課件（3）程序框圖（4）程序INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND開始輸入m,nr=mMODnm=nr=0?是否n=r輸出m結(jié)束第11頁ks5u精品課件《九章算術(shù)》——更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大數(shù)減較小數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得減數(shù)和差相等為止，則這個等數(shù)就是所求最大條約數(shù)。第12頁ks5u精品課件2、更相減損術(shù)（1）算理：所謂更相減損術(shù)，就是對于給定兩個數(shù)，用較大數(shù)減去較小數(shù)，然后將差和較小數(shù)組成新一對數(shù)，再用較大數(shù)減去較小數(shù)，重復(fù)執(zhí)行此步驟直到差數(shù)和較小數(shù)相等，此時相等兩數(shù)便為原來兩個數(shù)最大條約數(shù)。第13頁ks5u精品課件（2）算法步驟第一步：輸入兩個正整數(shù)a,b(a>b);第二步：若a不等于b,則執(zhí)行第三步；不然轉(zhuǎn)到第五步；第三步：把a(bǔ)-b差賦予r;第四步：假如b>r,那么把b賦給a,把r賦給b;不然把r賦給a，執(zhí)行第二步；第五步：輸出最大條約數(shù)b.第14頁ks5u精品課件（3）程序框圖（4）程序INPUT“a,b=“;a,bWHILEa<>br=a-bIFb>rTHENa=bb=rELSEa=rENDIFWENDPRINTbEND開始輸入a,ba≠b?是否輸出b結(jié)束b=ra=br=a-br<b?a=r否是第15頁ks5u精品課件例3用更相減損術(shù)求98與63最大條約數(shù)解：因為63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝2114－7＝7所以，98和63最大條約數(shù)等于7用更相減損術(shù)求兩個正數(shù)84與72最大條約數(shù)．練習(xí)：先約簡，再求21與18最大條約數(shù),然后乘以兩次約簡質(zhì)因數(shù)4第16頁ks5u精品課件例3、求324、243、135這三個數(shù)最大條約數(shù)。思緒分析：求三個數(shù)最大條約數(shù)能夠先求出兩個數(shù)最大條約數(shù)，第三個數(shù)與前兩個數(shù)最大條約數(shù)最大條約數(shù)即為所求。第17頁ks5u精品課件比較輾轉(zhuǎn)相除法與更相減損術(shù)區(qū)分（1）都是求最大條約數(shù)方法，計算上