秦九韶算法与进位制-精讲版课件

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求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值．这样通过一次式的反复运算，逐步得出高次多项式的值的方法称作 ．秦九韶算法2．进位制是人们为了计数和运算方便而约定的记数系统．“满十进一”就是十进制，“满二进一”就是二进制，“满k进一”就是

，k进制的基数是k，因此k进制需要使用

数字．3．若k是一个大于1的整数，以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan－1…a1a0(k)(0<an<k,0≤an－1，…，a1，a0<k)其中右下角括号内的数字k表明此数是k进制数，十进制的基数不标注．k进制k个4．十进制数与k进制数可以相互转换(1)把k进制数化为十进制数的方法是：先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果．如anan－1…a2a1a0(k)＝

.其中要注意的是，k的幂的最高次数应是该k进制的位数减去1，然后逐个减小1，最后是0次幂．(2)将十进制化为k进制数的方法叫 ．即用k连续去除该十进制数或所得的商，直到商是零为止，然后把每次所得的余数倒着排成一列，就是相应的k进制数．例如，把十进制数化为二进制数的方法是除2取余法．an×kn＋an－1×kn－1＋…＋a2×k2＋a1×k＋a0除k取余法重点：(1)秦九韶算法的原理、算法思想、算法设计．(2)进位制的概念及其表示，进位制的相互转换及算法设计．难点：(1)递推关系的算法设计．(2)k进制数表示方法的理解及k进制数与十进制数之间相互转换．(2)f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时，求函数值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)的系数ak，放在循环体内，用一次循环实现．INPUT

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

i>＝0INPUT

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

vEND2．进位制的理解与程序设计(1)进位制及其转换是计算机的基础知识，它有助于了解计算机的工作原理，要切实弄明白．(2)二进制数只用0和1两个数字，这正好和电路的“通”和“断”两种状态相对应，因此计算机内部都使用二进制，计算机在进行运算时，都是先将输入的十进制数转化为二进制数进行运算和存储后，再转换为十进制数输出．(3)k进制数转换为十进制数的方法是：anan－1…a2a1a0(k)＝an×kn＋an－1×kn－1＋…＋a2×k2＋a1×k＋a0我们用t＝aMOD10来求k进制数a除以10的余数即此数的个位，用a＝a\10来记录a除以10的整数商．故把k进制数a(共有n位)转化为十进制数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其当型循环程序为：INPUT

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

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

bEND程序框图依据此程序：第1轮(i＝1)循环结束时b＝a0.第2轮(i＝2)循环结束时b＝a1k＋a0.…第j轮(i＝j)循环结束时，b＝aj－1kj－1＋aj－2kj－2＋…＋a1k＋a0.最后结束时，b＝ankn＋an－1kn－1＋…＋a1k＋a0.(4)将一个十进制数a化为k进制数b的步骤：第一步：将给定的十进制整数除以基数k，余数便是等值的k进制的最低位．第二步：将上一步的商再除以基数k，余数便是等值的k进制数的次低位．第三步：重复第二步，直到最后所得的商等于0为止．各次除得的余数，便是k进制各位的数，最后一次的余数是最高位．即除k取余法．算法程序为：INPUT

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

q＝0PRINT

bEND用WHILE语句编程如下：(1)十进制数a化为k进制数b的程序语句．INPUT

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

q<>0q＝a\k

←求a除以k的整数商r＝aMODk

←求a除以k的余数b＝b＋r*10^i

←把余数依次从右到左排列得 到k进制数bi＝i＋1a＝qWENDPRINT

bEND(5)k进制数的性质：①在k进制中，具有k个数字符号；例如十进制，有0,1,2,3,4,5,6,7,8,9十个数字．十六进制有0～9和A、B、C、D、E、F共十六个数字．②在k进制中，由低位向高位是按“逢k进一”的规则进行计数．例如十进制，逢“十”进一，二进制逢“二”进一．(6)非十进制数之间的转化一般应先转化成十进制数，再将这个十进制数转化为要化成的另一种进位制数．

[例1]

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

[解析]

可根据秦九韶算法原理，将所给多项式改写，然后由内到外逐次计算即可．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.[点评]利用秦九韶算法计算多项式的值，关键是能正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算需用前项的结果，故应认真、细心，确保中间结果的准确性．求多项式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1当x＝－2时的值．[解析]

先改写多项式，再由内向外计算．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.把二进制数1110011(2)化为十进制数．2．将8进制数314706(8)化为十进制数，并且编写一个实现该算法的程序．[解析]

1.先把二进制数写成不同位上数字与2的幂的乘积之和的形式，再按照十进制数的运算规则求出结果1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.2．利用把k进制数化为十进数的一般方法就可以将8进制数314706(8)化为十进制数，然后根据该算法，应用循环结构可以设计程序．314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化为十进制数是104902.8进制数314706(8)中共有6位，因此可令a＝314706，k＝8，n＝6，设计程序如下：程序运行时输入314706,8,6.[点评]

上述程序可以把任何一个k进制数a(共有n位)转化为十进制数b，只要输入相应的a，k，n的值即可．把7进制数24005(7)化为十进制数的结果为________．[答案]

2401[解析]

只需将该数写成其各位上的数字与7的幂的乘积之和的形式，再计算即可化为十进制数．24005(7)＝2×74＋4×73＋0×72＋0×71＋5＝2401，故七进制数24005(7)化成十进制数为2401.[例3]

1.把十进制数89化为二进制数．2．将十进制数21化为五进制数．[解析]

1.根据“满二进一”的原则，可以用2连续去除89或所得商，然后取余数—即除2取余法．用竖式表示为：∴89＝1×26＋0×25＋1×24＋1×23＋0×22×0×21＋1×20＝1011001(2)2．同1用除5取余法可得：

将十进制数22化为三进制数，并且编写一个实现该算法的程序．[解析]

用除3取余法可得：此算法程序为：(把十进制数a化为k进制数)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时的函数值f(2)．[解析]

本例中，有几项不存在，可视这些项的系数为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按照由内及外的顺序，依次计算一次多项式当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]将五进制数434化为二进制数．[解析]

先将五进制数化为十进制数．434(5)＝4×52＋3×51＋4×50＝119，再将十进制数119化为二进制数．则119＝1110111(2)所以434(5)＝1110111(2)[点评]

1.k进制之间相互转化可以借助十进制作跳板来进行．2．将十进制与k进制相互转换的算法结合在一块，就能实现非十进制数之间的转换了．一、选择题1．三位七进制最大的数表示的十进制的数是(

)A．322

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

C[解析]

三位七进制数中最大的为666(7)＝6×72＋6×7＋6＝342.2．下列各数转化成十进制后最小的数是(

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

A[解析]

将它们都化为十进制数为：A表示63，B表示78，C表示64，D表示73.3．已知一个k进制的数132与十进制的数30相等，那么k等于(

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

C[解析]

由k2＋3k＋2＝30得，k＝4或k＝－7(舍去)．4．类似于十进制中逢10进1，十二进制的进位原则是逢12进1，采用数字0,1,2，…，9和字母M，N共12个计数符号，这些符号与十进制的对应关系如下表：十二进制0123456789MN十进制01234567891011例如，由于563＝3×122＋10×12＋11，所以十进制中563在十二进制中就被表示为3MN，那么十进制中的2010在十二进制中被表示为(

)A．11N6