必修三算法案例課件

1、1. 回顧算法的三種表示方法：回顧算法的三種表示方法：（1）、自然語言）、自然語言（2）、程序框圖）、程序框圖（3）、程序語言）、程序語言（三種邏輯結構）（三種邏輯結構）（五種基本語句（五種基本語句）復習引入2. 思考：思考：小學學過的求兩個數(shù)的最大公約數(shù)的方法？小學學過的求兩個數(shù)的最大公約數(shù)的方法？ 先用兩個公有的質因數(shù)連續(xù)去除，先用兩個公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止，然后一直除到所得的商是互質數(shù)為止，然后把所有的除數(shù)連乘起來把所有的除數(shù)連乘起來.例：求下面兩個正整數(shù)的最大公約數(shù)例：求下面兩個正整數(shù)的最大公約數(shù)：（1）求）求25和和35的最大公約數(shù)的最大公約數(shù)（2）求）求

2、49和和63的最大公約數(shù)的最大公約數(shù)25（1）5535749（2）77639所以，所以，25和和35的最的最大公約數(shù)為大公約數(shù)為5所以，所以，49和和63的最的最大公約數(shù)為大公約數(shù)為7例：如何算出例：如何算出8251和和6105的最大公約數(shù)？的最大公約數(shù)？新課講解：新課講解：一、輾轉相除法（歐幾里得算法）一、輾轉相除法（歐幾里得算法）1、定義：、定義： 所謂輾轉相除法，就是對于給定的所謂輾轉相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構成余數(shù)不為零，則將余數(shù)和較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的除法，直到大新的一對數(shù)，繼

3、續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。來兩個數(shù)的最大公約數(shù)。 2、步驟、步驟:（以求（以求8251和和6105的最大公約數(shù)的過的最大公約數(shù)的過程為例）程為例）第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)商和余數(shù):8251=61051+2146結論：結論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求8251和和6105的最大公約數(shù)，只要的最大公約數(shù)，只要求出求出6105和和2146的最大公約數(shù)就可以了。的最大公約數(shù)就可以了。第二步第二

4、步 對對6105和和2146重復第一步的做法重復第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過程完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0顯然顯然37是是148和和37的最大公的最大公約數(shù)，也約數(shù)，也就是就是8251和和6105的的最大公約最大公約數(shù)數(shù) 例：例： 用輾轉相除法求用輾轉相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351+90135

5、=901+4590=452顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最的最大公約數(shù)大公約數(shù) 思考思考1：從上面的兩個例子中可以看出計算的規(guī)：從上面的兩個例子中可以看出計算的規(guī)律是什么？律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復：重復S1，直到余數(shù)為，直到余數(shù)為0 輾轉相除法是一個反復執(zhí)行直到余數(shù)等于輾轉相除法是一個反復執(zhí)行直到余數(shù)等于0才停才停止的步驟，這實際上是一個循環(huán)結構。止的步驟，這實際上是一個循環(huán)結構。8251=61051+2146 6105=21462+1813

6、 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否思考：你能把輾轉相除法編成一個計算機程序嗎？(1)(1)、算法步驟：、算法步驟：第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)m,n(mn).第二步：計算第二步：計算m除以除以n所得的余數(shù)所得的余數(shù)r.第三步：第三步：m=n,n=r.第四步：若第四步：若r0,則則m,n的最大公約數(shù)等于的最大公約數(shù)等于m； 否則，返回第二步否則，返回第二步. 第五步：輸出最大公約數(shù)第五步：輸出最大公約

7、數(shù)m.(2)(2)、程序框圖：、程序框圖：開始開始輸入輸入m,n r=m MOD n m=nr=0?是是否否 n=r 輸出輸出m結束結束(3)(3)、程序：、程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND思考思考:你能用當型循環(huán)結構構造算法，求兩個正整你能用當型循環(huán)結構構造算法，求兩個正整數(shù)的最大公約數(shù)嗎？寫出算法步驟、程序框圖和程數(shù)的最大公約數(shù)嗎？寫出算法步驟、程序框圖和程序序。開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結束結束是是n=rINPUT mINPUT m，n nWHILEWHIL

8、E n n0 0r=m r=m MODnMODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND二、更相減損術二、更相減損術 可半者半之，不可半者，副置分母、子之數(shù)，以少可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。減多，更相減損，求其等也，以等數(shù)約之。第一步：第一步：任意給定兩個正整數(shù)；判斷他們是否都是任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。約簡；若不是則執(zhí)行第二步。第二步：第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較

