算法案例1 詳細(xì)版課件

1、1.3 算法案例 第一課時(shí) 輾轉(zhuǎn)相除法與更相減損術(shù)例：求下面兩個(gè)正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7思考1：求兩整數(shù)60和84的最大公約數(shù)602308442所以，60和84的最大公約數(shù)為223=12思考：除了用這種方法外還有沒(méi)有其它方法？問(wèn)：如何算出101和148的最大公約數(shù)？22115375問(wèn)：如何算出8251和6105的最大公約數(shù)？思考2:對(duì)于8251與6105這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難. 注意: 82

2、51=61051+2146 結(jié)論：因?yàn)楣s數(shù)相同，所以最大公約數(shù)也相同。2146=18131+333，148=374 + 0.333=1482+37，1813=3335+148，8251=61051+2146，6105=21462+1813，得到：8251與6105最大公約數(shù)就是37.輾轉(zhuǎn)相除法 完整的過(guò)程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0練習(xí)1： 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225和135的最大公約數(shù)是45 思考1：從上面的兩個(gè)運(yùn)算過(guò)程中可以看出計(jì)算的規(guī)律是

3、什么？ 步驟1：用大數(shù)除以小數(shù)步驟2：除數(shù)變成被除數(shù)，余 數(shù)變成除數(shù)步驟3：重復(fù)步驟1，直到余 數(shù)為0 上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱(chēng)為輾轉(zhuǎn)相除法或歐幾里得算法. 第一步，給定兩個(gè)正整數(shù)m，n(mn).第二步，計(jì)算m除以n所得的余數(shù)r. 第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約 數(shù)等于m；否則，返回第二步. 其算法步驟如何設(shè)計(jì)？開(kāi)始輸入m，n求m除以n的余數(shù)rm=nn=r r=0？是輸出m結(jié)束否該算法的程序框圖如何表示？該程序框圖對(duì)應(yīng)的程序如何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND開(kāi)始輸入m，n求m除

4、以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否思考：如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m，n的最大公約數(shù)的程序框圖和程序分別如何表示？開(kāi)始輸入m，n求m除以n的余數(shù)rm=nn0？否輸出m結(jié)束是n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND練習(xí)2：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù). (53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.二、更相減損術(shù) 可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給

5、定兩個(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ù)：知識(shí)探究（二）:更相減損術(shù) 思考1:設(shè)兩個(gè)正整數(shù)mn，若m-n=k，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等.反復(fù)利用這個(gè)原理，可求得98與63的最大公約數(shù)為多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，(1)、算法步驟第一步：給定兩個(gè)

6、正整數(shù)a,b,不妨設(shè)ab.第二步,若a,b都是偶數(shù)則不斷用2約簡(jiǎn)，使它們不同時(shí)是偶數(shù)，約簡(jiǎn)后的兩個(gè)數(shù)仍記為a,b.第三步：d=a-b.第四步：判斷“db”是否成立。若是, 則將b,d中的較大者記為a,較小者記為b,返回第三步；否則, 2kd(k是約簡(jiǎn)整數(shù)的2的個(gè)數(shù)）為所求的最大公約數(shù).思考：你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？開(kāi)始輸入a,b輸出a2i結(jié)束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tba?a MOD 2=0且b MOD 2=0?YNNNYi=0i=i+1INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD

7、2=0 a=a/2 b=b/2 i=i+1 WENDDOIF ba THEN t=a a=b b=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND理論遷移 例1 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù). 輾轉(zhuǎn)相除法 168=931+75 93=751+18， 75=184+3， 18=36.所以168與93的最大公約數(shù)是3.更相減損術(shù): 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.所以168與93的最大公約數(shù)是3.168-93=75， 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ù). 課堂小結(jié) 2. 更相減損術(shù)，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時(shí)相等的兩數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù). 例2 求325，130，270