算法案例 省賽獲獎 完整版PPT

1、算法案例（第一課時）1、求兩個正整數(shù)的最大公約數(shù)（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）55357所以，25和35的最大公約數(shù)為549（2）77639所以，49和63的最大公約數(shù)為72、求8251和6105的最大公約數(shù) 輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程 第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論： 6105和2146的公約數(shù)就是8251和6105的公約，求8251和6105的最大公約數(shù)，只要求出6105和2146的最大公約數(shù)就可以了。第二步 對6105和2146重復(fù)第一步的做

2、法6105=21462+1813同理2146和1813的最大公約數(shù)也是6105和2146的最大公約數(shù)。 思考：從上述的過程你體會到了什么？為什么呢？ 完整的過程 8251=61051+21466105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù) 225=1351+90135=901+4590=452+0顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù) 思考1：從上面的兩個例子可以看出計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)S2：除數(shù)

3、變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0例2 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù) 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r輾轉(zhuǎn)相除除法的程序框圖與程序開始輸入m,n r=mMODn m=nn=r否是r=0？輸出m結(jié)束 INPUT m,n DO r=

4、mMODn m=n n=r LOOP UNTIL r=0 PRINT m END九章算術(shù)更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。例3 用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減3528728721217149863356335281477所以，98和6

5、3的最大公約數(shù)等于7 練習(xí)：課本P45練習(xí)第1題計算多項式（） =當(dāng)x = 5的值算法1：因為（） =1所以（5）=555551=3125625125255= 3906算法2：（5）=555551=5（5555） 1=5（5（555 ） ） 1 =5（5（ 5 （55 ） ） ）=5（5（ 5 （5 （5 ） ） ） ） 1分析：兩種算法中各用了幾次乘法運算？和幾次加法運算？引題：秦九韶算法算法1用了10次乘法，5次加法算法1用了5次乘法，5次加法數(shù)書九章秦九韶算法設(shè)是一個n次的多項式對該多項式按下面的方式進(jìn)行改寫：思考：當(dāng)知道了x的值后該如何求多項式的值？這是怎樣的一種改寫方式？最后的結(jié)果是什么？要求多項式的值，應(yīng)該先算最內(nèi)層的一次多項式的值，即然后，由內(nèi)到外逐層計算一次多項式的值，即最后的一項是什么？這種將求一個n次多項式f（x）的值轉(zhuǎn)化成求n個一次多項式的值的方法，稱為秦九韶算法。思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？例2 已知一個五次多項式為用秦九韶算法求這個多項式當(dāng)x = 5的值。解：將多項式變形：按由里到外的順序，依此計算一次多項式當(dāng)x = 5時的值：所以，當(dāng)x = 5時，多項式的值等于17255.2你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？i=1v=anv= v x0 +an-ii=i+1in?否是輸