算法案例-秦九韶和進(jìn)位制9

1、 古時(shí)候，當(dāng)邊境有敵人來(lái)犯時(shí)，守邊的官兵通過(guò)在烽火臺(tái)上點(diǎn)火向境內(nèi)報(bào)告，如圖，烽火臺(tái)上點(diǎn)火表示點(diǎn)火表示 數(shù)字?jǐn)?shù)字1，未點(diǎn)未點(diǎn)火表示數(shù)字火表示數(shù)字0，約定二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)的單位是1000，請(qǐng)你計(jì)算一下，這組烽火臺(tái)表示有多少敵人入侵？ 算法案例算法案例 進(jìn)位制進(jìn)位制1 1、什么是進(jìn)位制？、什么是進(jìn)位制？進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)記數(shù)系統(tǒng)。進(jìn)位制是一種進(jìn)位制是一種記數(shù)方式記數(shù)方式，用有限的，用有限的數(shù)字?jǐn)?shù)字在不同的位在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)個(gè)數(shù)稱(chēng)為稱(chēng)為基基數(shù)數(shù)，基數(shù)為，基數(shù)為n n

2、，即可稱(chēng)，即可稱(chēng)n n進(jìn)位制，簡(jiǎn)稱(chēng)進(jìn)位制，簡(jiǎn)稱(chēng)n n進(jìn)制。進(jìn)制?！皾M(mǎn)幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾.基數(shù)：基數(shù)： 為了區(qū)分不同的進(jìn)位制，常在數(shù)的為了區(qū)分不同的進(jìn)位制，常在數(shù)的右下角右下角標(biāo)明基數(shù)，標(biāo)明基數(shù)，十進(jìn)制一般不標(biāo)注基數(shù)十進(jìn)制一般不標(biāo)注基數(shù). .例如十進(jìn)制的例如十進(jìn)制的133133，寫(xiě)成，寫(xiě)成133133(10)(10)七進(jìn)制的七進(jìn)制的1313，寫(xiě)成，寫(xiě)成1313(7)(7)；二進(jìn)制的；二進(jìn)制的1010，寫(xiě)成，寫(xiě)成1010(2) (2) 一般地，若一般地，若k是一個(gè)大于是一個(gè)大于1的整數(shù)，那么以的整數(shù)，那么以k為基數(shù)的為基數(shù)的k進(jìn)制進(jìn)制可以表示為一串?dāng)?shù)字連寫(xiě)在一起可以表示為一串?dāng)?shù)

3、字連寫(xiě)在一起的形式：的形式：110110110( )(,0,0,)nnnnnnkaaaaNakaa aka aa a，2 2、最常見(jiàn)的進(jìn)位制是什么？除此之外還有哪、最常見(jiàn)的進(jìn)位制是什么？除此之外還有哪些常見(jiàn)的進(jìn)位制？請(qǐng)舉例說(shuō)明些常見(jiàn)的進(jìn)位制？請(qǐng)舉例說(shuō)明 最常見(jiàn)的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的最常見(jiàn)的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的十進(jìn)十進(jìn)制制,比如一般的數(shù)值計(jì)算，但是并不是生活比如一般的數(shù)值計(jì)算，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的中的每一種數(shù)字都是十進(jìn)制的. 古人有古人有半斤八兩半斤八兩之說(shuō)，就是之說(shuō)，就是十六十六進(jìn)制與進(jìn)制與十十進(jìn)制的轉(zhuǎn)換進(jìn)制的轉(zhuǎn)換. 比如時(shí)間和角度的單位用六十進(jìn)位制比如時(shí)間和角度的

4、單位用六十進(jìn)位制, 計(jì)算計(jì)算“一打一打”數(shù)值時(shí)是數(shù)值時(shí)是12進(jìn)制的。進(jìn)制的。 電子計(jì)算機(jī)用的是二進(jìn)制電子計(jì)算機(jī)用的是二進(jìn)制 。 （16）（7）（12）（2）練習(xí):下列寫(xiě)法正確的是： （ ）A、751 B、751 C、095 D、901A7 79 90 03 3、十進(jìn)制的構(gòu)成、十進(jìn)制的構(gòu)成十進(jìn)制由兩個(gè)部分構(gòu)成十進(jìn)制由兩個(gè)部分構(gòu)成第一、它有第一、它有0 09 9十個(gè)十個(gè)數(shù)字?jǐn)?shù)字；第二、它有第二、它有“數(shù)位數(shù)位”，即，即從右往左從右往左為個(gè)位、十位、為個(gè)位、十位、百位、千位等等。百位、千位等等。32103721 3 107 102 101 10 例如：例如：3721按照位置原則計(jì)數(shù)按照位置原則計(jì)數(shù)表

