新課標(biāo)人教A版高中數(shù)學(xué)必修三1.3.1算法案例課件

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

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

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

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

5、大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。研探新知2、更相減損術(shù)（1）算理：所謂更相減損術(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)相減， 即：986335; 633528; 35287; 28721; 21714; 1477.所

6、以，98與63的最大公約數(shù)是7。練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。 (12)研探新知輾轉(zhuǎn)相除法與更相減損術(shù)的比較: （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ù)與差相等而得到.研探新知1：用輾轉(zhuǎn)相除法求80和36的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)所得結(jié)果分析：將80作為大數(shù)，36作為小數(shù)，執(zhí)行輾轉(zhuǎn)相除法和更相減損術(shù)的步驟即可解：用輾轉(zhuǎn)相除法： 803628， 36844

7、， 8420.故80和36的最大公約數(shù)是4.課堂測(cè)試2、分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù). 輾轉(zhuǎn)相除法：168=931+75， 93=751+18， 75=184+3， 18=36.更相減損術(shù):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.課堂測(cè)試3求三個(gè)數(shù)175、100、75的最大公約數(shù)分析：求三個(gè)數(shù)的最大公約數(shù)時(shí)，可以先求出其中兩個(gè)數(shù)的最大公約數(shù)，用這個(gè)最大公約數(shù)再與第三個(gè)數(shù)求最大公約數(shù)，所得結(jié)果就是這三個(gè)數(shù)的最大公約

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

9、法答案：B隨堂練習(xí)3求378和90的最大公約數(shù)解：37890418,90185，378和90的最大公約數(shù)是18.隨堂練習(xí)4：求三個(gè)數(shù)324,243,108的最大公約數(shù)解：先求324與243的最大公約數(shù)，324243181，243813，324與243的最大公約數(shù)為81.下面再求108與81的最大公約數(shù)：1088127，81273.108與81的最大公約數(shù)是27.故324,243,108的最大公約數(shù)為27.隨堂練習(xí) 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. 更相減損術(shù)，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時(shí)相等的兩數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù).小結(jié)與作業(yè)3、輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）