人教a版必修三：《1.3算法案例》ppt課件(2)

1、第一章第一章 算法初步算法初步 1.3 1.3 算法案例算法案例例：求下面兩個(gè)正整數(shù)的最大公約數(shù)：例：求下面兩個(gè)正整數(shù)的最大公約數(shù)：（1）求）求25和和35的最大公約數(shù)的最大公約數(shù)（2）求）求49和和63的最大公約數(shù)的最大公約數(shù)25（1） 5535749（2） 77639所以，所以，25和和35的最大公的最大公約數(shù)為約數(shù)為5所以，所以，49和和63的最大公的最大公約數(shù)為約數(shù)為7思考：除了用這種方法外還有沒有其它方法？思考：除了用這種方法外還有沒有其它方法？例：如何算出例：如何算出8251和和6105的最大公約數(shù)？的最大公約數(shù)？輾轉(zhuǎn)相除法與更相減損術(shù)一、輾轉(zhuǎn)相除法（歐幾里得算法）一、輾轉(zhuǎn)相除法（

2、歐幾里得算法）1、定義：、定義：所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)。最大公約數(shù)。 2、步驟、步驟（以求（以求8251和和6105的最大公約數(shù)的過程為例）的最大公約數(shù)的過程為例）第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余

3、數(shù)8251=61051+2146結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求8251和和6105的最大公約數(shù)，的最大公約數(shù)，只要求出只要求出6105和和2146的公約數(shù)就可以了。的公約數(shù)就可以了。第二步第二步 對(duì)對(duì)6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過程完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+14

4、8333=1482+37148=374+0例：例： 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351+90135=901+4590=452顯然顯然37是是148和和37的最大的最大公約數(shù)，也就是公約數(shù)，也就是8251和和6105的最大公約數(shù)的最大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，的最大公約數(shù)，也就是也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考：從上面的兩個(gè)例子中可思考：從上面的兩個(gè)例子中可以看出計(jì)算的規(guī)律是什么？以看出計(jì)算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)變成除

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

6、?是是否否 n=r 輸出輸出m結(jié)束結(jié)束思考：你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？程序：程序：INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND1.定義：定義：所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公

7、約數(shù)。便為原來兩個(gè)數(shù)的最大公約數(shù)。二、更相減損術(shù)二、更相減損術(shù)2、方法：、方法：例例: : 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). .解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公約數(shù)等于的最大公約數(shù)等于7 7 INPUT m, nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD

8、2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WENDd=m-nWHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-nWENDd=2 k*dPRINT dEND思考：你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？（1）設(shè)計(jì)求多項(xiàng)式）設(shè)計(jì)求多項(xiàng)式763452)(2345xxxxxxf當(dāng)當(dāng)x=5時(shí)的值的算法，并寫出程序。時(shí)的值的算法，并寫出程序。（2）有沒有更高效的算法？能否探求更好的算法，來解決任意多項(xiàng)式的）有沒有更高效的算法？能否探求更好的算法，來解決任意多項(xiàng)式的求解問題？求解問題？引導(dǎo)學(xué)生把多項(xiàng)式變形為：引導(dǎo)學(xué)生把

9、多項(xiàng)式變形為：7)6) 3)4)52(763452)(2345xxxxxxxxxxxf思考：從內(nèi)到外，如果把每一個(gè)括號(hào)都看成一個(gè)常數(shù)，那么變形思考：從內(nèi)到外，如果把每一個(gè)括號(hào)都看成一個(gè)常數(shù)，那么變形后的式子中有哪些后的式子中有哪些“一次式一次式”？x的系數(shù)依次是什么？的系數(shù)依次是什么？（3）若將）若將x的值代入變形后的式子中，那么求值的計(jì)算過程是怎樣的值代入變形后的式子中，那么求值的計(jì)算過程是怎樣的？的？ 將變形前將變形前x的系數(shù)乘以的系數(shù)乘以x的值，加上變形前的第的值，加上變形前的第2個(gè)系數(shù)，得到一個(gè)新個(gè)系數(shù)，得到一個(gè)新的系數(shù)；將此系數(shù)繼續(xù)乘以的系數(shù)；將此系數(shù)繼續(xù)乘以x的值，再加上變形前的第

10、的值，再加上變形前的第3個(gè)系數(shù)，又得到一個(gè)系數(shù)，又得到一個(gè)新的系數(shù)；繼續(xù)對(duì)新系數(shù)做上面的變換，直到與變形前的最后一個(gè)系數(shù)個(gè)新的系數(shù)；繼續(xù)對(duì)新系數(shù)做上面的變換，直到與變形前的最后一個(gè)系數(shù)相加，得到一個(gè)新的系數(shù)為止。這個(gè)系數(shù)即為所求多項(xiàng)式的值。這種算法相加，得到一個(gè)新的系數(shù)為止。這個(gè)系數(shù)即為所求多項(xiàng)式的值。這種算法即是即是“秦九韶算法秦九韶算法” （4）用秦九韶算法求多項(xiàng)式的值，與多項(xiàng)式組成有直接關(guān)）用秦九韶算法求多項(xiàng)式的值，與多項(xiàng)式組成有直接關(guān)系嗎？用秦九韶算法計(jì)算上述多項(xiàng)式的值，需要多少次乘系嗎？用秦九韶算法計(jì)算上述多項(xiàng)式的值，需要多少次乘法運(yùn)算和多少次加法運(yùn)算法運(yùn)算和多少次加法運(yùn)算？ 數(shù)書九

11、章數(shù)書九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn設(shè)設(shè))(xf是一個(gè)是一個(gè)n 次的多項(xiàng)式次的多項(xiàng)式對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn這是怎樣的一種改寫方式？最后的結(jié)果是什么？0121)()(axaxaxaxaxfnnn要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即11nnaxav然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即然后，由內(nèi)到外逐層計(jì)算一次

12、多項(xiàng)式的值，即212naxvv323naxvv01axvvnn最后的一最后的一項(xiàng)是什么？項(xiàng)是什么？這種將求一個(gè)這種將求一個(gè)n次多項(xiàng)式次多項(xiàng)式f(x)的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n個(gè)一個(gè)一次多項(xiàng)式的值的方法，稱為次多項(xiàng)式的值的方法，稱為秦九韶算法秦九韶算法。程序框圖：程序框圖：這是一個(gè)在這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。輸入輸入ai開始開始輸入輸入n,an,xi=0?輸出輸出v結(jié)束結(jié)束v=vx+aii=i-1YNi=n-1V=an ),(nkaxvvavknkkn2110秦九韶算法的特點(diǎn)：秦九韶算法的特點(diǎn)： 通過一次式的

13、反復(fù)計(jì)算，逐步得出通過一次式的反復(fù)計(jì)算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)高次多項(xiàng)式的值，對(duì)于一個(gè)n次多項(xiàng)式，次多項(xiàng)式，只需做只需做n次乘法和次乘法和n次加法即可。次加法即可。程序：程序：INPUT “n=”；nINPUT “an=“;aINPUT “x=“;xv=ai=n-1WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND1 1、什么是進(jìn)位制？、什么是進(jìn)位制？進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)。進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)。進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位進(jìn)位制是一種記數(shù)方

14、式，用有限的數(shù)字在不同的位置表示不同的數(shù)值。可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為數(shù)，基數(shù)為n n，即可稱，即可稱n n進(jìn)位制，簡(jiǎn)稱進(jìn)位制，簡(jiǎn)稱n n進(jìn)制。進(jìn)制。 比如：比如： 滿二進(jìn)一，就是二進(jìn)制；滿二進(jìn)一，就是二進(jìn)制； 滿十進(jìn)一，就是十進(jìn)制；滿十進(jìn)一，就是十進(jìn)制； 滿十二進(jìn)一，就是十二進(jìn)制；滿十二進(jìn)一，就是十二進(jìn)制； 滿六十進(jìn)一，就是六十進(jìn)制滿六十進(jìn)一，就是六十進(jìn)制基數(shù)：基數(shù)：“滿幾進(jìn)一滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾. .2 2、最常見的進(jìn)位制是什么？除此之外還有哪些常見、最常見的進(jìn)位制是什么？除此之外還有哪

