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

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).

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


赞助商链接
相关文章:
算法案例练习(一)
算法案例练习(一)一、选择题(题型注释) 1.十进制数 25 转化为二进制数为( ...退出循环体时 k=4 13.下列各数中,最小的数是( A.75 B. 210( 6) ) ...
§13.2基本算法语句
同系列文档 基本算法语句 算法与程序框图 算法案例 算法初步单元测试...2,S 被赋予 4;第二次循环时,I 被赋予 3,S 被赋予 4+ 错解 =13;第三...
2018最新高中数学必修三练习:1.4 算法案例(2) Word版含...
2018最新高中数学必修三练习:1.4 算法案例(2) Word版含答案 - 1.4 算法案例(2) 【新知导读】 1.欧几里得辗转相除法的思想精髓是什么? 2.什么是更相减损术?...
第13课时5.4.3算法案例三(二分法)已对
第一会所 sis001 www.001dizhi.com 第 13 课时重点难点 5.4 算法案例 重点:...2.能由流程图分析出期所含有的结构并用 为代码表示出相应的算法. 3.GoTo 语句...
13[1].2 基本算法语句
11[1].4 统计案例 12[1].1 随机事件的概率 12[1].3 几何概型 12[1]...2 ?x +1, 10.(13 分)设计算法,根据输入的 x 的值,计算 y=? 2 ?x ...
【高中数学】2018最新高中数学必修三练习:1.4 算法案例(2) Word版...
【高中数学】2018最新高中数学必修三练习:1.4 算法案例(2) Word版含答案_数学_...【随堂演练】 1.整数 143 和 65 的最大公约数为 ( A.13 B.11 C.5 )...
高中数学典型例题解析:第十三章 算法初步
13-1-1 图 13-1-2 二、疑难知识导析 1.“算法“没有一个精确化的...举一形象的例子:有蓝和黑两个墨水瓶,但现在却把蓝墨水装在了黑墨水瓶中,黑...
13.算法及推理与证明
算法案例 算法初步单元测试 1.集合和常用逻辑用语 2.函数和基本函数 3.导数和...13.1 算法与程序框图 46页 5财富值 11.2 用样本估计总体 55页 免费 顺序结构...
13 第十三编 算法初步、推理与证明、复数(共51页)_免费...
1/2 相关文档推荐 课标版2011届高三数学全程... 51页 10财富值 13十三...流程图如下: 方法一 方法二 § 13.2 基本算法语句、算法案例 基础自测 1....
高中数学典型例题解析:第十三章_算法初步
错解:第一步 y?x z?y x?z 第二步 第三步 流程图为 图 13-1-3 错因:未理解赋值的含义,由上面的算法使得 y , z 均取 x 的值. 举一形象的例子:...
更多相关标签: