高中数学必修三课件1.3算法案例

n 次乘法运算，n 次加法运算.
例1 已知一个5次多项式为
5 4 3
f ( x ) 4 x 2 x 3.5 x 2.6 x 1.7 x 0.8
2
用秦九韶算法求f(5)的值. 解：根据秦九韶算法，把多项式改写成 f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8. v0= 4； v1= 4×5+2= 22； v2= 22×5+3.5=113.5； v3= 113.5×5-2.6= 564.9； v4= 564.9×5+1.7= 2826.2； v5= 2826.2×5-0.8= 14130.2. 所以f(5)=14130.2.
[问题1]我们常见的数字都是十进制的, 但是并不是生活中的每一种数字都是十进制的. 比如时间和角度的单位用六十进位制,电子计 算机用的是二进制.那么什么是进位制?不同的 进位制之间又有什么联系呢? 进位制是人们为了计数和运算的方便而 约定的一种记数系统，约定满二进一,就是二 进制;满十进一,就是十进制;满十六进一,就 是十六进制;等等. “满几进一”,就是几进制,几进制的基数就是几.
知识探究(一):秦九韶算法的基本思想
思考1:对于多项式f(x)=x5+x4+x3+x2+x+1， 怎么样求f(5)的值呢？
思考2:利用后一种算法求多项式 f(x)=anxn+an-1xn-1+„+a1x+a0的值，这 个多项式应写成哪种形式？ f(x)=anxn+an-1xn-1+„+a1x+a0 =(anxn-1+an-1xn-2+„+a2x+a1)x+a0 =((anxn-2+an-1xn-3+„+a2)x+a1)x+a0 = „ =(„((anx+an-1)x+an-2)x+„+a1)x+a0
+…+a1×k1+a0×k0 . 注意这是一 个n+1位数.
例1:把二进制数110011(2)化为十进制数. 分析:先把二进制数写成不同位上数字与2 的幂的乘积之和的形式,再按照十进制数的运算 规则计算出结果.
解:110011(2)
=1×25+1×24+0×23+0×22+1×21+1×20
=1×32+1×16+1×2+1=51.
7
所以，98和63的最大公约数等于7。
开始 输入：a,b i=0 是
a MOD 2=0且b MOD 2=0?
否 b>a? 是 否
t=a,a=b,b=t
a=a-b 否
a=b? 是 输出：a×2i
结束
程序： INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 i=i+1 WEND a=a/2,b=b/2 DO IF b>a THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2^i END
案例2、秦九韶算法
秦九韶（约1202年－1261年）南 宋官员、数学家，与李冶、杨辉、 朱世杰并称宋元数学四大家。主要 成就:1247年完成了数学名著《数 书九章》，其中的大衍求一术、三 斜求积术和秦九韶算法是具有世界 意义的重要贡献。秦九韶算法就是 中国古代数学的一枝奇葩。直到今 天，这种算法仍是多项式求值比较 先进的算法 。 美国著名科学史家萨顿说过，秦九 韶是“他那个民族，他那个时代， 并且确实也是所有时代最伟大的数 学家之一”。
10221(3)=1×34+0×33+2×32+2×31+1×30
=81+18+6+1=106. 第二步:再把十进制数化为二进制数: 106=1101010(2). ∴10221(3)=106= 1101010(2).
8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333
解：
225=135×1+90 135=90×1+45
1813=333×5+148 333=148×2+37
148=37×4+0 显然37是148和37的最大公约 数，也就是8251和6105的最 大公约数
4 3 2
∴f(4)=709.
程序？
开始
输入n，an，x的值
v=an i=n-1
i=i-1 v=vx+ai
i≥0？ 否 输出v 结束 输入ai
是
INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i>=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END
可使用数字符号的个数称为基数.基数 都是大于1的整数.
一般地,若k是一个大于1的整数,那么以k为 基数的k进制数可以表示为一串数字连写在一起 的形式 anan-1…a1a0(k)
k进制的数也可以表示成不同位上数字与 基数k的幂的乘积之和的形式,即
anan-1…a1a0(k)=an×kn+an-1×kn-1
例、用更相减损术求98与63的最大公约数
解：由于63不是偶数，把98和63以大数减小数，并辗转相减。 （98，63） =（63，35） 98-63=35
63-35=28 =（35，28）
35-28=7
28-7=21 21-7=14 14-7=7
=（28，7）
=（21，7） =（14，7） =（7，7） =
k进制数转化为十进制数的方法
先把k进制的数表示成不同位上数字 与基数k的幂的乘积之和的形式,即 anan-1…a1a0(k) =an×kn+an-1×kn-1+…+a1×k1+a0×k0 . 再按照十进制数的运算规则计算出结果.
301 例：10231（4）=________
235（7）
124 =________
案例1、
例、求18与24的最大公约数：
解：2 1 8 2 4 用公有质因数2除， 3 9 12 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：2×3＝6
短除法
想一想，如何求8251与6105的最大公约数？
辗转相除法（欧几里得算法） 例2 用辗转相除法求225和135的最大公约数
90=45×2 显然45是90和45的最大公约数，也就是 225和135的最大公约数 思考1：从上面的两个例子可以看出计 算的规律是什么？
S1：用大数除以小数
S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0
辗转相除除法的程序框图与程序 开始 INPUT m,n DO r=mMODn m=n n=r LOOP UNTIL r=0 PRINT m END
这种方法也可以推广为把 十进制数化为k进制数的 算法,称为除k取余法.

例3:把89化为五进制的数. 解:以5作为除数,相应的除法算式为: 余数 5 89 5 17 4 5 3 2 0 3 ∴ 89=324(5).
[问题4]你会把三进制数10221(3)化为二进制数吗?
解:第一步:先把三进制数化为十进制数:
输入m,n
r=mMODn
m=n
n=r 否
r=0？ 是 输出m
结束
《九章算术》——更相减损术
算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减 损，求其等也，以等数约之。
第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2 约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并 以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个 等数或这个等数与约简的数的乘积就是所求的最大公约数。
f ( x ) 3 x 2 x 9 x 11x 1 ,求f(4)的值. 解：根据秦九韶算法，把多项式改写成 f(x)=(((3x+2)x-9)x-11)x+1 v 0= 3 ； v1= 3×4+2= 14； v2= 14×4-9= 47； v3= 47×4-11= 177； v4= 177×4+1= 709；
十进制数转化为k进制数的方法
例2:把89化为二进制的数.
例2:把89化为二进制的数. 余数 1 0 0 1 1 0 1
解： 我们可以用下面的除法算式表示除2取余法:
2 89 2 44 2 22 2 11 2 5 2 2 21 0
把算式中各步所得的余数 从下到上排列,得到 89=1011001(2).