1.3 算法案例課件(人教A版必修3)

1.3算法案例例：求下面兩個正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7思考：除了用這種方法外還有沒有其它方法？例：如何算出8251和6105的最大公約數(shù)？輾轉(zhuǎn)相除法與更相減損術一、輾轉(zhuǎn)相除法（歐幾里得算法）1、定義：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。

2、步驟（以求8251和6105的最大公約數(shù)的過程為例）第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。為什么呢？第二步對6105和2146重復第一步的做法

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。

完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例：用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)思考：從上面的兩個例子中可以看出計算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復S1，直到余數(shù)為0

輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于0才停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。m=n×q＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0思考：輾轉(zhuǎn)相除法中的關鍵步驟是哪種邏輯結(jié)構(gòu)？

利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)m除以較小的數(shù)n得到一個商q0和一個余數(shù)r0；(m=n×q0+r0)第二步：若r0＝0，則n為m，n的最大公約數(shù)；若r0≠0，則用除數(shù)n除以余數(shù)r0得到一個商q1和一個余數(shù)r1；(n=r0×q1+r1)第三步：若r1＝0，則r0為m，n的最大公約數(shù)；若r1≠0，則用除數(shù)r0除以余數(shù)r1得到一個商q2和一個余數(shù)r2；(r0=r1×q2+r2)……依次計算直至rn＝0，此時所得到的rn-1即為所求的最大公約數(shù)。練習1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.二.更相減損術: 我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術。 更相減損術求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母·子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。例2用更相減損術求98與63的最大公約數(shù). 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98與63的最大公約數(shù)是7。先約簡，再求21與18的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)4練習2：用更相減損術求兩個正數(shù)84與72的最大公約數(shù)。輾轉(zhuǎn)相除法與更相減損術的比較: （1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術以減法為主;計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。 （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術則以減數(shù)與差相等而得到.（1）設計求多項式當x=5時的值的算法，并寫出程序。（2）有沒有更高效的算法？能否探求更好的算法，來解決任意多項式的求解問題？三、秦九韶算法引導學生把多項式變形為：思考：從內(nèi)到外，如果把每一個括號都看成一個常數(shù)，那么變形后的式子中有哪些“一次式”？x的系數(shù)依次是什么？（3）若將x的值代入變形后的式子中，那么求值的計算過程是怎樣的？

將變形前x的系數(shù)乘以x的值，加上變形前的第2個系數(shù)，得到一個新的系數(shù)；將此系數(shù)繼續(xù)乘以x的值，再加上變形前的第3個系數(shù)，又得到一個新的系數(shù)；繼續(xù)對新系數(shù)做上面的變換，直到與變形前的最后一個系數(shù)相加，得到一個新的系數(shù)為止。這個系數(shù)即為所求多項式的值。這種算法即是“秦九韶算法”（4）用秦九韶算法求多項式的值，與多項式組成有直接關系嗎？用秦九韶算法計算上述多項式的值，需要多少次乘法運算和多少次加法運算？

計算只與多項式的系數(shù)有關，

《數(shù)書九章》——秦九韶算法

設是一個n次的多項式對該多項式按下面的方式進行改寫：思考：當知道了x的值后該如何求多項式的值？這是怎樣的一種改寫方式？最后的結(jié)果是什么？要求多項式的值，應該先算最內(nèi)層的一次多項式的值，即然后，由內(nèi)到外逐層計算一次多項式的值，即最后的一項是什么？這種將求一個n次多項式f(x)的值轉(zhuǎn)化成求n個一次多項式的值的方法，稱為秦九韶算法。思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？程序框圖：這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)。輸入ai開始輸入n,an,xi>=0?輸出v結(jié)束v=vx+aii=i-1YNi=n-1V=an秦九韶算法的特點：

通過一次式的反復計算，逐步得出高次多項式的值，對于一個n次多項式，只需做n次乘法和n次加法即可。例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.解法一:首先將原多項式改寫成如下形式: f(x)=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,當x=5時,多項式的值是2677.然后由內(nèi)向外逐層計算一次多項式的值,即練一練:用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當x=5時的值.解:原多項式先化為:

f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0

