秦九韶算法與進位制-精講版課件

1．把一個n次多項式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫成如下形式：f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0求多項式的值時，首先計算最內(nèi)層括號內(nèi)一次多項式的值，然后由內(nèi)向外逐層計算一次多項式的值．這樣通過一次式的反復運算，逐步得出高次多項式的值的方法稱作 ．秦九韶算法2．進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)．“滿十進一”就是十進制，“滿二進一”就是二進制，“滿k進一”就是

，k進制的基數(shù)是k，因此k進制需要使用

數(shù)字．3．若k是一個大于1的整數(shù)，以k為基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一起的形式：anan－1…a1a0(k)(0<an<k,0≤an－1，…，a1，a0<k)其中右下角括號內(nèi)的數(shù)字k表明此數(shù)是k進制數(shù)，十進制的基數(shù)不標注．k進制k個4．十進制數(shù)與k進制數(shù)可以相互轉(zhuǎn)換(1)把k進制數(shù)化為十進制數(shù)的方法是：先把這個k進制數(shù)寫成用各位上的數(shù)字與k的冪的乘積之和的形式，再按照十進制數(shù)的運算規(guī)則計算出結(jié)果．如anan－1…a2a1a0(k)＝

.其中要注意的是，k的冪的最高次數(shù)應是該k進制的位數(shù)減去1，然后逐個減小1，最后是0次冪．(2)將十進制化為k進制數(shù)的方法叫 ．即用k連續(xù)去除該十進制數(shù)或所得的商，直到商是零為止，然后把每次所得的余數(shù)倒著排成一列，就是相應的k進制數(shù)．例如，把十進制數(shù)化為二進制數(shù)的方法是除2取余法．a(chǎn)n×kn＋an－1×kn－1＋…＋a2×k2＋a1×k＋a0除k取余法重點：(1)秦九韶算法的原理、算法思想、算法設計．(2)進位制的概念及其表示，進位制的相互轉(zhuǎn)換及算法設計．難點：(1)遞推關系的算法設計．(2)k進制數(shù)表示方法的理解及k進制數(shù)與十進制數(shù)之間相互轉(zhuǎn)換．(2)f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0當x＝x0時，求函數(shù)值f(x0)的算法設計．程序框圖：程序語句：INPUT

“n＝”；n

i＝0WHILE

i<＝nINPUT

“ai＝”；a(i)

i＝i＋1WENDINPUT

“x0＝”；x

i＝1

v＝a(n)WHILE

i<＝n

v＝v*x＋a(n－i)

i＝i＋1WENDPRINT

vEND.說明：也可以把輸入f(x)的系數(shù)ak，放在循環(huán)體內(nèi)，用一次循環(huán)實現(xiàn)．INPUT

“n，an，x＝”；n，v，xi＝n－1WHILE

i>＝0INPUT

“ai＝”；av＝v*x＋ai＝i－1WENDPRINT

vEND2．進位制的理解與程序設計(1)進位制及其轉(zhuǎn)換是計算機的基礎知識，它有助于了解計算機的工作原理，要切實弄明白．(2)二進制數(shù)只用0和1兩個數(shù)字，這正好和電路的“通”和“斷”兩種狀態(tài)相對應，因此計算機內(nèi)部都使用二進制，計算機在進行運算時，都是先將輸入的十進制數(shù)轉(zhuǎn)化為二進制數(shù)進行運算和存儲后，再轉(zhuǎn)換為十進制數(shù)輸出．(3)k進制數(shù)轉(zhuǎn)換為十進制數(shù)的方法是：anan－1…a2a1a0(k)＝an×kn＋an－1×kn－1＋…＋a2×k2＋a1×k＋a0我們用t＝aMOD10來求k進制數(shù)a除以10的余數(shù)即此數(shù)的個位，用a＝a\10來記錄a除以10的整數(shù)商．故把k進制數(shù)a(共有n位)轉(zhuǎn)化為十進制數(shù)b的算法程序為：INPUT

“a，k，n＝”；a，k，n

i＝1

b＝0t＝aMOD10DOb＝b＋t*k^(i－1)a＝a\10t＝aMOD10i＝i＋1LOOPUNTIL

i>nPRINT

bEND其當型循環(huán)程序為：INPUT

“a，k，n＝”；a，k，ni＝1b＝0t＝aMOD10WHILE

