算法案例（輾轉(zhuǎn)相除法）

1、算算 法法 案案 例例 第一課時 1. 回顧算法的三種表示方法：回顧算法的三種表示方法： （1）、自然語言）、自然語言 （2）、程序框圖）、程序框圖 （3）、程序語言）、程序語言 （三種邏輯結(jié)構(gòu)）（三種邏輯結(jié)構(gòu)） （五種基本語句）（五種基本語句） 復習引入 2. 思考：思考： 小學學過的求兩個數(shù)的最大公約數(shù)的方法？小學學過的求兩個數(shù)的最大公約數(shù)的方法？ 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直 除到所得的商是互質(zhì)數(shù)為止，然后把所有的除到所得的商是互質(zhì)數(shù)為止，然后把所有的 除數(shù)連乘起來除數(shù)連乘起來. 例：求下面兩個正整數(shù)的最大公約數(shù)：例：求下面兩個正整數(shù)的最大公約數(shù)：

2、 （1）求）求25和和35的最大公約數(shù)的最大公約數(shù) （2）求）求49和和63的最大公約數(shù)的最大公約數(shù) 25（1） 5 5 35 7 49（2） 7 7 63 9 所以，所以，25和和35的最大公約數(shù)為的最大公約數(shù)為5所以，所以，49和和63的最大公約數(shù)為的最大公約數(shù)為7 思考：除了用這種方法外還有沒有其它方法？思考：除了用這種方法外還有沒有其它方法？ 例：如何算出例：如何算出8251和和6105的最大公約數(shù)？的最大公約數(shù)？ 新課講解：新課講解： 一、輾轉(zhuǎn)相除法（歐幾里得算法）一、輾轉(zhuǎn)相除法（歐幾里得算法） 1、定義：、定義： 所謂輾轉(zhuǎn)相除法，就是對于給定的兩個所謂輾轉(zhuǎn)相除法，就是對于給定的兩個

3、 數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為 零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)， 繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則 這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。 2、步驟：、步驟： （以求（以求8251和和6105的最大公約數(shù)的過程為例）的最大公約數(shù)的過程為例） 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù) 8251=61051+2146 結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的

4、公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求8251和和 6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約數(shù)就可以了。的公約數(shù)就可以了。 第二步第二步 對對6105和和2146重復第一步的做法重復第一步的做法 6105=21462+1813 同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過程完整的過程 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 例：例： 用輾轉(zhuǎn)相除

5、法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù) 225=1351+90 135=901+45 90=452 顯然顯然37是是148和和37的最大公約數(shù)，的最大公約數(shù)， 也就是也就是8251和和6105的最大公約的最大公約 數(shù)數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是 225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1：從上面的兩個例子中可以看出計：從上面的兩個例子中可以看出計 算的規(guī)律是什么？算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù) S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù) S3：重復：重復S1，直到余數(shù)為，直到

6、余數(shù)為0 輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于0才停止的步驟，這實際上才停止的步驟，這實際上 是一個循環(huán)結(jié)構(gòu)。是一個循環(huán)結(jié)構(gòu)。 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 m = n q r 用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程 r=m MOD n m = n n = r r=0? 是 否 思考：你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？ (1)(1)、算法步驟：、算法步驟： 第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)m,n

7、(mn). 第二步：計算第二步：計算m除以除以n所得的余數(shù)所得的余數(shù)r. 第三步：第三步：m=n,n=r. 第四步：若第四步：若r0,則則m,n的最大公約數(shù)等于的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步否則轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)m. (2)(2)、程序框圖：、程序框圖： 開始開始 輸入輸入m,n r=m MOD n m=n r=0? 是是 否否 n=r 輸出輸出m 結(jié)束結(jié)束 (3)(3)、程序：、程序： INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 二、更相減損術(shù)二、更相減損術(shù) 可

8、半者半之，不可半者，副置分母、子之數(shù)，以少減多，可半者半之，不可半者，副置分母、子之數(shù)，以少減多， 更相減損，求其等也，以等數(shù)約之。更相減損，求其等也，以等數(shù)約之。 第一步：第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。 若是，則用若是，則用2約簡；若不是則執(zhí)行第二步。約簡；若不是則執(zhí)行第二步。 第二步：第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小以較大的數(shù)減較小的數(shù)，接著把所得的差與較小 的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的 減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。減

9、數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。 （1）、九章算術(shù)中的更相減損術(shù)： 1、背景介紹： （2）、現(xiàn)代數(shù)學中的更相減損術(shù)： 2、定義：、定義： 所謂更相減損術(shù)，就是對于給定的兩個所謂更相減損術(shù)，就是對于給定的兩個 數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和 較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減 去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較 小的數(shù)相等，此時相等的兩數(shù)便為原來兩個小的數(shù)相等，此時相等的兩數(shù)便為原來兩個 數(shù)的最大公約數(shù)。數(shù)的最大公約數(shù)。 例例: : 用更相減損術(shù)求用更

10、相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). . 解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，以大數(shù)減小數(shù)， 并輾轉(zhuǎn)相減并輾轉(zhuǎn)相減 989863633535 636335352828 353528287 7 28287 72121 21217 71414 14147 77 7 所以，所以，9898和和6363的最大公約數(shù)等于的最大公約數(shù)等于7 7 3、方法： 1、用更相減損術(shù)求兩個正數(shù)、用更相減損術(shù)求兩個正數(shù)84與與72的最大公約數(shù)的最大公約數(shù) 練習：練習： 思路分析：先約簡，再求思路分析：先約簡，再求21與與18的最大公約數(shù)的最大公約數(shù), 然

11、后乘以兩次約簡的質(zhì)因數(shù)然后乘以兩次約簡的質(zhì)因數(shù)4。 2、求、求324、243、135這三個數(shù)的最大公約數(shù)。這三個數(shù)的最大公約數(shù)。 思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個 數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約 數(shù)的最大公約數(shù)即為所求。數(shù)的最大公約數(shù)即為所求。 (1)、算法步驟、算法步驟 第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)a,b(ab); 第二步：若第二步：若a不等于不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)則執(zhí)行第三步；否則轉(zhuǎn) 到第五步；到第五步； 第三步：把第三步：把a-b的差賦予的差賦予r;

12、 第四步：如果第四步：如果br, 那么把那么把b賦給賦給a,把把r賦給賦給b;否否 則把則把r賦給賦給a，執(zhí)行第二步；，執(zhí)行第二步； 第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)b. *思考：你能根據(jù)更相減損術(shù)設(shè)計程序，求兩 個正整數(shù)的最大公約數(shù)嗎？ (2)(2)、程序框圖、程序框圖 開始開始 輸入輸入a,b ab? 是是 否否 輸出輸出b 結(jié)束結(jié)束 b=r a=b r=a-b rb? a=r 否否 是是 (3)(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 比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1 1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除 法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)法以除法為主，更相減損術(shù)以減法為主，計算次數(shù) 上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)