当前位置:首页 >> 数学 >>

13算法案例(二)


练习1
求120与168的最大公约数

法一:168=120×1+48;

120=48×2+24;
48=24×2 所以24是120与168的最大公约数
法二:168-120=48; 120-48=72; 72-48=24; 48-24=24

练习2

B

>
练习3

〖教学设计〗
[问题1]设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7 当x=5时的值的算法,并写出程序.
程序
x=5 f=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7

PRINT f
END

点评:上述算法一共做了15次乘法运算,5次加法 运算.优点是简单,易懂;缺点是计算效率不高.

[问题2]有没有更高效的算法? 分析:计算x的幂时,可以利用前面的计算结 果,以减少计算量, 即先计算x2,然后依次计算

x ? x,( x ? x) ? x,(( x ? x) ? x) ? x
2 2 2

第二种做法与第一种做法相比,乘法的运 算次数减少了,因而能提高运算效率.而且对于 计算机来说,做一次乘法所需的运算时间比做一 次加法要长得多,因此第二种做法能更快地得到 结果.

[问题3]能否探索更好的算法,来解决任意多项式的 求值问题? v =2 0 f(x)=2x5-5x4-4x3+3x2-6x+7 v1=v0x-5=2×5-5=5 4 3 2 =(2x -5x -4x +3x-6)x+7 v =v x-4=5 × 5-4=21 2 1 =((2x3-5x2-4x+3)x-6)x+7 v3=v2x+3=21×5+3=108 2 =(((2x -5x-4)x+3)x-6)x+7 v4=v3x-6=108×5-6=534 =((((2x-5)x-4)x+3)x-6)x+7 所以,当x=5时,多项式的值是2677. 这种求多项式值的方法就叫秦九韶算法.

v5=v4x+7=534×5+7=2677

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由内向外逐层计算一次多项式的值,即

v0=2

v1=v0x-5=2×5-5=5

v2=v1x-4=5×5-4=21

v3=v2x+3=21×5+3=108
v4=v3x-6=108×5-6=534 所以,当x=5时,多 v5=v4x+7=534×5+7=2677 项式的值是2677.

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.

解法二:列表
2

原多项式 的系数

x=5
2

-5 10 5

-4 25 21

3 105 108

-6 7 540 2670 534 2677
多项式 的值.

所以,当x=5时,多项式的值是2677.

练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值. 解:原多项式先化为:

f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0
3 -6 0 605 3040 15170 608 3034 15170 所以,当x=5时,多项式的值是15170. 注意:n次多项式有n+1项,因此缺少哪一项 应将其系数补0. 列表 2 x=5 2 -5 10 5 0 -4 25 125 25 121

一般地,对于一个n次多项式 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,

然后由内向外逐层计算一次多项式的值,即
v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0.

这样,求n次多项式f(x)的值就转化为求n个 一次多项式的值.这种算法称为秦九韶算法.

程序框图 开始
输入a0,a1,a2,a3,a4,a5

f(x)=2x5-5x4-4x3+3x2-6x+7

输入x0
n=1 v=a5

程序
INPUT a0,a1,a2,a3,a4,a5

n=n+1 n≤5?
v=vx0+a5-n


输出v



结束

INPUT x0 n=1 v=a5 WHILE n<=5 v=vx0+a5-n n=n+1 WEND PRINT v END

进位制是人们为了计数和运算的方便而 约定的一种记数系统,约定满二进一,就是二 进制;满十进一,就是十进制;满十六进一,就 是十六进制;等等. “满几进一”,就是几进制,几进制的基数就是几. 可使用数字符号的个数称为基数.基数都是 大于1的整数.

二进制:可使用的数字有0和1,基数是2;
十进制:可使用的数字有0,1,2,…,8,9等十个数字, 基数是10; 注意:为了区分不同的进位制,常在数字的右 下脚标明基数,. 如111001(2)表示 ? 进制数,34(5)表示?进制数. 十进制数一般不标注基数.