=(((((2x-5)x+0)x-4)x+3)x-6)x+0注意:n次多項式有n+1項,因此缺少哪一項應將其系數(shù)補0.v0=2v1=v0x-5=2×5-5=5v2=v1x+0=5×5+0=25v3=v2x-4=25×5-4=125-4=121v4=v3x+3=121×5+3=605+3=608v5=v4x-6=608×5-6=3040-6=3034v6=v5x+0=3034×5+0=15170+0=15170四、進位制1、什么是進位制？進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)。進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進位制，簡稱n進制。

比如：

滿二進一，就是二進制；

滿十進一，就是十進制；滿十二進一，就是十二進制；

滿六十進一，就是六十進制基數(shù)：“滿幾進一”就是幾進制，幾進制的基數(shù)就是幾.2、最常見的進位制是什么？除此之外還有哪些常見的進位制？請舉例說明．最常見的進位制應該是我們數(shù)學中的十進制,比如一般的數(shù)值計算，但是并不是生活中的每一種數(shù)字都是十進制的.古人有半斤八兩之說，就是十六進制與十進制的轉(zhuǎn)換.比如時間和角度的單位用六十進位制,計算“一打”數(shù)值時是12進制的。電子計算機用的是二進制。式中1處在百位，第一個3所在十位，第二個3所在個位，5和9分別處在十分位和百分位。十進制數(shù)是逢十進一的。

我們最常用最熟悉的就是十進制數(shù)，它的數(shù)值部分是十個不同的數(shù)字符號0，1，2，3，4，5，6，7，8，9來表示的。十進制：例如133.59，它可用一個多項式來表示：133.59=1*102+3*101+3*100+5*10-1+9*10-2實際上，十進制數(shù)只是計數(shù)法中的一種，但它不是唯一記數(shù)法。除了十進制數(shù)，生產(chǎn)生活中還會遇到非十進制的記數(shù)制。如時間：60秒為1分，60分為1小時，它是六十進制的。兩根筷子一雙，兩只手套為一副，它們是二進制的。其它進制：二進制、七進制、八進制、十二進制、六十進制……二進制只有0和1兩個數(shù)字，七進制用0~6七個數(shù)字十六進制有0~9十個數(shù)字及ABCDEF六個字母.

為了區(qū)分不同的進位制，常在數(shù)的右下角標明基數(shù)，十進制一般不標注基數(shù).例如十進制的133.59，寫成133.59(10)七進制的13，寫成13(7)；二進制的10，寫成10(2)一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進制可以表示為一串數(shù)字連寫在一起的形式：十進制的構(gòu)成十進制由兩個部分構(gòu)成例如：3721其它進位制的數(shù)又是如何的呢？第一、它有0～9十個數(shù)字；第二、它有“數(shù)位”，即從右往左為個位、十位、百位、千位等等。(用10個數(shù)字來記數(shù)，稱基數(shù)為10)表示有：1個1，2個十，7個百即7個10的平方，3個千即3個10的立方十進制：“滿十進一”其它進制數(shù)化成十進制數(shù)公式二進制二進制是用0、1兩個數(shù)字來描述的．如11001二進制的表示方法區(qū)分的寫法：11001（2）或者(11001)2八進制呢？如7342(8)k進制呢？anan-1an-2…a1(k)？二進制與十進制的轉(zhuǎn)換1、二進制數(shù)轉(zhuǎn)化為十進制數(shù)例1：將二進制數(shù)110011(2)化成十進制數(shù)。解：根據(jù)進位制的定義可知所以，110011（2）=51．例2、設計一個算法，將k進制數(shù)a(共有n位)轉(zhuǎn)換為十進制數(shù)b。(1)算法步驟:第一步，輸入a,k和n的值；第二步，將b的值初始化為0,i的值初始化為1；第三步，b=b+ai*ki-1,i=i+1第四步，判斷i>n是否成立.若是,則執(zhí)行第五步,否則,返回第三步；第五步，輸出b的值.

練一練把三進制數(shù)10221(3)化為十進制數(shù)解:10221(3)

=1×34+0×33+2×32+2×31+1×30=81+18+6+1=106.

方法：除2取余法，即用2連續(xù)去除89或所得的商，然后取余數(shù)。例、把89化為二進制數(shù)解：根據(jù)“逢二進一”的原則，有89＝2×44＋1＝2×

(2×22＋0)+1＝2×(2×(2×11＋0)+0)+1＝2×(2×(2×

(2×5＋1)+0)+0)+15＝2×2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1＝2×（2×（24＋22＋2＋0）＋0）＋1＝2×（25＋23+22＋0＋0）＋1＝26＋2