9、，并以大數(shù)減小數(shù)。繼續(xù)這個操差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)和差相等為止，則這個等數(shù)或這作，直到所得的數(shù)和差相等為止，則這個等數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。（1）、）、九章算術九章算術中的更相減損術：中的更相減損術：1、背景介紹：、背景介紹：（2）、現(xiàn)代數(shù)學中的更相減損術：）、現(xiàn)代數(shù)學中的更相減損術：2、定義：、定義： 所謂更相減損術，就是對于給定的兩個所謂更相減損術，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構成新的一對數(shù)，再用較大的數(shù)減較小的數(shù)

10、構成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。數(shù)的最大公約數(shù)。例例: : 用更相減損術求用更相減損術求9898與與6363的最大公約數(shù)的最大公約數(shù). .解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小以大數(shù)減小數(shù)，并輾轉相減數(shù)，并輾轉相減 989863633535636335352828353528287 728287 7212121217 71 14 414147 77 7所以，所以，9898和和6363的最大公

11、約數(shù)等于的最大公約數(shù)等于7 7 3、方法：、方法：1、用更相減損術求兩個正數(shù)、用更相減損術求兩個正數(shù)84與與72的最大公約數(shù)的最大公約數(shù) 練習：練習：思路分析：先約簡，再求思路分析：先約簡，再求21與與18的最大公約數(shù)的最大公約數(shù),然后乘以兩次約簡的質因數(shù)然后乘以兩次約簡的質因數(shù)4。2、求、求324、243、135這三個數(shù)的最大公約數(shù)。這三個數(shù)的最大公約數(shù)。思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。數(shù)的最大公約數(shù)即為所求。2、求、求324

12、、243、135這三個數(shù)的最大公約數(shù)這三個數(shù)的最大公約數(shù).27135243324.2713581, 022754,2715481,54181135.812433240381243811243324的最大公約數(shù)為、所以，三個數(shù)的最大公約數(shù)為與則又的最大公約數(shù)為與則2、求、求324、243、135這三個數(shù)的最大公約數(shù)這三個數(shù)的最大公約數(shù).27135243324.2713581,272754,275481,5481135.81243324,8181162,16281243,81243324最大公約數(shù)為、所以，三個數(shù)的最大公約數(shù)為與則的最大公約數(shù)為與則(1)、算法步驟、算法步驟第一步：輸入兩個正整數(shù)第

13、一步：輸入兩個正整數(shù)m,n(mn);第二步：若第二步：若m不等于不等于n ,則執(zhí)行第三步；否則則執(zhí)行第三步；否則轉到第五步；轉到第五步；第三步：把第三步：把m-n的差賦予的差賦予r;第四步：如果第四步：如果nr, 那么把那么把n賦給賦給m,把把r賦給賦給n;否則把否則把r賦給賦給m，執(zhí)行第二步；，執(zhí)行第二步；第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)n.*思考：你能根據(jù)更相減損術設計程序，求兩個正整數(shù)的最大公約數(shù)嗎？(2)(2)、程序框圖、程序框圖是是否否是是開始開始輸入輸入m,nmn?否否 輸出輸出n結束結束 n=rm=nr=m-nrn?m=r(3)(3)、程序、程序INPUT “m,n=

14、;m,nWHILE mn r=m-n IF nr THEN m=n n=r ELSE m=r END IFWENDPRINT nEND比較輾轉相除法與更相減損術的區(qū)別比較輾轉相除法與更相減損術的區(qū)別（1 1）都是求最大公約數(shù)的方法，計算上輾轉相除）都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數(shù)法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計算次數(shù)相對較少，特別當兩個數(shù)字上輾轉相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2 2）從結果體現(xiàn)形式來看，輾轉相除法體現(xiàn)結果）從結果體現(xiàn)形式來

15、看，輾轉相除法體現(xiàn)結果是以相除余數(shù)為是以相除余數(shù)為0 0則得到，而更相減損術則以減數(shù)與則得到，而更相減損術則以減數(shù)與差相等而得到。差相等而得到。小結小結1、求兩個數(shù)的最大公約數(shù)的兩種方法分別是、求兩個數(shù)的最大公約數(shù)的兩種方法分別是（ ）和（）和（ ）。）。2、兩個數(shù)、兩個數(shù)21672，8127的最大公約數(shù)是的最大公約數(shù)是 （ ）A、2709 B、2606 C、2703 D、2706怎樣求多項式怎樣求多項式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1當當x=5x=5時的值呢？時的值呢？計算多項式計算多項式() =當當x = 5的值的值算法算法1：因為因

