新課標人教A版高中數學必修三1.3.1算法案例課件

1、1.3算法案例（第一課時）表示算法的三種方式：算法步驟（自然語言）程序框圖（圖形語言）計算機程序（程序語言）復習引入3 59 15問題1：在小學，我們已經學過求最大公約數的知識，你能求出18與30的最大公約數嗎？18 302318和30的最大公約數是23=6.先用兩個數公有的質因數連續(xù)去除,一直除到所得的商是互質數為止,然后把所有的除數連乘起來.問題2:求8251與6105的最大公約數?新課講解輾轉相除法（歐幾里得算法）觀察用輾轉相除法求8251和6105的最大公約數的過程 第一步 用兩數中較大的數除以較小的數，求得商和余數8251=61051+2146結論： 8251和6105的公約數就是6

2、105和2146的公約數，求8251和6105的最大公約數，只要求出6105和2146的公約數就可以了。第二步 對6105和2146重復第一步的做法6105=21462+1813同理6105和2146的最大公約數也是2146和1813的最大公約數。 新課講解完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0顯然37是148和37的最大公約數，也就是8251和6105的最大公約數.新課講解一、輾轉相除法（歐幾里得算法）1、定義： 所謂輾轉相除法，就是對于給定的兩個數，用較大的數除

3、以較小的數。若余數不為零，則將除數變被除數，余數變除數，繼續(xù)上面的除法，直到大數被小數除盡，則這時最后的除數就是原來兩個數的最大公約數。輾轉相除法是一個反復執(zhí)行直到余數等于0停止的算法 問題3你能把輾轉相除法寫成算法步驟嗎？研探新知第四步,若r=0,則m,n的最大公約數等于m;否則，返回第二步輾轉相除法求最大公約數算法步驟：第一步,給定兩個正數m,n第二步,計算m除以n所得到余數r第三步,m=n,n=r研探新知問題4:該算法的程序框圖如何表示？開始輸入m，n求m除以n的余數rm=nn=rr=0？是輸出m結束否新課講解問題5:該程序框圖對應的程序如何表述？INPUT m，nDOr=m MOD n

4、m=nn=rLOOP UNTIL r=0PRINT mEND開始輸入m，n求m除以n的余數rm=nn=rr=0？是輸出m結束否新課講解問題6:如果用當型循環(huán)結構構造算法，求兩個正整數m，n的最大公約數的程序框圖和程序分別如何表示？研探新知開始輸入m，n求m除以n的余數rm=nn0？否輸出m結束是n=rINPUT m，nWHILE n0r=m MODnm=nn=rWENDPRINT mEND九章算術更相減損術 算理：可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也，以等數約之。第一步：任意給定兩個正整數；判斷他們是否都是偶數。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較

5、大的數減較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續(xù)這個操作，直到所得的減數和差相等為止，則這個等數或這個數與約簡的數的乘積就是所求的最大公約數。研探新知2、更相減損術（1）算理：所謂更相減損術，就是對于給定的兩個數，用較大的數減去較小的數，然后將差和較小的數構成新的一對數，再用較大的數減去較小的數，反復執(zhí)行此步驟直到差數和較小的數相等，此時相等的兩數便為原來兩個數的最大公約數。研探新知例 用更相減損術求98與63的最大公約數.解：由于63不是偶數，把98和63以大數減小數，并輾轉相減， 即：986335; 633528; 35287; 28721; 21714; 1477.所

6、以，98與63的最大公約數是7。練習：用更相減損術求兩個正數84與72的最大公約數。 (12)研探新知輾轉相除法與更相減損術的比較: （1）都是求最大公約數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主;計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區(qū)別較大時計算次數的區(qū)別較明顯。（2）從結果體現(xiàn)形式來看，輾轉相除法體現(xiàn)結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到.研探新知1：用輾轉相除法求80和36的最大公約數，并用更相減損術檢驗所得結果分析：將80作為大數，36作為小數，執(zhí)行輾轉相除法和更相減損術的步驟即可解：用輾轉相除法： 803628， 36844

7、， 8420.故80和36的最大公約數是4.課堂測試2、分別用輾轉相除法和更相減損術求168與93的最大公約數. 輾轉相除法：168=931+75， 93=751+18， 75=184+3， 18=36.更相減損術:168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.課堂測試3求三個數175、100、75的最大公約數分析：求三個數的最大公約數時，可以先求出其中兩個數的最大公約數，用這個最大公約數再與第三個數求最大公約數，所得結果就是這三個數的最大公約

8、數解：(輾轉相除法)：先求175與100的最大公約數：175100175，10075125，75253.175與100的最大公約數是25.課堂測試以下再求25與75的最大公約數：7525325和75的最大公約數是25.故25是75和25的最大公約數，也就是175、100、75的最大公約數課堂測試1.(2011寧夏模擬)用輾轉相除法計算60與48的最大公約數時，需要做的除法次數是()A1B2C3 D4解析：6048112,481240.僅需要兩步運算答案：B隨堂練習2用輾轉相除法求294和84的最大公約數時，需要做除法的次數是()A1B2C3 D4解析：29484342,84422.故需做2次除

9、法答案：B隨堂練習3求378和90的最大公約數解：37890418,90185，378和90的最大公約數是18.隨堂練習4：求三個數324,243,108的最大公約數解：先求324與243的最大公約數，324243181，243813，324與243的最大公約數為81.下面再求108與81的最大公約數：1088127，81273.108與81的最大公約數是27.故324,243,108的最大公約數為27.隨堂練習 1.輾轉相除法，就是對于給定的兩個正整數，用較大的數除以較小的數，若余數不為零，則將余數和較小的數構成新的一對數，繼續(xù)上面的除法，直到大數被小數除盡為止，這時的較小的數即為原來兩個數的最大公約數. 2. 更相減損術，就是對于給定的兩個正整數，用較大的數減去較小的數，然后將差和較小的數構成新的一對數，繼續(xù)上面的減法，直到差和較小的數相等，此時相等的兩數即為原來兩個數的最大公約數.小結與作業(yè)3、輾轉相除法與更相減損術的區(qū)別（1）