秦九韶算法和進位制

1、（二）（二）復(fù)習(xí)：求兩數(shù)復(fù)習(xí)：求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0. 輾轉(zhuǎn)相除法與更相減損術(shù)的比較輾轉(zhuǎn)相除法與更相減損術(shù)的比較: : （1 1）都是求最大公約數(shù)的方法，計算上）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主主; ;計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)特別當(dāng)兩個數(shù)字大小區(qū)別較大

2、時計算次數(shù)的區(qū)別較明顯。別較明顯。（2 2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為體現(xiàn)結(jié)果是以相除余數(shù)為0 0則得到，而更相減損則得到，而更相減損術(shù)則以減數(shù)與差相等而得到術(shù)則以減數(shù)與差相等而得到. .案例案例3秦九韶算法秦九韶算法教學(xué)設(shè)計教學(xué)設(shè)計問題問題1設(shè)計求多項式設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時的值的算法時的值的算法,并寫出程序并寫出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序程序點評點評:上述算法一共做了上述算法一共做了15次乘法運算次乘法運算,5次次加法運算加法運

3、算.優(yōu)點是簡單優(yōu)點是簡單,易懂易懂;缺點是不通用缺點是不通用,不能不能解決任意多項式求值問題解決任意多項式求值問題,而且計算效率不高而且計算效率不高.n次多項式至多次多項式至多n(n+1)/2次乘法運算和次乘法運算和n次加法運算次加法運算 分析計算上述多項式的值分析計算上述多項式的值,一共需要幾次一共需要幾次乘法運算乘法運算,幾次加法運算？幾次加法運算？問題問題2有沒有更高效的算法有沒有更高效的算法?分析分析:計算計算x的冪時的冪時,可以利用前面的計算結(jié)可以利用前面的計算結(jié)果果,以減少計算量以減少計算量,即先計算即先計算x2,然后依次計算然后依次計算222,(),()xx xxxxxxx的值的

4、值.第二種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運乘法的運算次數(shù)減少了算次數(shù)減少了,因而能提高運算效率因而能提高運算效率.而且對于而且對于計算機來說計算機來說,做一次乘法所需的運算時間比做一做一次乘法所需的運算時間比做一次加法要長得多次加法要長得多,因此第二種做法能更快地得到因此第二種做法能更快地得到結(jié)果結(jié)果.9次乘法，次乘法，5次加法次加法問題問題3能否探索更好的算法能否探索更好的算法,來解決任意多來解決任意多項式的求值問題項式的求值問題?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7

5、=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=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所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是2677.這種求多項式值的方法就叫這種求多項式值的方法就叫秦九韶算法秦九韶算法.變?yōu)榍髱讉€一次式的值變?yōu)榍髱讉€一次式的值幾次乘法幾次乘法幾次加法？幾次加法？秦九韶秦九韶數(shù)書九章數(shù)書九章.當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是15170.練習(xí)練習(xí):用秦九韶算法求多項式用秦九韶

6、算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)當(dāng)x=5時的值時的值. 注意注意:n次多項式有次多項式有n+1項項,因此缺少哪一項因此缺少哪一項應(yīng)將其系數(shù)補應(yīng)將其系數(shù)補0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式我們可以改寫成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多項式的值時求多項式的值時,首先計算最內(nèi)層括號內(nèi)一首先計算最內(nèi)層括號內(nèi)一次多項式的值次多項式的值,即即 v1=anx+an-1,然后由內(nèi)向外逐層計算一次多項式的值然后由內(nèi)向外逐層計算一次多項式的值,即即一般地一般地,對于一個對于一個

7、n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個個一次多項式的值一次多項式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.點評點評:秦九韶算法是求一元多項式的秦九韶算法是求一元多項式的值的一種方法值的一種方法.它的特點是它的特點是:把求一個把求一個n次多項式的值次多項式的值轉(zhuǎn)化為求轉(zhuǎn)化為求n個一次多項式的值個一次多項式的值,通過這種轉(zhuǎn)通過這種轉(zhuǎn)化化,把運算的次數(shù)由至多把運算的次數(shù)由至多n(n+1)/2次乘法次乘法運算和運算和n次加法運算次加法運算,減少為減少為n次乘法運算