5、示有：表示有：1個(gè)個(gè)1，2個(gè)十，個(gè)十， 7個(gè)百即個(gè)百即7個(gè)個(gè)10的平方，的平方，3個(gè)千即個(gè)千即3個(gè)個(gè)10的立方的立方解：解：根據(jù)進(jìn)位制的定義可知根據(jù)進(jìn)位制的定義可知012345)2(21212020212111001112116132151所以，所以，110011110011（2 2）=51=51如如1100111001的寫(xiě)法：的寫(xiě)法：1100111001（2 2）或者或者(11001)(11001)2 24 4 二進(jìn)制的構(gòu)成二進(jìn)制的構(gòu)成二進(jìn)制是用二進(jìn)制是用0 0、1 1兩個(gè)數(shù)字來(lái)描述的兩個(gè)數(shù)字來(lái)描述的-十進(jìn)制數(shù)十進(jìn)制數(shù)其它進(jìn)位制的數(shù)又是如何的呢？其它進(jìn)位制的數(shù)又是如何的呢？5 5 閱讀課本閱

6、讀課本4040頁(yè)，探究頁(yè)，探究: :110( )nnka aa akk若表示一個(gè) 進(jìn)制數(shù)，如何把它寫(xiě)成各個(gè)位置上的數(shù)字與 的冪的乘積之和的形式。110( )110110(10)nnknnnna aa aakakakak其它進(jìn)制數(shù)化成十進(jìn)制數(shù)公式-化為十進(jìn)制數(shù)化為十進(jìn)制數(shù)236（7）=10011（2）=3452（6）=210273 767 432101 20 20 21 2 1 2 32103 64 65 62 6 120 19391將下列進(jìn)位制轉(zhuǎn)換為十進(jìn)位制數(shù)：方法：除方法：除2取余法，即用取余法，即用2連續(xù)去除連續(xù)去除89或所得的商，然后取余數(shù)?；蛩玫纳蹋缓笕∮鄶?shù)。例、例、 把把89化為

7、二進(jìn)制數(shù)化為二進(jìn)制數(shù)解：解：根據(jù)根據(jù)“逢二進(jìn)一逢二進(jìn)一”的原則，有的原則，有892441 2 (2220)+1 2( 2( 2110)+0)+1 2 (2 (2 (2 51)+0)+0)+15 2 212（2（2（2（221）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2523+2200）12624+23002089244144 222022 211011 2 51 2 (2 (2 (2 (2 21)+1)+0)+0)+1所以所以892（2（2（2（2 2 1）1）0）0）16

8、 十進(jìn)制轉(zhuǎn)換為二進(jìn)制十進(jìn)制轉(zhuǎn)換為二進(jìn)制注意：注意：1. 1.最后一步商為最后一步商為0 0，2.2.將上式各步所得的余數(shù)將上式各步所得的余數(shù)從下到上排列從下到上排列，得到：，得到： 89=101100189=1011001（2 2）另解（另解（除除2 2取余法的另一直觀寫(xiě)法取余法的另一直觀寫(xiě)法）：）：5 52 22 22 21 12 20 01 10 0余數(shù)余數(shù)11112222444489892 22 22 22 20 01 11 10 01 1練習(xí)練習(xí)將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)？將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)？（1 1）1010（2 2）2020方法方法:除除k取余法取余法即用即用k連續(xù)去除

