秦九韶算法與進(jìn)位制-精講版課件

1．把一個(gè)n次多項(xiàng)式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求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值．這樣通過一次式的反復(fù)運(yùn)算，逐步得出高次多項(xiàng)式的值的方法稱作 ．秦九韶算法2．進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)．“滿十進(jìn)一”就是十進(jìn)制，“滿二進(jìn)一”就是二進(jìn)制，“滿k進(jìn)一”就是

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

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

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

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

i>＝0INPUT

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

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

“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其當(dāng)型循環(huán)程序?yàn)椋篒NPUT

“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é)束時(shí)b＝a0.第2輪(i＝2)循環(huán)結(jié)束時(shí)b＝a1k＋a0.…第j輪(i＝j(luò))循環(huán)結(jié)束時(shí)，b＝aj－1kj－1＋aj－2kj－2＋…＋a1k＋a0.最后結(jié)束時(shí)，b＝ankn＋an－1kn－1＋…＋a1k＋a0.(4)將一個(gè)十進(jìn)制數(shù)a化為k進(jìn)制數(shù)b的步驟：第一步：將給定的十進(jìn)制整數(shù)除以基數(shù)k，余數(shù)便是等值的k進(jìn)制的最低位．第二步：將上一步的商再除以基數(shù)k，余數(shù)便是等值的k進(jìn)制數(shù)的次低位．第三步：重復(fù)第二步，直到最后所得的商等于0為止．各次除得的余數(shù)，便是k進(jìn)制各位的數(shù)，最后一次的余數(shù)是最高位．即除k取余法．算法程序?yàn)椋篒NPUT

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

q＝0PRINT

bEND用WHILE語句編程如下：(1)十進(jìn)制數(shù)a化為k進(jìn)制數(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進(jìn)制數(shù)bi＝i＋1a＝qWENDPRINT

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

[例1]

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

[解析]

可根據(jù)秦九韶算法原理，將所給多項(xiàng)式改寫，然后由內(nèi)到外逐次計(jì)算即可．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.[點(diǎn)評(píng)]利用秦九韶算法計(jì)算多項(xiàng)式的值，關(guān)鍵是能正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外逐次計(jì)算，由于后項(xiàng)計(jì)算需用前項(xiàng)的結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保中間結(jié)果的準(zhǔn)確性．求多項(xiàng)式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1當(dāng)x＝－2時(shí)的值．[解析]

先改寫多項(xiàng)式，再由內(nèi)向外計(jì)算．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.把二進(jìn)制數(shù)1110011(2)化為十進(jìn)制數(shù)．2．將8進(jìn)制數(shù)314706(8)化為十進(jìn)制數(shù)，并且編寫一個(gè)實(shí)現(xiàn)該算法的程序．[解析]

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

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

2401[解析]

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

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

1.根據(jù)“滿二進(jìn)一”的原則，可以用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取余法可得：

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

用除3取余法可得：此算法程序?yàn)椋?把十進(jìn)制數(shù)a化為k進(jìn)制數(shù))INPUT

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

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

本例中，有幾項(xiàng)不存在，可視這些項(xiàng)的系數(shù)為0，如含x5的項(xiàng)可記作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)及外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x＝2時(shí)的值：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]將五進(jìn)制數(shù)434化為二進(jìn)制數(shù)．[解析]

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

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

)A．322

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

C[解析]

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

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

A[解析]

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

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

C[解析]

由k2＋3k＋2＝30得，k＝4或k＝－7(舍去)．4．類似于十進(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例如，由于563＝3×122＋10×12＋11，所以十進(jìn)制中563在十二進(jìn)制中就被表示為3MN，那么十進(jìn)制中的2010在十二進(jìn)制中被表示為(

)A．11N6