练习.下列有可能是 4 进制数的是( A.5 123 C.3 103

)

B.6 542 D.4 312

解析

4 进制数每位上的数字一定小于 4,故选 C.

十进制数3721中的3表示3个千,7表示7个百,2 表示2个十,1表示1个一,从而它可以写成下面 的形式: 3721=3×103+7×102+2×101+1×100. 问题:1011(2)可以类似的写成什么形式? 1011(2)=1×23+0×22+1×21+1×20.

同理3421(5)= 3×53+4×52+2×51+1×50.

例1:把二进制数110011(2)化为十进制数.
解:110011(2) =1×25+1×24+0×23+0×22+1×21+1×20 =1×32+1×16+1×2+1=51. 练习:10221(3)化为十进制 解:10221(3)=1×34+0×33+2×32+2×31+1×30 =81+18+6+1=106.

例2:把89化为二进制的数. 我们可以用下面的除法算式表示除2取余法: 余数 1 0 0 1 1 0 1

2 89 2 44 2 22 2 11 2 5 2 2 21 0

把算式中各步所得的余数 从下到上排列,得到 89=1011001(2).
这种方法也可以推广为把 十进制数化为k进制数的 算法,称为除k取余法.

练习:把89化为五进制的数. 解:以5作为除数,相应的除法算式为: 余数 5 89 5 17 4 5 3 2 0 3 ∴ 89=324(5).

例3:把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= 1101010(2).

小结
? 进位制的概念及表示方法; ? 各种进位制之间的相互转化.


相关文章:
第13课时5.4.3算法案例三(二分法)已对
第一会所 sis001 www.001dizhi.com 第 13 课时重点难点 5.4 算法案例 重点:...2.能由流程图分析出期所含有的结构并用 为代码表示出相应的算法. 3.GoTo 语句...
§ 13.3 算法案例
1.4算法案例 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题...的算法流程图,并写出其伪代码.(其中 分别表示区间的左右端点) 图 13-3-2 ...
1.3算法案例(3)
1.3.1算法案例一 13页 1下载券 1.3.1算法案例(一) 23页 免费 1.3算法案例() 2页 1下载券1​.​3​算​法​案​例​(​3​) ...
算法案例分析(雷春来)
13页 2下载券 案例分析方法 暂无评价 1页 免费 案例分析方法(最新) 暂无评价...《算法案例分析》教学设计西乡县第二中学 雷春来 723500 课题:算法案例分析 ...
算法案例
13页 免费 算法案例1 暂无评价 12页 20财富值 算法案例2 暂无评价 17页 免费...(讲座 17)—算法案例 数学第一轮复习教案 )一.课标要求: 课标要求:通过阅读...
算法案例
13 算法案例 暂无评价 18页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出...第二种算法与第一种算法相比,乘法的运算次数减少了,对计算机来说,毕竟做一次...
高二数学算法案例3
高二数学算法案例3_从业资格考试_资格考试/认证_教育专区。第 13 课时 5.4 ...(3)分层训练 1、阅读下列代码,写出该代码的运行结果 p←20 m←2 do p←p...
1.3算法案例(已修)
1.3.1算法案例一 13页 1财富值 1.3.1算法案例(一) 23页 免费 1.3算法案例() 2页 1财富值喜欢此文档的还喜欢 基本算法语句与算法案例练... 3页 免...
13 第十三编 算法初步、推理与证明、复数(共51页)_免费...
1/2 相关文档推荐 课标版2011届高三数学全程... 51页 10财富值 13十三...流程图如下: 方法一 方法二 § 13.2 基本算法语句、算法案例 基础自测 1....
实习教案10-算法案例2
(星期 4 ) 第 节课 实习学校 教学课题 所用教材 陈经纶中学 算法案例 2 实习班级 高一 2 班 实习科目 数学 教材名称: 高中数学必修 第 出版社: 人民教育...
更多相关标签: