公開課算法案例-輾轉(zhuǎn)相除法與更相減損術(shù)課件人

1、1.3 算法案例 第一課時(shí) 1. 我們是如何求兩個(gè)正數(shù)的最大公約數(shù)的？如：求下面兩個(gè)正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求2520和1470的最大公約數(shù)25（1）55357（2）147010 147 2520252所以，25和35的最大公約數(shù)為5 所以，2520和1470的最大公約數(shù)為210解：回顧736 217123如何算出8251和6105的最大公約數(shù)？2.輾轉(zhuǎn)相除法（歐幾里德算法）3.思考1:對(duì)于8251與6105這兩個(gè)數(shù)，由于 8251=61051+2146 8251與6105的公約數(shù)就是6105與 2146的公約數(shù)。？那么,8251與6105這兩個(gè)數(shù)的公約數(shù)和 6

2、105與2146的公約數(shù)有什么關(guān)系？ 4.思考2:重復(fù)上述操作，如何得到8251與 6105這兩個(gè)數(shù)的最大公約數(shù)？5.完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333 =1482+37148 = 374+0例： 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=1351+90135=901+4590 =452 +0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù) 顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù) S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3

3、：重復(fù)S1，直到余數(shù)為0從上面的兩個(gè)例子中可以看出 計(jì)算的規(guī)律是什么？ 6. 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。 8251=61051+2146 6105=21462+1813 2146=18131+333 1813= 3335+148333= 1482+37148= 374+0m = n q r思考3:輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 其算法步驟如何設(shè)計(jì)？ 第一步：給定兩個(gè)正整數(shù)m，n(mn)。第二步：計(jì)算m除以n所得的余數(shù)r。 第三步：m=n，n=r。第四步：判斷“r=0”是否成立， 若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步。 7

4、. 8251=61051+2146 6105=21462+1813 2146=18131+333 1813= 3335+148333= 1482+37148= 374+0m = n q r思考3:輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 其算法步驟如何設(shè)計(jì)？ 用程序框圖表示出右邊的過程r=m MOD nm = nn = r是否r=0?8.思考5: 如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？9.是開始求m除以n的余數(shù)rm=n否輸出m結(jié)束n=rr0？輸入m，nr=110.練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與 20723的最大公約數(shù). (5

5、3)20723=40815+3184081=31812+265318=2651+53265=535+011.練習(xí)2：求325，130，270三個(gè)數(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ù)是5.12. 可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。九章算術(shù)中的更相減損術(shù)：背景介紹： 任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是，則以較大的數(shù)減較小的數(shù)，接著把所得的差

6、與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。 現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：13.例: 用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)， 并輾轉(zhuǎn)相減 所以，98和63的最大公約數(shù)等于7 98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，14.98-63=3514-7=721-7=1428-7=2135-28=763-35=28思考6: 用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步 驟如何設(shè)計(jì)？程序框圖如何表示？m n k第一步，給定兩個(gè)正整數(shù)m，n(mn). 第二

7、步，計(jì)算m-n所得的差k. 第三步，比較n與k的大小，其中大 者用m表示，小者用n表示. 第四步，若m=n，則m，n的最大公約 數(shù)等于m；否則，返回第二步. 15.理論遷移 例1. 分別用輾轉(zhuǎn)相除法和更相減損 術(shù)求168與93的最大公約數(shù). 輾轉(zhuǎn)相除法： 168=931+75 93=751+18 75=184+3 18=36+016.更相減損術(shù): 168-93=75， 18-3=15， 93-75=18， 15-3=12， 75-18=57， 12-3=9， 57-18=39， 9-3=6， 39-18=21， 6-3=3。 21-18=3， 17.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求

8、最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到小結(jié)18. 1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時(shí)的較小的數(shù)即為原來兩個(gè)數(shù)的最大公約數(shù). 小結(jié)作業(yè) 2. 更相減損術(shù)，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的減法，直到

9、差和較小的數(shù)相等，此時(shí)相等的兩數(shù)即為原來兩個(gè)數(shù)的最大公約數(shù).19.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到小結(jié)20. 任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是，則以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。21.

10、例2 求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.22.該算法的程序框圖:開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否23.思考4:該程序框圖對(duì)應(yīng)的程序如何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND是開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？輸出m結(jié)束否24.開始輸入m，n求m除

11、以n的余數(shù)rm=nr=0？否輸出m結(jié)束n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND是25.知識(shí)探究（二）:更相減損術(shù) 可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。（1）、九章算術(shù)中的更相減損術(shù)：1、背景介紹：（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：26.INPUT “m,n=“