8、次乘法運算和和n次加法運算次加法運算,大大提高了運算效率大大提高了運算效率.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的觀察上述秦九韶算法中的n個一次式個一次式,可見可見vk的計算要用到的計算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n）這是一個在秦九韶算法中反復(fù)執(zhí)行的步這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟驟,因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)因此可用循環(huán)結(jié)構(gòu)來實現(xiàn). 第一步第一步,輸入多項式次數(shù)輸入多項式次數(shù)n、最高次項的系、最高次項的系數(shù)數(shù)an和和x的值的值 第二步

9、第二步,將將v的值初始化為的值初始化為an，將將i的值初始化的值初始化為為n-1 第三步第三步,輸入輸入i次項的系數(shù)次項的系數(shù)ai 第四步第四步,v=vx+ai,i=i-1 第五步第五步,若若i=0,則返回第三步，否則輸出則返回第三步，否則輸出v算法分析：算法分析：否否程序框圖程序框圖開始開始輸入輸入n,an,x的值的值輸入輸入aii=0?i=n-1v=anv=vx+aii=i-1輸出輸出v結(jié)束結(jié)束是是案例案例3 進位制進位制 問題問題11我們常見的數(shù)字都是十進制的我們常見的數(shù)字都是十進制的, ,但是并不是生活中的每一種數(shù)字都是十進制的但是并不是生活中的每一種數(shù)字都是十進制的. .比如時間和角

10、度的單位用六十進位制比如時間和角度的單位用六十進位制, ,電子計電子計算機用的是二進制算機用的是二進制. .那么什么是進位制那么什么是進位制? ?不同的不同的進位制之間又有什么聯(lián)系呢進位制之間又有什么聯(lián)系呢? ?進位制是人們?yōu)榱擞嫈?shù)和運算的方便而進位制是人們?yōu)榱擞嫈?shù)和運算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進一約定的一種記數(shù)系統(tǒng)，約定滿二進一, ,就是二就是二進制進制; ;滿十進一滿十進一, ,就是十進制就是十進制; ;滿十六進一滿十六進一, ,就就是十六進制是十六進制; ;等等等等. . “滿幾進一滿幾進一”,就是幾進制就是幾進制,幾進制的幾進制的基數(shù)基數(shù)就是幾就是幾.可使用數(shù)字符號的個數(shù)稱

11、為基數(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ù)字?jǐn)?shù)字,基數(shù)是基數(shù)是10; 十六進制可使用的數(shù)字或符號有十六進制可使用的數(shù)字或符號有09等等10個數(shù)字以及個數(shù)字以及AF等等6個字母個字母(規(guī)定字母規(guī)定字母AF對應(yīng)對應(yīng)1015),十六進制的基數(shù)是十六進制的基數(shù)是16.注意注意: :為了區(qū)分不同的進位制為了區(qū)分不同的進位制, ,常在數(shù)字常在數(shù)字的右下腳標(biāo)明基數(shù)的右下腳標(biāo)明基數(shù),. ,. 如如111001111001

12、(2)(2)表示二進制數(shù)表示二進制數(shù),34,34(5)(5)表示表示5 5進制數(shù)進制數(shù). .十進制數(shù)一般不標(biāo)注基數(shù)十進制數(shù)一般不標(biāo)注基數(shù).問題問題2十進制數(shù)十進制數(shù)3721中的中的3表示表示3個千個千,7表示表示7個百個百,2表示表示2個十個十,1表示表示1個一個一,從而它可以寫成從而它可以寫成下面的形式下面的形式:3721=3103+7102+2101+1100.想一想二進制數(shù)想一想二進制數(shù)1011(2)可以類似的寫成什可以類似的寫成什么形式么形式?1011(2)=123+022+121+120.同理同理:3421(5)=353+452+251+150.C7A16(16)=12164+716