i<＝nb＝b＋t*k^(i－1)a＝a\10t＝aMOD10i＝i＋1WENDPRINT

bEND程序框圖依據(jù)此程序：第1輪(i＝1)循環(huán)結(jié)束時b＝a0.第2輪(i＝2)循環(huán)結(jié)束時b＝a1k＋a0.…第j輪(i＝j)循環(huán)結(jié)束時，b＝aj－1kj－1＋aj－2kj－2＋…＋a1k＋a0.最后結(jié)束時，b＝ankn＋an－1kn－1＋…＋a1k＋a0.(4)將一個十進制數(shù)a化為k進制數(shù)b的步驟：第一步：將給定的十進制整數(shù)除以基數(shù)k，余數(shù)便是等值的k進制的最低位．第二步：將上一步的商再除以基數(shù)k，余數(shù)便是等值的k進制數(shù)的次低位．第三步：重復第二步，直到最后所得的商等于0為止．各次除得的余數(shù)，便是k進制各位的數(shù)，最后一次的余數(shù)是最高位．即除k取余法．算法程序為：INPUT

“a，k＝”；a，kb＝0i＝0DOq＝a\kr＝aMODkb＝b＋r*10^ii＝i＋1a＝qLOOPUNTIL

q＝0PRINT

bEND用WHILE語句編程如下：(1)十進制數(shù)a化為k進制數(shù)b的程序語句．INPUT

“a，k＝”；a，kb＝0i＝0q＝1WHILE

q<>0q＝a\k

←求a除以k的整數(shù)商r＝aMODk

←求a除以k的余數(shù)b＝b＋r*10^i

←把余數(shù)依次從右到左排列得 到k進制數(shù)bi＝i＋1a＝qWENDPRINT

bEND(5)k進制數(shù)的性質(zhì)：①在k進制中，具有k個數(shù)字符號；例如十進制，有0,1,2,3,4,5,6,7,8,9十個數(shù)字．十六進制有0～9和A、B、C、D、E、F共十六個數(shù)字．②在k進制中，由低位向高位是按“逢k進一”的規(guī)則進行計數(shù)．例如十進制，逢“十”進一，二進制逢“二”進一．(6)非十進制數(shù)之間的轉(zhuǎn)化一般應先轉(zhuǎn)化成十進制數(shù)，再將這個十進制數(shù)轉(zhuǎn)化為要化成的另一種進位制數(shù)．

[例1]

用秦九韶算法求多項式f(x)＝1＋x＋0.5x2＋0.16667x3＋0.04167x4＋0.00833x5在x＝－0.2時的值．

[解析]

可根據(jù)秦九韶算法原理，將所給多項式改寫，然后由內(nèi)到外逐次計算即可．f(x)＝1＋x＋0.5x2＋0.16667x3＋0.04167x4＋0.00833x5＝((((0.00833x＋0.04167)x＋0.16667)x＋0.5)x＋1)x＋1，而x＝－0.2，所以有v0＝a5＝0.00833，v1＝v0x＋a4＝0.04，v2＝v1x＋a3＝0.15867，v3＝v2x＋a2＝0.46827，v4＝v3x＋a1＝0.90635，v5＝v4x＋a0＝0.81873.即f(－0.2)＝0.81873.[點評]利用秦九韶算法計算多項式的值，關鍵是能正確地將所給多項式改寫，然后由內(nèi)向外逐次計算，由于后項計算需用前項的結(jié)果，故應認真、細心，確保中間結(jié)果的準確性．求多項式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1當x＝－2時的值．[解析]

先改寫多項式，再由內(nèi)向外計算．f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1＝((((x＋5)x＋10)x＋10)x＋5)x＋1.而x＝－2，所以有：v0＝1，v1＝v0x＋a4＝1×(－2)＋5＝3，v2＝v1x＋a3＝3×(－2)＋10＝4，v3＝v2x＋a2＝4×(－2)＋10＝2，v4＝v3x＋a1＝2×(－2)＋5＝1，v5＝v4x＋a0＝1×(－2)＋1＝－1.即f(－2)＝－1.[例2]

1.把二進制數(shù)1110011(2)化為十進制數(shù)．2．將8進制數(shù)314706(8)化為十進制數(shù)，并且編寫一個實現(xiàn)該算法的程序．[解析]