16、為() =所以所以(5)=55555=3125625125255= 3906算法算法2：(5)=55555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +算法算法1：因為因為() =所以所以(5)=55555=3125625125255= 3906算法算法2：(5)=55555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +共做了共做了1+2+3+4=10次乘法運算，次乘法運算，5次加法運算。次加法運算。共做了共

17、做了4次乘法運算，次乘法運算，5次加法運算。次加法運算。數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn設設)(xf是一個是一個n 次的多項式次的多項式對該多項式按下面的方式進行改寫：對該多項式按下面的方式進行改寫：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn這是怎樣的一種改寫方式？最后的結果是什么？0121)()(axaxaxaxaxfnnn要求多項式的值，應該先算最內層的一次多項式的值，即要求多項式的值，應該先算最內層的一次多項式的值，即11nnaxav然后

18、，由內到外逐層計算一次多項式的值，即然后，由內到外逐層計算一次多項式的值，即212naxvv323naxvv01axvvnn最后的一最后的一項是什么項是什么？這種將求一個這種將求一個n次多項式次多項式f(x)的值轉化成求的值轉化成求n個一個一次多項式的值的方法，稱為次多項式的值的方法，稱為秦九韶算法秦九韶算法。算法步驟算法步驟：第一步：輸入多項式次數(shù)第一步：輸入多項式次數(shù)n、最高次項的系數(shù)、最高次項的系數(shù)an和和x的值的值.第二步：將第二步：將v的值初始化為的值初始化為an，將，將i的值初始化為的值初始化為n-1.第三步：輸入第三步：輸入i次項的系數(shù)次項的系數(shù)ai第四步：第四步：v=vx+ai

19、,i=i-1.第五步：判斷第五步：判斷i是否小于或等于是否小于或等于0，若是，則返回第，若是，則返回第三步；否則，輸出多項式的值三步；否則，輸出多項式的值v。程序框圖：程序框圖：這是一個在這是一個在秦九韶算法秦九韶算法中反復執(zhí)行的步驟，因中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn)此可用循環(huán)結構來實現(xiàn)。 ),(nkaxvvavknkkn2110輸入輸入ai開始開始輸入輸入n,an,xi 0?輸出輸出v結束結束v=vx+aii=i-1YNi=n-1V=an輸入輸入ai開始開始輸入輸入n,an,xi 0?輸出輸出v結束結束v=vx+aii=i-1YNi=n-1V=anINPUT n=;nINPUT a

20、n=;aINPUT x=;xv=ai=n-1WHILE i=0 PRINT i=;i INPUT ai=;a v=v*x+a i=i-1WENDPRINT vEND程序程序特點：特點：通過一次式的反復計算，逐步得出高次多通過一次式的反復計算，逐步得出高次多項式的值，對于一個項式的值，對于一個n次多項式，只需做次多項式，只需做n次乘次乘法和法和n次加法即可。次加法即可。例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當當x=5時的值時的值.解法一解法一:首先將原多項式改寫成如下形式首先將原多項式改寫成如下形式 : f(x)=(2x-5)x-4)

21、x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,當當x=5時時,多多項式的值是項式的值是2677.然后由內向外逐層計算一次多項式的值然后由內向外逐層計算一次多項式的值,即即2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,當當x=5時時,多項式的值是多項式的值是2677.原多項式原多項式的系數(shù)的系數(shù)多項式多項式的值的值.例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)

22、=2x5-5x4-4x3+3x2-6x+7當當x=5時的值時的值.解法二解法二:列表列表22 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,當當x=5時時,多項式的值是多項式的值是15170.練一練練一練:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當當x=5時的值時的值.解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:n次多項式有次多項式有n+1項項,因此缺少哪一項因此缺少哪一項應將其系數(shù)補應將其系數(shù)補

23、0.例例2 已知一個五次多項式為已知一個五次多項式為8 . 07 . 16 . 25 . 324)(2345xxxxxxf用秦九韶算法求這個多項式當用秦九韶算法求這個多項式當x = 5的值。的值。解：解：將多項式變形：將多項式變形：8 . 0)7 . 1)6 . 2)5 . 3)24()(xxxxxxf按由里到外的順序，依此計算一次多項式當按由里到外的順序，依此計算一次多項式當x = 5時的值：時的值：222541v40v5 .1135 . 35222v9 .5646 . 255 .1133v2 .28267 . 159 .5644v2 .141308 . 052 .28265v所以，當所以，

24、當x = 5時，多項式的值等于時，多項式的值等于14130.2你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？程序框圖：程序框圖：開始輸入f(x)的系數(shù)：a0,a1,a2,a3,a4a5輸入x0n5?輸出v結束v=vx0+a5-nn=n+1YN n=1 v=a5 ),(nkaxvvavknkkn2110這是一個在這是一個在秦九韶算法秦九韶算法中反復執(zhí)行的步驟，因中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn)此可用循環(huán)結構來實現(xiàn)。練習、已知多項式練習、已知多項式f(x)=x5+5x4+10 x3+10 x2+5x+1用用秦九韶算法求這個多項式當秦九韶算法求這個多項式當x=-2時的值。時的值。課堂小結：

25、課堂小結：1、秦九韶算法的方法和步驟、秦九韶算法的方法和步驟2、秦九韶算法的程序框圖、秦九韶算法的程序框圖 問題問題11我們常見的數(shù)字都是十進制的我們常見的數(shù)字都是十進制的, ,但是并不是生活中的每一種數(shù)字都是十進制的但是并不是生活中的每一種數(shù)字都是十進制的. .比如時間和角度的單位用六十進位制比如時間和角度的單位用六十進位制, ,電子計電子計算機用的是二進制算機用的是二進制. .那么什么是進位制那么什么是進位制? ?不同的不同的進位制之間又有什么聯(lián)系呢進位制之間又有什么聯(lián)系呢? ?進位制是人們?yōu)榱擞嫈?shù)和運算的方便而進位制是人們?yōu)榱擞嫈?shù)和運算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進一約定的一種記

26、數(shù)系統(tǒng)，約定滿二進一, ,就是二就是二進制進制; ;滿十進一滿十進一, ,就是十進制就是十進制; ;滿十六進一滿十六進一, ,就就是十六進制是十六進制; ;等等等等. . “滿幾進一滿幾進一”,就是幾進制就是幾進制,幾進制的幾進制的基數(shù)基數(shù)就是幾就是幾.可使用數(shù)字符號的個數(shù)稱為基數(shù)可使用數(shù)字符號的個數(shù)稱為基數(shù). .基數(shù)基數(shù)都是大于都是大于1 1的整數(shù)的整數(shù). . 如二進制可使用的數(shù)字有如二進制可使用的數(shù)字有0和和1,基數(shù)是基數(shù)是2; 十進制可使用的數(shù)字有十進制可使用的數(shù)字有0,1,2,8,9等十個等十個數(shù)字數(shù)字,基數(shù)是基數(shù)是10; 十六進制可使用的數(shù)字或符號有十六進制可使用的數(shù)字或符號有09等

27、等10個數(shù)字以及個數(shù)字以及AF等等6個字母個字母(規(guī)定字母規(guī)定字母AF對應對應1015),十六進制的基數(shù)是十六進制的基數(shù)是16.注意注意: :為了區(qū)分不同的進位制為了區(qū)分不同的進位制, ,常在數(shù)字常在數(shù)字的右下腳標明基數(shù)的右下腳標明基數(shù). . 如如111001111001(2)(2)表示二進制數(shù)表示二進制數(shù),34,34(5)(5)表示表示5 5進制數(shù)進制數(shù). .十進制數(shù)一般不標注基數(shù)十進制數(shù)一般不標注基數(shù).問題問題2十進制數(shù)十進制數(shù)3721中的中的3表示表示3個千個千,7表示表示7個百個百,2表示表示2個十個十,1表示表示1個一個一,從而它可以寫成從而它可以寫成下面的形式下面的形式:3721=

28、3103+7102+2101+1100.想一想二進制數(shù)想一想二進制數(shù)1011(2)可以類似的寫成什可以類似的寫成什么形式么形式?1011(2)=123+022+121+120.同理同理:3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162+1161+6160一般地一般地,若若k是一個大于是一個大于1的整數(shù)的整數(shù),那么以那么以k為為基數(shù)的基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一進制數(shù)可以表示為一串數(shù)字連寫在一起的形式起的形式anan-1a1a0(k) (0ank,0an-1,a1,a0n?否否是是輸出輸出b結束結束INPUT a,k,ni=1b=0

29、DOb=b+t*k(i-1)i=i+1LOOP UNTIL inPRINT bENDt=a MOD 10a=a10t=a MOD 10例例3:把把89化為二進制的數(shù)化為二進制的數(shù).分析分析:把把89化為二進制的數(shù)化為二進制的數(shù),需想辦法將需想辦法將89先寫成如下形式先寫成如下形式89=an2n+an-12n-1+a121+a020 .89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).但如果數(shù)太大但如果數(shù)太大,我們是無法這樣湊出來的我們是無法這樣湊出來的,怎么辦怎么辦?89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 2=12+0, 1=02+1, 89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1=126+025+124+123+022+021+120=1011001(2).可以用可