12、;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m- nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd 27.作業(yè)：P45練習(xí)：1.P48習(xí)題1.3A組：1.28.科學(xué)精神歐幾里德留給現(xiàn)代文明的寶貴遺產(chǎn)他的生平，后人所知甚少。大概早年在雅典就讀,深悉柏拉圖的學(xué)說。公元前300年左右，歐幾里德接受托勒密王（公元前364前283）的邀請(qǐng)，來到亞歷山大城，長期在那里工作。他是一位

13、溫良敦厚的教育家，對(duì)有志數(shù)學(xué)之士，總是循循善誘。但反對(duì)投機(jī)取巧、不肯刻苦鉆研的作風(fēng)，也反對(duì)狹隘實(shí)用觀點(diǎn)。 218x320 14k jpg歐幾里德 - 陳具才,具才軟件.29.學(xué)問追求真理而并非追求實(shí)利知識(shí)淵博的歐幾里德在教授學(xué)生時(shí)，像一個(gè)真正的父親那樣引導(dǎo)學(xué)生，關(guān)心他們。然而有時(shí)，他也用辛辣的諷刺來鞭撻學(xué)生中的傲慢之徒。斯托貝烏斯（約公元500年）轉(zhuǎn)述：有個(gè)學(xué)生在聽講“第一定理”之后，便問道：“學(xué)習(xí)幾何，究竟會(huì)有什么好處？”于是，歐幾里得轉(zhuǎn)身吩咐傭人說：“格魯米阿，拿三個(gè)錢幣給這位先生，因?yàn)樗朐趯W(xué)習(xí)中獲得實(shí)利?！薄皫缀螌W(xué)里沒有王者大道”及“科學(xué)無坦途”據(jù)希臘學(xué)者普羅克洛斯（約410485年）

14、轉(zhuǎn)述歷史記載，亞歷山大國王多祿米曾師從歐幾里得學(xué)習(xí)幾何，有一次對(duì)于歐幾里得一遍又一遍地解釋他的原理表示不耐煩。國王問道：“有沒有比你的方法簡(jiǎn)捷一些的學(xué)習(xí)幾何學(xué)的途徑？”歐幾里德回答：“陛下！原野上有兩種道路，一種是供平民百姓走的崎嶇小路，一條種供王者走的坦途。但是在幾何學(xué)里，大家只能走同一條崎嶇小路！走向?qū)W問，是沒有什么王者大道的！請(qǐng)陛下明白?！睔W幾里德的這番話，后代廣為傳誦，簡(jiǎn)略為“幾何無王者之大道”、“求知無坦途”，又成為馬克思引用并信奉的名言：“在科學(xué)上是沒有康莊大道可走的；只有在那崎嶇小路上不畏勞苦、勇敢攀登的人，有希望達(dá)到光輝的頂點(diǎn)！” 30.16世紀(jì)以前多少世代，中國在技術(shù)方面一直

15、領(lǐng)先于歐洲。但從來沒有出現(xiàn)一個(gè)可以同歐幾里德相比的、具有真正邏輯思維的中國數(shù)學(xué)家。結(jié)果，中國從未擁有過歐洲人那樣的數(shù)學(xué)理論體系。華夏文明和印度文明等東方文明固然偉大，但是在思維方式方面，自古以來就是存在嚴(yán)重欠缺的！自古以來，中國思想界一向擅長綜合、聯(lián)想、類比，固然具有“中國特色”，但是容易墮入籠統(tǒng)、含混、武斷、臆測(cè)、想當(dāng)然、浮皮潦草、牽強(qiáng)附會(huì)、不符實(shí)際的聯(lián)想類比、望文生義、不求甚解、含糊朦朧的表述方式。造成的危害是難以估量的。大量事實(shí)（甚至某些令人痛心而又可笑可嘆可悲的事實(shí)）表明，中國人普遍的思維方式亟需提高！這需要我們大家做許多扎實(shí)的認(rèn)真的工作！ 31.復(fù)習(xí)引入1. 回顧算法的三種表示方法：（1）、自然語言（2）、程序框圖（3）、程序語言（三種邏輯結(jié)構(gòu)）（五種基本語句）32.思考2:重復(fù)上述操作，如何得到8251與 6105這兩個(gè)數(shù)的最大公約數(shù)？2146=18131+333 148= 374+0 333= 1482+371813= 3335+1488251=61051+21466105=21462+181333.思考2:重復(fù)上述操作，如何得到8251與 6105這兩個(gè)數(shù)的最大公約數(shù)？2146=18131+333 148= 374