15、些常見的進(jìn)位制？請(qǐng)舉例說明的進(jìn)位制？請(qǐng)舉例說明 最常見的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的十進(jìn)制最常見的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的十進(jìn)制, ,比如比如一般的數(shù)值計(jì)算，但是并不是生活中的每一種數(shù)一般的數(shù)值計(jì)算，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的字都是十進(jìn)制的. . 古人有古人有半斤八兩半斤八兩之說，就是十六進(jìn)制與十進(jìn)制的之說，就是十六進(jìn)制與十進(jìn)制的轉(zhuǎn)換轉(zhuǎn)換. . 比如時(shí)間和角度的單位用六十進(jìn)位制比如時(shí)間和角度的單位用六十進(jìn)位制, , 計(jì)算計(jì)算“一一打打”數(shù)值時(shí)是數(shù)值時(shí)是1212進(jìn)制的。進(jìn)制的。 電子計(jì)算機(jī)用的是二進(jìn)制電子計(jì)算機(jī)用的是二進(jìn)制 。 式中式中1 1處在百位，第一個(gè)處在百位，第一個(gè)3 3所在十

16、位，第二個(gè)所在十位，第二個(gè)3 3所在所在個(gè)位，個(gè)位，5 5和和9 9分別處在十分位和百分位。十進(jìn)制數(shù)是逢分別處在十分位和百分位。十進(jìn)制數(shù)是逢十進(jìn)一的。十進(jìn)一的。 我們最常用最熟悉的就是十進(jìn)制數(shù)，它的數(shù)值我們最常用最熟悉的就是十進(jìn)制數(shù)，它的數(shù)值部分是十個(gè)不同的數(shù)字符號(hào)部分是十個(gè)不同的數(shù)字符號(hào)0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9來表示的。來表示的。十進(jìn)制：十進(jìn)制：例如例如133.59133.59，它可用一個(gè)多項(xiàng)式來表示：，它可用一個(gè)多項(xiàng)式來表示：133.59=1133.59=1* *10102 2+3+3* *10101 1+3+3* *10100 0 +

17、5+5* *1010-1-1+9+9* *1010-2-2 實(shí)際上，十進(jìn)制數(shù)只是計(jì)數(shù)法中的一種，但它不是實(shí)際上，十進(jìn)制數(shù)只是計(jì)數(shù)法中的一種，但它不是唯一記數(shù)法。除了十進(jìn)制數(shù)，生產(chǎn)生活中還會(huì)遇到非十唯一記數(shù)法。除了十進(jìn)制數(shù)，生產(chǎn)生活中還會(huì)遇到非十進(jìn)制的記數(shù)制。如時(shí)間：進(jìn)制的記數(shù)制。如時(shí)間：6060秒為秒為1 1分，分，6060分為分為1 1小時(shí)，它小時(shí)，它是六十進(jìn)制的。兩根筷子一雙，兩只手套為一副，它們是六十進(jìn)制的。兩根筷子一雙，兩只手套為一副，它們是二進(jìn)制的。是二進(jìn)制的。其它進(jìn)制：其它進(jìn)制：二進(jìn)制、七進(jìn)制、八進(jìn)制、十二進(jìn)制、六十進(jìn)制二進(jìn)制、七進(jìn)制、八進(jìn)制、十二進(jìn)制、六十進(jìn)制二進(jìn)制只有0和1兩個(gè)

18、數(shù)字，七進(jìn)制用06七個(gè)數(shù)字十六進(jìn)制有09十個(gè)數(shù)字及ABCDEF六個(gè)字母. 為了區(qū)分不同的進(jìn)位制，常在數(shù)的右下角標(biāo)明基數(shù)，為了區(qū)分不同的進(jìn)位制，常在數(shù)的右下角標(biāo)明基數(shù)，十進(jìn)制一般不標(biāo)注基數(shù)十進(jìn)制一般不標(biāo)注基數(shù). .例如十進(jìn)制的例如十進(jìn)制的133.59133.59，寫成，寫成133.59133.59(10)(10)七進(jìn)制的七進(jìn)制的1313，寫成，寫成1313(7)(7)；二進(jìn)制的；二進(jìn)制的1010，寫成，寫成1010(2) (2) 一般地，若一般地，若k k是一個(gè)大于是一個(gè)大于1 1的整數(shù)，那么以的整數(shù)，那么以k k為基數(shù)的為基數(shù)的k k進(jìn)制可以表示為一串?dāng)?shù)字連寫在一起進(jìn)制可以表示為一串?dāng)?shù)字連寫在

