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

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.2 基本算法语句、算法案例--随堂巩固
13.2 基本算法语句、算法案例 1.如果下边程序执行后输出的结果是 132,那么程序中 UNTIL 后面的“条件”应为( ) A.i>11 B.i>=11 C.i<=11 D.i<11 ...
1.3算法案例(二)
1.3算法案例(二)_数学_高中教育_教育专区。高二数学教学设计教师 刘艳娟、...1.3.3算法案例(2) 13页 免费 1.3.2算法案例(秦九韶算... 20页 2下载...
§ 13.3 算法案例
1.4算法案例 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题...的算法流程图,并写出其伪代码.(其中 分别表示区间的左右端点) 图 13-3-2 ...
§1.3.1算法案例2 一课一练
§1.3.1 算法案例 2 1、用秦九韶算法和直接算法求当 x ? x0 时 f ?...13 在 x ? 2 的值,写出详细步骤,并统计需要多少次乘法计算和多少次加法计算...
1.3算法案例(2)
1.3.2算法案例(第二课时) 14页 免费 1.3.3算法案例(2) 13页 免费 1-...体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学 表达能力 重点:...
算法案例试题(含答案)3
同系列文档 算法案例试题(含答案)1 算法案例试题(含答案)21/2 相关文档推荐...由于 f(1)=13-1-1=-1<0, f(1.5)=1.53-1.5-1=0.875>0, 所以取[...
1.3算法案例(3)
1.3.1算法案例一 13页 1下载券 1.3.1算法案例(一) 23页 免费 1.3算法案例() 2页 1下载券1​.​3​算​法​案​例​(​3​) ...
1.3算法案例(1)
1.3.1算法案例一 13页 1下载券 1.3.1算法案例(一) 23页 免费 1.3算法案例() 2页 1下载券1​.​3​算​法​案​例​(​1​) ...
17 §1.4算法案例(二)
扬大附中导学案必修三 第一章 算法初步 主备:高源 辅备:刘跃武 编号:17 反思感悟: §1.4 算法案例(二)班级 姓名 学号 一、教学目标: 1、通过对算法案例的赏...
更多相关标签:
算法案例ppt | 智能算法30个案例分析 | 算法案例 | pagerank算法应用案例 | 1.3算法案例 | 算法的概念和案例 | 启发式算法的应用案例 | 遗传算法案例 |