【成才之路】高中数学 算法案例第2课时秦九韶算法与进位制学案课件 新人教A版必修3_图文

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 个一次式可见,只要令 ?v =a ? 0 n ? 其中 k=1,2, ?, 就得到了一个递推关 n ?vk=vk-1x+an-k ? 系.这个递推关系是一个反复执行的步骤,可用循环语句 来实现.

2.进位制是人们为了计数和运算方便而约定的记数系
统.“满十进一”就是十进制,“满二进一”就是二进制, “满k进一”就是 需要使用 数字. k个 k进制 ,k进制的基数是k,因此k进制

3.若k是一个大于1的整数,以k为基数的k进制数可以

表示为一串数字连写在一起的形式:
anan-1?a1a0(k)(0<an<k,0≤an-1,?,a1,a0<k) 其中右下角括号内的数字k表明此数是k进制数,十进 制的基数不标注.

4.十进制数与k进制数可以相互转换
(1)把k进制数化为十进制数的方法是:先把这个k进制 数写成用各位上的数字与k的幂的乘积之和的形式,再按照 十进制数的运算规则计算出结果.如anan-1?a2a1a0(k)= an×kn+an-1×kn-1+?+a2×k2+a1×k+a0 逐个减小1,最后是0次幂. (2)将十进制化为k进制数的方法叫 除k取余法 .即用k 连续去除该十进制数或所得的商,直到商是零为止,然后 把每次所得的余数倒着排成一列,就是相应的k进制数.例 .其中要注

意的是,k的幂的最高次数应是该k进制的位数减去1,然后

如,把十进制数化为二进制数的方法是除2取余法.

重点:(1)秦九韶算法的原理、算法思想、算法设计.
(2)进位制的概念及其表示,进位制的相互转换及算法 设计. 难点:(1)递推关系的算法设计. (2)k进制数表示方法的理解及k进制数与十进制数之间

相互转换.

1. 理解秦九韶算法的关键: 一是弄清算法原理是加法对 乘法的分配律,二是弄清算法设计中递推关系是一个反复执 行的运算,故用循环语句来实现. (1)秦九韶算法过程分析: ?v =a , ? 0 n ? 由于 其中 k=1,2,?,n. ?vk=vk-1x+an-k. ? 这样我们便可由 v0 依次求出 v1,v2,?,vn: v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,?,vn= vn-1x+a0. 于是我们用 v 来记录每次一次式计算的结果,最初赋值 v=an,用 v=v*x+an-i 实现递推循环,i 的初值为 1,i=i+ 1 记录循环次数, i≤n 控制何时结束循环输出 v.f(x)的系数 ak 用一个循环语句实现输入.

(2)f(x)=anxn+an-1xn-1+?+a1x+a0当x=x0时,求函
数值f(x0)的算法设计. 程序框图:

程序语句:
INPUT i=0 WHILE INPUT i<=n “ai=”;a(i) “n=”;n

i=i+1
WEND INPUT i=1 v=a(n) “x0=”;x

WHILE i<=n
v=v*x+a(n-i) i=i+1 WEND PRINT v

END.

说明:也可以把输入f(x)的系数ak,放在循环体内,用
一次循环实现. INPUT i=n-1 WHILE i>=0 “n,an,x=”;n,v,x

INPUT

“ai=”;a

v=v*x+a i=i-1 WEND PRINT v

END

n(n+1) (3)用秦九韶算法将一个多项式(n 次)的至多 次乘法 2 和 n 次加法运算减少为至多 n 次乘法和 n 次加法运算,大大提 高了运算效率. 通过学习体会提高运算效率对用计算机解决问题的好处, 从而明确算法设计的一个重要问题——提高运算效率,进一步 领悟算法思想.

2.进位制的理解与程序设计
(1)进位制及其转换是计算机的基础知识,它有助于了 解计算机的工作原理,要切实弄明白. (2)二进制数只用0和1两个数字,这正好和电路的“通” 和“断”两种状态相对应,因此计算机内部都使用二进制,

计算机在进行运算时,都是先将输入的十进制数转化为二
进制数进行运算和存储后,再转换为十进制数输出.

(3)k进制数转换为十进制数的方法是:
anan-1?a2a1a0(k) =an×kn +an-1×kn-1 +?+a2×k2 + a1×k+a0我们用t=a MOD 10来求k进制数a除以10的余数 即此数的个位,用a=a\10来记录a除以10的整数商.故把k 进制数a(共有n位)转化为十进制数b的算法程序为:

