当前位置:文档之家› 高中数学必修三课件1.3算法案例

高中数学必修三课件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).
相关主题