9、連續(xù)去除n或所得的商，然后或所得的商，然后取余數(shù)。取余數(shù)。例：把例：把8989化為五進(jìn)制數(shù)?；癁槲暹M(jìn)制數(shù)。7 7、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制解：解：根據(jù)根據(jù)除除k k取余法取余法以以5 5作為除數(shù)，相應(yīng)的除法算式為：作為除數(shù)，相應(yīng)的除法算式為：所以，所以，89=32489=324（5 5）89895 517175 53 35 50 04 42 23 3余數(shù)余數(shù)練習(xí)：練習(xí)：完成下列進(jìn)位制之間的轉(zhuǎn)化：完成下列進(jìn)位制之間的轉(zhuǎn)化：（1）137（10）= （6）；（2）1231（5）= （7）；（3）1010111（2）= （4）。3453621113思考：思考：如何計(jì)算多項(xiàng)式如何計(jì)算多

10、項(xiàng)式f( (x) =) =x5 5x4 4x3 3x2 2x當(dāng)當(dāng)x = 5的值？的值？解：解：因?yàn)橐驗(yàn)閒(x) =xxxxx所以所以(5)=55555=3125625125255= 3906秦九韶：秦九韶：(5)=55555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) += 390610次乘法，次乘法，5次加法次加法。4次乘法，次乘法，5次加法次加法。 秦九韶（約秦九韶（約1202-1261），字），字道古，四川安岳人。先后在湖北，道古，四川安岳人。先后在湖北，安徽，江蘇，浙江等地做官，安徽，江蘇，浙江

11、等地做官，1261年左右被貶至梅州，（今廣東梅年左右被貶至梅州，（今廣東梅縣），不久死于任所。他與李冶，縣），不久死于任所。他與李冶，楊輝，朱世杰并稱(chēng)宋元數(shù)學(xué)四大家。楊輝，朱世杰并稱(chēng)宋元數(shù)學(xué)四大家。早年在杭州早年在杭州“訪習(xí)于太史，又嘗從訪習(xí)于太史，又嘗從隱君子受數(shù)學(xué)隱君子受數(shù)學(xué)”，1247年寫(xiě)成著名年寫(xiě)成著名的的數(shù)書(shū)九章數(shù)書(shū)九章。數(shù)書(shū)九章數(shù)書(shū)九章全全書(shū)凡書(shū)凡18卷，卷，81題，分為九大類(lèi)。其題，分為九大類(lèi)。其最重要的數(shù)學(xué)成就最重要的數(shù)學(xué)成就-“大衍總數(shù)術(shù)大衍總數(shù)術(shù)”（一次同余組解法）與（一次同余組解法）與“正負(fù)開(kāi)方正負(fù)開(kāi)方術(shù)術(shù)(高次方程數(shù)值解法）高次方程數(shù)值解法），使這部宋使這部宋代算經(jīng)在中

12、世紀(jì)世界數(shù)學(xué)史上占有代算經(jīng)在中世紀(jì)世界數(shù)學(xué)史上占有突出的地位。突出的地位。秦九韶算法秦九韶算法例例:用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解法一解法一:首先將原多項(xiàng)式首先將原多項(xiàng)式改寫(xiě)改寫(xiě)成如下形式成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7v0= v1= v2= v3= v4= v5= 所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多多項(xiàng)式的值是項(xiàng)式的值是2677.然后然后由內(nèi)向外由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值逐層計(jì)算一次多項(xiàng)式的值,即即2 v0 x-5=25-5=5 v1 x-4 =55-4=21 v2 x+

13、3 v3 x-6 v4 x+7 =215+3=108=1085-6=534=5345+7=26772 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多項(xiàng)式的值是多項(xiàng)式的值是2677.原多項(xiàng)式原多項(xiàng)式的系數(shù)的系數(shù)多項(xiàng)式多項(xiàng)式的值的值.例例:用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解法二解法二:列表列表2vnf(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以我們可以改寫(xiě)改寫(xiě)成如下形式成如下形式:f(x)=(anx+an-1)x+an

14、-2)x+a1)x+a0.v1=v0 x+an-1,一般地一般地,對(duì)于一個(gè)對(duì)于一個(gè)n次多項(xiàng)式次多項(xiàng)式v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項(xiàng)式次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個(gè)個(gè)一次多項(xiàng)式的值一次多項(xiàng)式的值.這種算法稱(chēng)為這種算法稱(chēng)為秦九韶算法秦九韶算法.v0=an,然后然后由內(nèi)向外由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值逐層計(jì)算一次多項(xiàng)式的值,即即2 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多項(xiàng)式的值是多項(xiàng)式的值是15170.練一練練一練:用秦九韶算法求多項(xiàng)