INPUT
i=1 b=0

“a,k,n=”;a,k,n

t=a MOD 10 DO b=b+t*k^(i-1) a=a\10 t=a MOD 10

i=i+1
LOOP UNTIL PRINT b i>n

END

其当型循环程序为:
INPUT i=1 b=0 t=a MOD 10 “a,k,n=”;a,k,n

WHILE i<=n
b=b+t*k^(i-1) a=a\10 t=a MOD 10 i=i+1

WEND
PRINT b END

程序框图

依据此程序:
第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 b=0 i=0 DO “a,k=”;a,k

q=a\k
r=a MOD k b=b+r*10^i i=i+1 a=q

LOOP UNTIL
PRINT b END

q=0

用WHILE语句编程如下:

(1)十进制数a化为k进制数b的程序语句.
INPUT b=0 i=0 q=1 “a,k=”;a,k

WHILE q<>0

q=a\k
r=a MOD k b=b+r*10^i

←求a除以k的整数商
←求a除以k的余数 ←把余数依次从右到左排列得 到k进制数b

i=i+1

a=q
WEND PRINT b END

(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 i=0 b=0 a,k

DO
c=a\k r=a MOD k b=b+r*10^i

i=i+1
a=c LOOP UNTIL PRINT b END c=0

运行时,输入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 C.342 [答案] C B.332 D.352 )

[解析]
+6=342.

三位七进制数中最大的为666(7)=6×72+6×7

2.下列各数转化成十进制后最小的数是(
A.111 111(2) C.1 000(4) [答案] A [解析] B.210(6) D.81(9)

)

将它们都化为十进制数为:A表示63,B表示

78,C表示64,D表示73.

3.已知一个k进制的数132与十进制的数30相等,那么
k等于 ( A.-7或4 C.4 B.-7 D.都不对 )

[答案] C
[解析] 由k2+3k+2=30得,k=4或k=-7(舍去).

4.类似于十进制中逢10进1,十二进制的进位原则是
逢12进1,采用数字0,1,2,?,9和字母M,N共12个计数符 号,这些符号与十进制的对应关系如下表:

十二进 制 十进制

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

M 10

N

11

例如,由于563=3×122+10×12+11,所以十进制中
563在十二进制中就被表示为3MN,那么十进制中的2010在 十二进制中被表示为 ( A.11N6 B.6N11 )

C.12N4 D.1N24
[答案] A [解析] (11N6)(12). 2010 = 1×123 + 1×122 + 11×12 + 6 =

二、解答题
5.已知一个5次多项式为f(x)=5x5+2x4+3.5x3-2.6x2 +1.7x-0.8.用秦九韶算法求这个多项式当x=5时的值.写 出其运算过程.

[解析]

根据秦九韶算法,把多项式改写成如下形式:

f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8 按照从内到外的顺序,依次计算一次多项式当x=5时 的值. x=5

a5=5

v0=a5=5;

a4=2 v1=v0x+a4=5×5+2=27; a3=3.5 v2=v1x+a3=27×5+3.5=138.5;

a2=-2.6 v3=v2x+a2=138.5×5-2.6=689.9;
a1=1.7 v4=v3x+a1=689.9×5+1.7=3451.2; a0=-0.8 v5=v4x+a0=3451.2×5-0.8=17255.2. 所以,当x=5时,多项式的值等于17255.2.


相关文档

人教A版高中数学必修三算法案例第2课时《秦九韶算法与进位制》学案课件
2014人教A版高中数学必修三算法案例第2课时秦九韶算法与进位制课时练习
人教A版高中数学高一必修三算法案例第2课时秦九韶算法与进位制课时练习
高中数学必修三课件1.3.2《算法案例---秦九韶算法》课件(1)(新人教A版必修3)
数学知识点人教A版高中数学必修三算法案例第2课时秦九韶算法与进位制课时练习-总结
2018年高中数学(人教A版)必修三课件:1.3 第2课时 秦九韶算法与进位制
广东省汕头市高中数学第一章算法初步1.3秦九韶算法与进位制课件新人教A版必修3
【金版学案】2013-2014学年度高中数学 1.3.2 秦九韶算法和进位制同步辅导与检测课件 新人教A版必修3
高中数学(新人教A版)必修3第一章1.3《算法案例---秦九韶算法》课件
高中数学1-3-2秦九韶算法和进位制同步辅导与检测课件新人教A版必修
电脑版