13、3+10162 +1161+6160.一般地一般地,若若k是一個大于是一個大于1的整數(shù)的整數(shù),那么以那么以k為為基數(shù)的基數(shù)的k進制數(shù)可以表示為一串?dāng)?shù)字連寫在一進制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式起的形式anan-1a1a0(k) (0ank,0an-1,a1,a0k)意思是意思是:(1):(1)第一個數(shù)字第一個數(shù)字a an n不能等于不能等于0;0;(2)(2)每一個數(shù)字每一個數(shù)字a an n,a,an-1n-1, ,a,a1 1,a,a0 0都須小于都須小于k.k.k進制的數(shù)也可以表示成不同位上數(shù)字與進制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)基數(shù)k的冪的乘積之和的形式的冪的乘積之和的形式,即

14、即anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .注意這是一注意這是一個個n+1位數(shù)位數(shù).問題問題3二進制只用二進制只用0和和1兩個數(shù)字兩個數(shù)字,這這正好與電路的通和斷兩種狀態(tài)相對應(yīng)正好與電路的通和斷兩種狀態(tài)相對應(yīng),因因此此計算機內(nèi)部都使用二進制計算機內(nèi)部都使用二進制.計算機在進計算機在進行數(shù)的運算時行數(shù)的運算時,先把接受到的數(shù)轉(zhuǎn)化成二先把接受到的數(shù)轉(zhuǎn)化成二進制數(shù)進行運算進制數(shù)進行運算,再把運算結(jié)果轉(zhuǎn)化為十再把運算結(jié)果轉(zhuǎn)化為十進制數(shù)輸出進制數(shù)輸出.那么二進制數(shù)與十進制數(shù)之間是如那么二進制數(shù)與十進制數(shù)之間是如何轉(zhuǎn)化的呢何轉(zhuǎn)化的呢?例例1:把二進制數(shù)把二進制數(shù)110

15、011(2)化為十進制數(shù)化為十進制數(shù).分析分析:先把二進制數(shù)寫成不同位上數(shù)字與先把二進制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式的冪的乘積之和的形式,再按照十進制數(shù)的運算再按照十進制數(shù)的運算規(guī)則計算出結(jié)果規(guī)則計算出結(jié)果.解解:110011(2) =125+124+023+022+121+120 =132+116+12+1=51. k進制數(shù)轉(zhuǎn)化為十進制數(shù)的方法進制數(shù)轉(zhuǎn)化為十進制數(shù)的方法先把先把k進制的數(shù)表示成不同位上數(shù)字進制的數(shù)表示成不同位上數(shù)字與基數(shù)與基數(shù)k的冪的乘積之和的形式的冪的乘積之和的形式,即即anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0 .再按照十進制

16、數(shù)的運算規(guī)則計算出結(jié)果再按照十進制數(shù)的運算規(guī)則計算出結(jié)果.例例2:把把89化為二進制的數(shù)化為二進制的數(shù).分析分析:把把89化為二進制的數(shù)化為二進制的數(shù),需想辦法將需想辦法將89先寫成如下形式先寫成如下形式89=an2n+an-12n-1+a121+a020 .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 +

17、123+022+021+120=1011001(2).可以用可以用2連續(xù)去除連續(xù)去除89或所得商或所得商(一直到商為一直到商為0為止為止),然后取余數(shù)然后取余數(shù)-除除2取余法取余法.2=12+0, 1=02+1, 44 1例例2:把把89化為二進制的數(shù)化為二進制的數(shù).我們可以用下面的除法算式表示除我們可以用下面的除法算式表示除2取余法取余法:289 余數(shù)余數(shù)222 0211 025 122 121 020 1把算式中各步所得的余數(shù)把算式中各步所得的余數(shù)從下到上排列從下到上排列,得到得到89=1011001(2).這種方法也可以推廣為把這種方法也可以推廣為把十進制數(shù)化為十進制數(shù)化為k進制數(shù)的進制數(shù)的算法算法,稱為稱為除除k取余法取余法.例例3:把把89化為五進制的數(shù)化為五進制的數(shù).解解:以以5作為除數(shù)作為除數(shù),相應(yīng)的除法算式為相應(yīng)的除法算式為:17 4589 余數(shù)余數(shù)53 250 3 89=324(5).問題問題5你會把三進制數(shù)你會把三進制數(shù)10221(3)化為二進制數(shù)嗎化為二進制數(shù)嗎?解解:第一步第一步:先把