15、式用秦九韶算法求多項(xiàng)式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解解:原多項(xiàng)式先化為原多項(xiàng)式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:n次多項(xiàng)式有次多項(xiàng)式有n+1項(xiàng)項(xiàng),因此缺少哪一項(xiàng)因此缺少哪一項(xiàng)應(yīng)將其系數(shù)補(bǔ)應(yīng)將其系數(shù)補(bǔ)0.課堂小結(jié)1.十進(jìn)制數(shù)與十進(jìn)制數(shù)與k進(jìn)制數(shù)之間的轉(zhuǎn)化方法進(jìn)制數(shù)之間的轉(zhuǎn)化方法2.秦九韶算法秦九韶算法 一、選擇題 1三位七進(jìn)制的數(shù)表示的最大的十進(jìn)制的數(shù)是() A322 B332 C342 D352 答案C 解析三位七進(jìn)制數(shù)中最大的為666(7)672676342. 2下列各

16、數(shù)轉(zhuǎn)化成十進(jìn)制后最小的數(shù)是() A111 111(2) B210(6) C1 000(4) D81(9) 答案A 解析將它們都化為十進(jìn)制數(shù)為：A表示63，B表示78，C表示64，D表示73. 3類(lèi)似于十進(jìn)制中逢10進(jìn)1，十二進(jìn)制的進(jìn)位原則是逢12進(jìn)1，采用數(shù)字0,1,2，9和字母M，N共12個(gè)計(jì)數(shù)符號(hào)，這些符號(hào)與十進(jìn)制的對(duì)應(yīng)關(guān)系如下表：十二進(jìn)制0123456789MN十進(jìn)制01234567891011 例如，由于5633122101211，所以十進(jìn)制中563在十二進(jìn)制中就被表示為3MN，那么十進(jìn)制中的2010在十二進(jìn)制中被表示為 () A11N6 B6N11 C12N4 D1N24 答案A 解

17、析20101123112211126(11N6)(12) 二、解答題 4已知一個(gè)5次多項(xiàng)式為f(x)5x52x43.5x32.6x21.7x0.8.用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x5時(shí)的值寫(xiě)出其運(yùn)算過(guò)程 解析根據(jù)秦九韶算法，把多項(xiàng)式改寫(xiě)成如下形式： f(x)(5x2)x3.5)x2.6)x1.7)x0.8 按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x5時(shí)的值 x5 a55v0a55； a42 v1v0 xa455227； a33.5 v2v1xa32753.5138.5； a22.6 v3v2xa2138.552.6689.9； a11.7v4v3xa1689.951.73451.2； a00.8v

18、5v4xa03451.250.817255.2. 所以，當(dāng)x5時(shí)，多項(xiàng)式的值等于17255.2. 這不是很簡(jiǎn)單、很基本的概念嗎？ 十進(jìn)制數(shù)，有：萬(wàn)、千、百、十、個(gè)，各個(gè)位。 那么從一個(gè)數(shù)字中，比如 80486， 分離出來(lái)個(gè)位，應(yīng)該先除以10，取出余數(shù)就是6； 還要再分離出來(lái)十位數(shù)，應(yīng)該再除以10，取出余數(shù)8； 二進(jìn)制數(shù)，各個(gè)位是：8、4、2、個(gè)。 求其中每個(gè)位的數(shù)字，那就是“除二取余”唄。周朝有個(gè)周幽王，這是一個(gè)非常殘暴而腐敗的君主，他有個(gè)愛(ài)妃名叫褒姒，長(zhǎng)得非常美麗，東周列國(guó)志中有這樣一段話(huà)來(lái)形容褒姒：“目秀眉清，唇紅齒白，發(fā)挽烏云，指排削玉，有如花如月之容，傾國(guó)傾城之貌。”褒妃雖然很美，但是“從未開(kāi)顏一笑”。為此，周幽王使出了一個(gè)賞格：“誰(shuí)要能叫娘娘一笑，就