19、一起的形式：的形式：11 0( )110(0,0, , ,).n nknnaaaaa kaa a k 十進(jìn)制的構(gòu)成十進(jìn)制的構(gòu)成十進(jìn)制由兩個(gè)部分構(gòu)成十進(jìn)制由兩個(gè)部分構(gòu)成例如：例如：37213721其它進(jìn)位制的數(shù)又是如何的呢？其它進(jìn)位制的數(shù)又是如何的呢？第一、它有第一、它有0 09 9十個(gè)數(shù)字；十個(gè)數(shù)字；第二、它有第二、它有“數(shù)位數(shù)位”，即，即從右往左從右往左為個(gè)位、十位、為個(gè)位、十位、百位、千位等等。百位、千位等等。( (用用1010個(gè)數(shù)字來記數(shù)，稱基數(shù)為個(gè)數(shù)字來記數(shù)，稱基數(shù)為10)10)01231011021071037213表示有：表示有：1 1個(gè)個(gè)1 1，2 2個(gè)十，個(gè)十， 7 7個(gè)百即個(gè)

20、百即7 7個(gè)個(gè)1010的平方，的平方，3 3個(gè)千即個(gè)千即3 3個(gè)個(gè)1010的立方的立方十進(jìn)制：十進(jìn)制：“滿十進(jìn)一滿十進(jìn)一”110( )110110(10)nnknnnna aa aakakakak其它進(jìn)制數(shù)化成十進(jìn)制數(shù)公式二進(jìn)制二進(jìn)制二進(jìn)制是用二進(jìn)制是用0 0、1 1兩個(gè)數(shù)字來描述的如兩個(gè)數(shù)字來描述的如1100111001二進(jìn)制的表示方法二進(jìn)制的表示方法區(qū)分的寫法：區(qū)分的寫法：1100111001（2 2）或者或者(11001)(11001)2 201234(2)212020212111001八進(jìn)制呢？八進(jìn)制呢？ 如如73427342(8)(8)k k進(jìn)制呢？進(jìn)制呢？ a an na an-1

21、n-1a an-2n-2a a1(k)1(k)？二進(jìn)制與十進(jìn)制的轉(zhuǎn)換二進(jìn)制與十進(jìn)制的轉(zhuǎn)換1 1、二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)、二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)例例1 1：將二進(jìn)制數(shù)：將二進(jìn)制數(shù)110011110011(2)(2)化成十進(jìn)制數(shù)?；墒M(jìn)制數(shù)。解：解：根據(jù)進(jìn)位制的定義可知根據(jù)進(jìn)位制的定義可知012345)2(21212020212111001112116132151所以，所以，110011110011（2 2）=51=51例例2 2、設(shè)計(jì)一個(gè)算法，將、設(shè)計(jì)一個(gè)算法，將k k進(jìn)制數(shù)進(jìn)制數(shù)a(a(共有共有n n位位) )轉(zhuǎn)換為十進(jìn)轉(zhuǎn)換為十進(jìn)制數(shù)制數(shù)b b。(1)(1)算法步驟算法步驟: :第一步，輸入

22、第一步，輸入a,ka,k和和n n的值；的值；第二步，將第二步，將b b的值初始化為的值初始化為0,i0,i的值初始化為的值初始化為1 1；第三步，第三步，b=b+ab=b+ai i* *k ki-1i-1, i=i+1, i=i+1第四步，判斷第四步，判斷inin是否成立是否成立. .若是若是, ,則執(zhí)行第五步則執(zhí)行第五步, ,否則否則, ,返回第三步；返回第三步；第五步，輸出第五步，輸出b b的值的值. .(2)程序框圖程序框圖:開始開始輸入輸入a,k,nb=0i=1把把a(bǔ)的右數(shù)第的右數(shù)第i位數(shù)字賦給位數(shù)字賦給tb=b+t*ki-1i=i+1in?否否是是輸出輸出b結(jié)束結(jié)束(3)程序：程序

23、：INPUT “a,k,n=”;a,k,nb=0i=1t=a MOD 10DO b=b+t*k(i-1) a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND*上面的程序如采用上面的程序如采用get函數(shù)函數(shù),可簡(jiǎn)化為：可簡(jiǎn)化為：INPUT a,k,nINPUT a,k,ni=1i=1b=0b=0WHILE i=nWHILE i=nt=GET ait=GET aib=tb=t* *k(i-1)+bk(i-1)+bi=i+1i=i+1WENDWENDPRINT bPRINT bENDEND備注備注:GET函數(shù)用于取出函數(shù)用于取出a的右數(shù)第的右數(shù)第i位數(shù)位數(shù)方法：除方法：除2取余法，即用取余法，即用2連續(xù)去除連續(xù)去除89