1.先把二進制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式，再按照十進制數(shù)的運算規(guī)則求出結(jié)果1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.2．利用把k進制數(shù)化為十進數(shù)的一般方法就可以將8進制數(shù)314706(8)化為十進制數(shù)，然后根據(jù)該算法，應用循環(huán)結(jié)構(gòu)可以設計程序．314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化為十進制數(shù)是104902.8進制數(shù)314706(8)中共有6位，因此可令a＝314706，k＝8，n＝6，設計程序如下：程序運行時輸入314706,8,6.[點評]

上述程序可以把任何一個k進制數(shù)a(共有n位)轉(zhuǎn)化為十進制數(shù)b，只要輸入相應的a，k，n的值即可．把7進制數(shù)24005(7)化為十進制數(shù)的結(jié)果為________．[答案]

2401[解析]

只需將該數(shù)寫成其各位上的數(shù)字與7的冪的乘積之和的形式，再計算即可化為十進制數(shù)．24005(7)＝2×74＋4×73＋0×72＋0×71＋5＝2401，故七進制數(shù)24005(7)化成十進制數(shù)為2401.[例3]

1.把十進制數(shù)89化為二進制數(shù)．2．將十進制數(shù)21化為五進制數(shù)．[解析]

1.根據(jù)“滿二進一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù)—即除2取余法．用豎式表示為：∴89＝1×26＋0×25＋1×24＋1×23＋0×22×0×21＋1×20＝1011001(2)2．同1用除5取余法可得：

將十進制數(shù)22化為三進制數(shù)，并且編寫一個實現(xiàn)該算法的程序．[解析]

用除3取余法可得：此算法程序為：(把十進制數(shù)a化為k進制數(shù))INPUT

a，ki＝0b＝0DOc＝a\kr＝aMODkb＝b＋r*10^ii＝i＋1a＝cLOOPUNTIL

c＝0PRINTbEND運行時，輸入a＝22，k＝3.[例4]用秦九韶算法求多項式f(x)＝8x7＋5x6＋3x4＋2x＋1當x＝2時的函數(shù)值f(2)．[解析]

本例中，有幾項不存在，可視這些項的系數(shù)為0，如含x5的項可記作0·x5.∴f(x)＝8x7＋5x6＋0·x5＋3x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)·x＋3)·x＋0)·x＋0)·x＋2)x＋1按照由內(nèi)及外的順序，依次計算一次多項式當x＝2時的值：v0＝8；v4＝87×2＋0＝174；v1＝8×2＋5＝21;v5＝174×2＋0＝348；v2＝21×2＋0＝42;v6＝348×2＋2＝698；v3＝42×2＋3＝87;v7＝698×2＋1＝1397.∴f(2)＝1397.[例5]將五進制數(shù)434化為二進制數(shù)．[解析]

先將五進制數(shù)化為十進制數(shù)．434(5)＝4×52＋3×51＋4×50＝119，再將十進制數(shù)119化為二進制數(shù)．則119＝1110111(2)所以434(5)＝1110111(2)[點評]

1.k進制之間相互轉(zhuǎn)化可以借助十進制作跳板來進行．2．將十進制與k進制相互轉(zhuǎn)換的算法結(jié)合在一塊，就能實現(xiàn)非十進制數(shù)之間的轉(zhuǎn)換了．一、選擇題1．三位七進制最大的數(shù)表示的十進制的數(shù)是(

)A．322

B．332C．342 D．352[答案]

C[解析]

三位七進制數(shù)中最大的為666(7)＝6×72＋6×7＋6＝342.2．下列各數(shù)轉(zhuǎn)化成十進制后最小的數(shù)是(

)A．111111(2) B．210(6)C．1000(4) D．81(9)[答案]

A[解析]

將它們都化為十進制數(shù)為：A表示63，B表示78，C表示64，D表示73.3．已知一個k進制的數(shù)132與十進制的數(shù)30相等，那么k等于(

)A．－7或4 B．－7C．4 D．都不對[答案]

C[解析]

由k2＋3k＋2＝30得，k＝4或k＝－7(舍去)．4．類似于十進制中逢10進1，十二進制的進位原則是逢12進1，采用數(shù)字0,1,2，…，9和字母M，N共12個計數(shù)符號，這些符號與十進制的對應關系如下表：十二進制0123456789MN十進制01234567891011例如，由于563＝3×122＋10×12＋11，所以十進制中563在十二進制中就被表示為3MN，那么十進制中的2010在十二進制中被表示為(

)A．11N6