數(shù)學(xué)：1[1].3.1《算法案例(輾轉(zhuǎn)相除法)》課件1(新人教版A必修3).ppt

1、輾轉(zhuǎn)相除法與更相減損術(shù),算 法 案 例,第一課時(shí),1. 回顧算法的三種表示方法：,（1）、自然語(yǔ)言,（2）、程序框圖,（3）、程序語(yǔ)言,（三種邏輯結(jié)構(gòu)）,（五種基本語(yǔ)句）,復(fù)習(xí)引入,2. 思考：,小學(xué)學(xué)過(guò)的求兩個(gè)數(shù)的最大公約數(shù)的方法？,先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái).,例：求下面兩個(gè)正整數(shù)的最大公約數(shù)：,（1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù),所以，25和35的最大公約數(shù)為5,所以，49和63的最大公約數(shù)為7,思考：除了用這種方法外還有沒(méi)有其它方法？,例：如何算出8251和6105的最大公約數(shù)？,新課講解：,一、輾

2、轉(zhuǎn)相除法（歐幾里得算法）,1、定義： 所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)。,2、步驟： （以求8251和6105的最大公約數(shù)的過(guò)程為例）,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146,結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。,第二步 對(duì)6105和2146重復(fù)第一步的做法6105=21462+1813同理61

3、05和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。,思考：從上述的過(guò)程你體會(huì)到了什么？,完整的過(guò)程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例： 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個(gè)例子中可以看出計(jì)算的規(guī)律是什么？,S1：用大數(shù)除以小

4、數(shù),S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3：重復(fù)S1，直到余數(shù)為0,輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。,m = n q r,用程序框圖表示出右邊的過(guò)程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,思考:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？,(1)、算法步驟：,第一步：輸入兩個(gè)正整數(shù)m,n(mn). 第二步：計(jì)算m除以n所得的余數(shù)r. 第三步：m=n,n=r. 第四步：若r0,則m,n的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)m.,(2)、程序框圖：,(3)、程序：

5、,INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,思考:你能用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？寫(xiě)出算法步驟、程序框圖和程序。,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,PRINT m,END,二、更相減損術(shù),可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼

6、續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。,（1）、九章算術(shù)中的更相減損術(shù)：,1、背景介紹：,（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：,2、更相減損術(shù),算理：所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)。,例: 用更相減損術(shù)求98與63的最大公約數(shù).,解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減,9863356335283528728721 21721 1477,所以，98和63的最大公約數(shù)等于7,3、方

7、法：,(1)、算法步驟,第一步：輸入兩個(gè)正整數(shù)a,b(ab); 第二步：若a不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)到第五步； 第三步：把a(bǔ)-b的差賦予r; 第四步：如果br, 那么把b賦給a,把r賦給b;否則把r賦給a，執(zhí)行第二步； 第五步：輸出最大公約數(shù)b.,*思考：你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？,(2)、程序框圖,(3)、程序,INPUT “a,b=“;a,b WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END,1、用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù),練習(xí)：,思路分析：先約簡(jiǎn)，再

8、求21與18的最大公約數(shù),然后乘以兩次約簡(jiǎn)的質(zhì)因數(shù)4。,2、求324、243、135這三個(gè)數(shù)的最大公約數(shù)。,思路分析：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。,比較輾轉(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)的形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。,小結(jié),1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直