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

创新设计2016


第一章 算法初步

1.3 算法案例

学习 目标

1.理解辗转相除法与更相减损术的含义,了解其执行过程. 2.理解秦九韶算法的计算过程,并了解它提高计算效率的实质. 3.理解进位制的概念,能进行不同进位制间的转化. 4.了解进位制的程序框图和程序.

栏目 索引

知识梳理 题型探究 当堂检测

自主学习
重点突破

自查自纠

知识梳理

自主学习

知识点一

辗转相除法与更相减损术

1.辗转相除法
(1)辗转相除法,又叫欧几里得算法,是一种求两个正整数的 最大公约数 的

古老而有效的算法.
(2)辗转相除法的算法步骤

第一步,给定两个正整数m,n .
第二步,计算 m除以n所得的余数r .

第三步, m=n,n=r .
第四步,若r=0,则m,n的最大公约数等于 m ;否则,返回 第二步 .
答案

2.更相减损术
第一步,任意给定两个正整数,判断它们是否都是偶数 .若是,用 2 约

简;若不是,执行 第二步 .
第二步,以 较大的数减去 较小 的数,接着把所得的差与 较小 的数比较,

并以大数减小数.继续这个操作,直到所得的数相等 为止,则这个数(等
数)或这个数与约简的数的乘积就是所求的最大公约数.

答案

3.辗转相除法和更相减损术的区别与联系: 名称 辗转相除法 (1)以除法为主; 区别 时,运算次数较少; 结果 更相减损术 (1)以减法为主; 较多; (4)相减前要进行是否都是偶数的判断

(2)两个整数的差值较大 (2)两个整数的差值较大时,运算次数 (3)相除,余数为0时得 (3)相减,减数与差相等时得结果; (1)都是求两个正整数最大公约数的方法; 联系 (2)二者的实质都是递归的过程; (3)二者都要用循环结构来实现

思考

实际应用更相减损术时要做的第一步工作是什么?

答 先判断a,b是否为偶数,若是,都除以2再进行.

答案

知识点二

秦九韶算法

1.秦九韶算法简介 (1)秦九韶算法要解决的问题是求多项式的值. (2)秦九韶算法的特点: 通过一次式的反复计算,逐步得到高次多项式的值,即将一个n次多项 式的求值问题归结为重复计算n个一次多项式的值的问题.

(3)秦九韶算法的原理: 将f(x)=anxn+an-1xn-1+?+a1x+a0改写为: f(x)=(anxn-1+an-1xn-2+?+a1)x+a0 =((anxn-2+an-1xn-3+?+a2)x+a1)x+a0 =?

先计算最内层括号内一次多项式的值,即v1=anx+an-1,再由内向外 逐层计算一次多项式vk的值.

2.秦九韶算法的操作方法

(1)算法步骤如下:
第一步,输入多项式次数n、最高次项的系数an和x的值.

第二步,将v的值初始化为an,将i的值初始化为n-1.
第三步,输入i次项的系数ai.

第四步,v=vx+ai,i=i-1.
第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多

项式的值v.

(2)程序框图如图所示.

(3)程序如下:
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.进位制的概念 进位制是为了计数和运算方便而约定的记数系统,约定“满几进一”

就是几进制,几进制的基数(大于1的整数)就是几.
2.常见的进位制 (1)二进制: ①只使用0和1两个数学; ②满二进一,即1+1=10(2). (2)八进制; ①使用0,1,2,3,4,5,6,7这八个不同数学; ②满八进一,即7+1=10(8).

思考

任何进位制中都要用到的数字是什么?

答 0和1.

答案

返回

题型探究

重点突破

题型一

求两个正整数的最大公约数

例1 分别用辗转相除法和更相减损术求261和319的最大公约数. 方法二 (更相减损术) 解 方法一 (辗转相除法) 319÷261=1(余58), 261÷58=4(余29), 58÷29=2(余0), 所以319与261的最大公约数为29.

319-261=58,
261-58=203, 203-58=145, 145-58=87, 87-58=29,

58-29=29,
29-29=0, 所以319与261的最大公约数是29.
反思与感悟 解析答案

跟踪训练1

用辗转相除法求80与36的最大公约数,并用更相减损术检

验你的结果.
解 80=36×2+8,36=8×4+4,8=4×2+0, 即80与36的最大公约数是4. 验证: 80÷2=40,36÷2=18;40÷2=20,18÷2=9; 20—9=11,11-9=2;9-2=7,7-2=5; 5-2=3,3-2=1;2-1=1,1×2×2=4; 所以80与36的最大公约数为4.
解析答案

题型二 秦九韶算法的应用
例2 解 用秦九韶算法求多项式f(x)=x5+5x4+10x3+10x2+5x+1当x=-2 f(x)=x5+5x4+10x3+10x2+5x+1=((((x+5)x+10)x+10)x+5)x+1. 时的值. 当x=-2时,有v0=1; v1=v0x+a4=1×(-2)+5=3; v2=v1x+a3=3×(-2)+10=4; v3=v2x+a2=4×(-2)+10=2; v4=v3x+a1=2×(-2)+5=1;

v5=v4x+a0=1×(-2)+1=-1.
故f(-2)=-1.
反思与感悟 解析答案

跟踪训练 2 解

用秦九韶算法计算多项式 f(x) = x6 - 12x5 + 60x4 - 160x3 +

240x2-192x+64当x=2时的值. 根据秦九韶算法,把多项式改写成如下形式: f(x)=(((((x-12)x+60)x-160)x+240)x-192)x+64. 由内向外依次计算一次多项式当x=2时的值; v0=1; v2=-10×2+60=40; v4=-80×2+240=80; v6=-32×2+64=0. 所以当x=2时,多项式的值为0.
解析答案

v1=1×2-12=-10; v3=40×2-160=-80; v5=80×2-192=-32;

题型三

进位制之间的互化

例3 (1)把二进制数1110011(2)化为十进制数. 解 1110011(2)=1×26+1×25+1×24+0×23+0×22+1×21+1=115.

(2)将8进制数314706(8)化为十进制数. 解 314706(8)=3×85+1×84+4×83+7×82+0×81+6×80=104902.
所以,化为十进制数是104902.

反思与感悟

解析答案

跟踪训练3 解

将53(8)转化为二进制数.

先将八进制数53(8)转化为十进制数:

53(8)=5×81+3×80=43; 再将十进制数43转化为二进制数:

所以53(8)=101011(2).
解析答案

思想方法

转化与化归思想

例4 下列各数中,最小的数是( D ) A.85(9) 分析 B.210(6) C.1000(4) D.111111(2)

先将它们转化为十进制数,再进行比较.

解析 85(9)=8×9+5=77,
210(6)=2×62+1×6+0=78,

1000(4)=1×43=64,
111111(2)=1×25+1×24+1×23+1×22+1×2+1=63.

故最小的是63.
分析 解后反思 解析答案

易错点

数制转化方法掌握不牢致错 对进位制间的换算,要弄清解题的办法,将十进制数转化为k进

例5 把十字进制数49化为二进制数. 分析 制数用“除k取余法”.



所以49=110 001(2).

解后反思

本例常出现的错误是把上式中各步所得的余数从上到下排
分析 解后反思 解析答案 返回

列,这是基本方法掌握不牢造成的,应加以注意.

当堂检测

1

2

3

4

5

1.1 337与382的最大公约数是( C ) A.3 解析 B.382 C.191 D.201

利用辗转相除法,1 337=382×3+191,382=191×2,

故两数的最大公约数为191.

解析答案

1

2

3

4

5

2.把189化为三进制数,则末位数字是( A ) A.0 B.1 C.2 D.3

解析 采用“除k取余法”,得

即189=21 000(3)

解析答案

1

2

3

4

5

3.用秦九韶算法求n次多项式f(x)=anxn+an-1xn-1+?+a1x+a0当x=x0 时的值,求f(x0)需要乘方、乘法、加法的次数分别为( D )
n?n+1? A. ,n,n 2 C.0,2n,n

B.n,2n,n D.0,n,n

解析 因为f(x)=(?((anx+an-1)x+an-2)x+?+a1)x+a0,
所以乘方、乘法、加法的次数分别为0,n,n.

解析答案

1

2

3

4

5

4.用秦九韶算法求多项式f(x)=7x6+6x5+3x2+2,当x=4时的值时,先

算的是( D )
A.4×4=16 B.7×4=28

C.4×4×4=64
解析

D.7×4+6=34

因为f(x)=anxn+an-1xn-1+?+a1x+a0

=(?((anx+an-1)x+an-2)x+?+a1)x+a0,
所以用秦九韶算法求多项式f(x)=7x6+6x5+3x2+2当x=4时的值时,先

算的是7×4+6=34.
解析答案

1

2

3

4

5

先除以2,得到 5.用更相减损术求36与134的最大公约数,第一步应为______________
18与67 ________. 解析 ∵36与134都是偶数,

∴第一步应为:先除以2,得到18与67.

解析答案

课堂小结 1.求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相 减损术.用辗转相除法,即根据a=nb+r这个式子,反复相除,直到r=0为 止;用更相减损术,即根据r=|a-b|这个式子,反复相减,直到r=0为止. 2.秦九韶算法的关键在于把n次多项式转化为一次多项式,注意体会递推的 实现过程,实施运算时要由内向外,一步一步执行. 3.把一个非十进制数转化为另一种非十进制数,通常是把这个数先转化为 十进制数,然后再利用除k取余法,把十进制数转化为k进制数.而在使用除 k取余法时要注意以下几点:(1)必须除到所得的商是0为止;(2)各步所得的 余数必须从下到上排列;(3)切记在所求数的右下角标明基数.
返回


赞助商链接
相关文章:
创新设计2016二轮语文全国通用专题复习保温练18.doc
创新设计2016二轮语文全国通用专题复习保温练18.doc - 保温练 18 一、语言文字运用 语言文字运用+名句默写+文学类文本阅读(四) ) 1.依次填入下列各句横线处的...
智慧树创新工程实践2016章节测试答案
智慧树创新工程实践2016章节测试答案 - 创新设计思维 1 创新设计思维是 正确答案是:前三者都是 2 创新设计思维具有三大步骤,下面哪一个不属于三大步骤 正确答案是...
创新设计2016届历史专题通关练习 经典提升 选修五、选...
创新设计2016届历史专题通关练习 经典提升 选修五、选修六.doc_政史地_高中教育_教育专区。选修五 选修六 探索历史的奥秘 世界文化遗产荟萃 1.(2015· 江苏单科,...
创新设计2016届历史专题通关练习测评实力综合卷(一).doc
创新设计2016届历史专题通关练习测评实力综合卷(一).doc - 第四部分 测评实力综合卷 测评实力综合卷(一) (时间:90 分钟 分值:150 分) 一、选择题(本大题共...
创新设计2016_2017学年高中数学综合检测一
创新设计2016_2017学年高中数学综合检测一 - 综合检测(一) 一、选择题(本大题共 12 小题,每小题 5 分,共 60 分) 1-3i 1.i 是虚数单位,复数 的共轭...
创新设计2016届历史专题通关练习 测评实力综合卷(三).doc
创新设计2016届历史专题通关练习 测评实力综合卷(三).doc - 测评实力综合卷(三) (时间:90 分钟 分值:150 分) 一、选择题(本大题共 25 小题,每小题 3 ...
创新设计2016届历史专题通关练习测评实力综合卷(三).doc
创新设计2016届历史专题通关练习测评实力综合卷(三).doc - 测评实力综合卷(三) (时间:90 分钟 分值:150 分) 一、选择题(本大题共 25 小题,每小题 3 分...
2016年化学实验能力与创新设计竞赛_图文
2016年化学实验能力与创新设计竞赛 - 2016年“化学实验能力与创新设计”竞赛 活动的通知(讨论稿) 伊犁哈萨克自治州教育学会,各地(州、市)教育学会、中学化学教学 ...
2016-2017《创新设计》同步人教A版选修2-3第一章 1.1(一)
2016-2017《创新设计》同步人教A版选修2-3第一章 1.1(一) - [学习目标] 1.理解分类加法计数原理与分步乘法计数原理 .2.会用这两个原理分析和解决一 些...
《创新设计》2016年高考物理一轮复习WORD版训练1-2-1.doc
创新设计2016年高考物理一轮复习WORD版训练1-2-1.doc - 第二章 相互作用 第 1 课时 重力、弹力 基本技能练 1.如图 1 所示,两辆车在以相同的速度做...
更多相关标签: