1.3 算法与案例 课件（36张PPT）

第一章 算法初步
1.3 算法案例
1.3.2 秦九韶算法与进位制
（1）设计求多项式
当x=5时的值的算法，并写出程序。

（2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？
三、秦九韶算法

思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？

f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.
我们可以改写成如下形式:
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.
求多项式的值时,首先计算最内层括号内一次多项式的值,即


v1=anx+an-1,
然后由内向外逐层计算一次多项式的值,即
一般地,对于一个n次多项式
v2=v1x+an-2,
v3=v2x+an-3, ……,
vn=vn-1x+a0.
这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.
《数书九章》——秦九韶算法

设
是一个n 次的多项式
对该多项式按下面的方式进行改写：
思考：当知道了x的值后该如何求多项式的值？
这是怎样的一种改写方式？最后的结果是什么？
要求多项式的值，应该先算最内层的一次多项式的值，即
然后，由内到外逐层计算一次多项式的值，即
最后的一项是什么？
这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。
思考：在求多项式的值上，这是怎样的一个转化？
2 -5 0 -4 3 -6 0


x=5
10
5
25
25
125
121
605
608
3040
3034
所以,当x=5时,多项式的值是15170.
练习:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.
解:原多项式先化为:
f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0
列表
2
15170
15170
注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.
求多项式的值
【例2】 用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x
当x=3时的值.
分析:解决本题首先需要将原多项式化成f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)x的形式,其次再弄清v0,v1,v2,…,v7分别是多少,再针对这些式子进行计算.
解:f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)x,
所以有v0=7;
v1=7×3+6=27;
v2=27×3+5=86;
v3=86×3+4=262;
v4=262×3+3=789;
v5=789×3+2=2 369;
v6=2 369×3+1=7 108;
v7=7 108×3=21 324.
故当x=3时,多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x的值为21 324.
反思秦九韶算法的关键在于把n次多项式转化为一次多项式,注意
体会递推的实现过程,实施运算时要由内向外,一步一步执行.
【变式训练2】 用秦九韶算法求f(x)=3x5+8x4-3x3+5x2+12x-6当x=2时的值.

解:根据秦九韶算法,把多项式改写成如下形式:
f(x)=((((3x+8)x-3)x+5)x+12)x-6,按照从内到外的顺序,依次计算一次多项式当x=2时的值.
v0=3,
v1=v0×2+8=3×2+8=14,
v2=v1×2-3=14×2-3=25,
v3=v2×2+5=25×2+5=55,
v4=v3×2+12=55×2+12=122,
v5=v4×2-6=122×2-6=238,
所以当x=2时,多项式的值为238.
易错点:利用秦九韶算法求含空项的n次多项式的值时易出现错误
【例3】 已知f(x)=3x4+2x2+4x+2,利用
秦九韶算法求f(-2)的值.

错解:f(x)=((3x2+2)x+4)x+2,
v1=3×(-2)2+2=14;
v2=14×(-2)+4=-24;
v3=-24×(-2)+2=50.故f(-2)=50.
错因分析:所求f(-2)的值是正确的,但是错解中没有抓住
秦九韶算法原理的关键,正确改写多项式,并使每一次
计算只含有x的一次项.
正解:
f(x)=3x4+0·x3+2x2+4x+2=(((3x+0)x+2)x+4)x+2,
v1=3×(-2)+0=-6;
v2=-6×(-2)+2=14;
v3=14×(-2)+4=-24;
v4=-24×(-2)+2=50.
故f(-2)=50.

反思利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写,依次计算一次多项式,由于后项计算用到前项的结果,故应认真、细心,确保中间结果的准确性.若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看成0·xn.
【变式训练3】 用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当x=2时的值.
解:f(x)=8x7+5x6+0·x5+3·x4+0·x3+0·x2+2x+1
=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1.
按照由内到外的顺序,依次计算一次多项式当x=2时的值.
v0=8;
v1=8×2+5=21;
v2=21×2+0=42;
v3=42×2+3=87;
v4=87×2+0=174;
v5=174×2+0=348;
v6=348×2+2=698;
v7=698×2+1=1 397.故当x=2时,多项式的值为1 397.
2.用秦九韶算法求多项式 ,
当x=3时的值，需要进行的乘法、加法次数分别是

（ ）

A. 4 ，4 B. 5，5

C. 3 ，2 D. 6，5


B
四、进位制
1、什么是进位制？
进位制是人们为了计数和运算方便而约定的记数系统。
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。
比如：
满二进一，就是二进制；
满十进一，就是十进制；
满十二进一，就是十二进制；
满六十进一，就是六十进制
基数：
“满几进一”就是几进制，几进制的基数就是几.
2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．
最常见的进位制应该是我们数学中的十进制,比如一般的数值计算，但是并不是生活中的每一种数字都是十进制的.
古人有半斤八两之说，就是十六进制与十进制的转换.
比如时间和角度的单位用六十进位制, 计算“一打”数值时是12进制的。
电子计算机用的是二进制 。
式中1处在百位，第一个3所在十位，第二个3所在个位，5和9分别处在十分位和百分位。十进制数是逢十进一的。
我们最常用最熟悉的就是十进制数，它的数值部分是十个不同的数字符号0，1，2，3，4，5，6，7，8，9来表示的。
十进制：
例如133.59，它可用一个多项式来表示：
133.59 = 1*102+3*101+3*100 +5*10-1+9*10-2
实际上，十进制数只是计数法中的一种，但它不是
唯一记数法。除了十进制数，生产生活中还会遇到非十
十进制的记数制。如时间：60秒为1分，60分为1小时，
它是六十进制的。两根筷子一双，两只手套为一副，它
们是二进制的。
其它进制：
二进制、七进制、八进制、十二进制、六十进制……
二进制只有0和1两个数字，七进制用0~6七个数字
十六进制有0~9十个数字及ABCDEF六个字母.
为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数.
例如十进制的133.59，写成133.59(10)
七进制的13，写成13(7)；二进制的10，写成10(2)
一般地，若k是一个大于1的整数，那么以k
为基数的k进制可以表示为一串数字连写在一起
的形式：

十进制的构成
十进制由两个部分构成
例如：3721
其它进位制的数又是如何的呢？
第一、它有0～9十个数字；
第二、它有“数位”，即从右往左为个位、十位、百位、千位等等。
(用10个数字来记数，称基数为10)
表示有：1个1，2个十， 7个百即7个10的平方，3个千即3个10的立方

十进制：“满十进一”
二进制
二进制是用0、1两个数字来描述的．如11001
二进制的表示方法
区分的写法：11001（2）或者(11001)2

八进制呢？
如7342(8)
k进制呢？
anan-1an-2…a1(k)？
二进制与十进制的转换
1、二进制数转化为十进制数
例1：将二进制数110011(2)化成十进制数。
解：
根据进位制的定义可知
所以，110011（2）=51．

k进制数转化为十进制数的方法
先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即
anan-1…a1a0(k)
=an×kn+an-1×kn-1+…+a1×k1+a0×k0 .
再按照十进制数的运算规则计算出结果.
2、十进制转换为二进制
方法 ：除2取余法，
即用2连续去除89或所得的商，然后取余数。
例： 把89化为二进制数
注意：
1.最后一步商为0，
2.将上式各步所得的余数从下到上排列，得到：
89=1011001（2）
解：（除2取余法的直观写法）：


5
2
2


2
1


2
0
1
0
余数




11
22




44
89
2
2
2
2
0
1
1
0
1
练习
将下面的十进制数化为二进制数？
（1）10
（2）20
把89化为五进制数。
3、十进制转换为其它进制
解：
根据除k取余法
以5作为除数，相应的除法算式为：
所以，89=324（5）


89
5
17


5
3


5
0
4
2
3
余数
[问题5]你会把三进制数10221(3)化为二进制数吗?
解:第一步:先把三进制数化为十进制数:
10221(3)=1×34+0×33+2×32+2×31+1×30
=81+18+6+1=106.
第二步:再把十进制数化为二进制数:
106=1101010(2).
∴10221(3)=106（10）=
1101010(2).
十进制数化为k进制数
【例1】 (1)将194化成八进制数;
(2)将48化成二进制数.
分析:除以k取余→倒序写出→标明基数
解:(1)


所以194化为八进制数为302(8).
(2)



所以48化成二进制数为110000(2).
【变式训练1】
(1)将137转化为六进制的数;
(2)将96转化为五进制的数.
解:(1)



所以137转化为六进制的数为345(6).
(2)



所以96转化为五进制的数为341(5).
k进制数化为十进制数
【例2】 将下列各数化成十进制数.
(1)11001000(2);　(2)310(8).

解:(1)11001000(2)
=1×27+1×26+0×25+0×24+1×23+0×22+0×21+0×20=200.
(2)310(8)=3×82+1×81+0×80=200.

反思k进制数化为十进制数:先把k进制数写成不同位上的数字与k的幂的乘积之和的形式,再按十进制数的运算规则计算出结果.
【变式训练2】
(1)将236(7)转化为十进制的数;
(2)将1032(4)转化为十进制的数.

解:(1)236(7)=2×72+3×71+6×70
=98+21+6=125.
(2)1032(4)=1×43+0×42+3×41+2×40
=64+0+12+2=78.
不同进位制数间的互化

【例3】 把1234(5)转化为六进制数.

分析:五进制数和六进制数之间的互化需要借助十进制数来进行.
解:1234(5)=1×53+2×52+3×51+4×50=194.



则1234(5)=522(6).
【变式训练3】
把八进制数2016(8)化为五进制数.
解:2016(8)=2×83+0×82+1×81+6×80=1 024+0+8+6=1 038.





则2016(8)=13123(5).
1. 下列各数中最小的数是: ( )

A.111111(2) B.210(6)

C.1000(4) D.81(8)


A
2、 把五进制数44（5）化为二进制数.
【做一做】 以下各数有可能是五进制数的是(　　)
A.15 B.106 C.731 D.21340

答案:D
小结
进位制的概念及表示方法;



各种进位制之间的相互转化.
anan-1…a1a0(k)
=an×kn+an-1×kn-1+…+a1×k1+a0×k0 .
k进制数的特点
(1)具有k个数字符号,它们是0,1,2,…,(k-1).
(2)由低位到高位是按“逢k进一”的规则进行计数.
(3)基数是k.
(4)可以表示为一串数字连写在一起的形式,
即anan-1…a1a0(k)(0(5)与十进制类似,也可以用其基数的幂的形式表示,
即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a2×k2+a1×k+a0.