nbhkdz.com冰点文库

2016年高中数学 第一章 算法初步 1.3算法案例学案 新人教A版必修3

时间:


1.3

算法案例

1.问题导航 (1)什么叫辗转相除法? (2)什么叫更相减损术? (3)辗转相除法与更相减损术的区别是什么? (4)什么是秦九韶算法? (5)学习了十进制,知道十进制是使用 0~9 十个数字,那么二进制、五进制、七进制分 别使用哪些数字? 2.例题导读 通过对例 1 的学习,学会用更相减损术求最大公约数; 通过对例 2

的学习,学会用秦九韶算法求多项式的值; 通过对例 3 的学习,学会如何将二进制化为十进制; 通过对例 4 的学习,学会如何将 k 进制化为十进制; 通过对例 5 的学习,学会如何将十进制化为二进制; 通过对例 6 的学习,学会十进制化为 k 进制的方法:即“除 k 取余法”(k∈N,2≤k≤9).

1.辗转相除法与更相减损术 (1)辗转相除法:又叫欧几里得算法,是一种求两个正整数的最大公约数的古老而有效的 算法. (2)更相减损术:我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约 数的算法. 2.秦九韶算法 功能 它是一种用于计算一元 n 次多项式的值的方 法

改写后的形式

f(x)=anxn+an-1xn-1+?+a1x+a0 n-1 n-2 =(anx +an-1x +?+a1)x+a0 n-2 n-3 =((anx +an-1x +?+a2)x+a1)x+a0
=? =(?((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,
-1-

计算方法

? 这样,求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值. 3.进位制 (1)进位制 进位制是人们为了计数和运算方便而约定的记数系统, “满几进一”就是几进制,几进制 的基数就是几. (2)其他进位制与十进制间的转化 ①其他进位制化成十进制 其他进位制的数化成十进制时,表示成不同位上数字与基数的幂的乘积之和的形式. ②十进制化成 k 进制的方法——“除 k 取余法”.

1.用更相减损术求 294 和 84 的最大公约数时,需做减法运算的次数是( ) A.2 B.3 C.4 D.5 解析:选 C.294-84=210,210-84=126,126-84=42,84-42=42,共做 4 次减法运 算. 6 5 4 3 2 2. 用秦九韶算法计算多项式 f(x)=3x +4x +5x +6x +7x +8x+1 当 x=0.4 时的值时, 需要做乘法和加法的次数分别是( ) A.6,6 B.5,6 C.5,5 D.6,5 答案:A 3.完成下列进位制之间的转化. (1)1 034(7)=________(10); (2)119(10)=________(6). 3 2 0 解析:(1)1 034(7)=1×7 +0×7 +3×7+4×7 =368.

(2) ∴119(10)=315(6). 答案:(1)368 (2)315 4.当所给的多项式按 x 的降幂排列“缺项”时,用秦九韶算法改写多项式时,应注意什 么? n 解:所缺的项写成系数为零的形式,即写成 0·x 的形式.

1.对于任何一个数,我们可以用不同的进位制来表示. 2.表示各种进位制数一般在数字右下角加注来表示,如 111 001(2)表示二进制数,34(5) 表示 5 进制数. 3.电子计算机一般都使用二进制. 4.利用除 k 取余法,可以把任何一个十进制数化为 k 进制数,并且操作简单、实用. 5.通过 k 进制数与十进制数的转化,我们也可以将一个 k 进制数转化为另一个不同基数 的 M 进制数.
-2-

6.利用秦九韶算法可以减少计算次数提高计算效率.

求最大公约数 用辗转相除法求 612 与 468 的最大公约数,并用更相减损术检验所得结果. (链接教材 P36 例 1) [解] 用辗转相除法: 612=468×1+144,468=144×3+36,144=36×4, 即 612 和 468 的最大公约数是 36. 用更相减损术检验: 612 和 468 为偶数,两次用 2 约简得 153 和 117,153-117=36,117-36=81,81-36 =45,45-36=9,36-9=27,27-9=18,18-9=9, 所以 612 和 468 的最大公约数为 9×2×2=36. 方法归纳 (1)利用辗转相除法求给定的两个数的最大公约数,即利用带余除法,用数对中较大的数 除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到 大数被小数除尽,则这时的较小数就是原来两个数的最大公约数. (2)利用更相减损术求两个正整数的最大公约数的一般步骤是:首先判断两个正整数是否 都是偶数.若是,用 2 约简,也可以不除以 2,直接求最大公约数,这样不影响最后结果.

1.(1)1 624 与 899 的最大公约数是________. 解析:1 624=899×1+725, 899=725×1+174, 725=174×4+29, 174=29×6, 故 1 624 与 899 的最大公约数是 29. 答案:29 (2)用辗转相除法求 80 和 36 的最大公约数,并用更相减损术检验所得结果. 解:辗转相除法: 80=36×2+8,36=8×4+4,8=4×2+0. 故 80 和 36 的最大公约数是 4. 用更相减损术检验: 80-36=44, 44-36=8, 36-8=28,

-3-

28-8=20, 20-8=12, 12-8=4, 8-4=4, ∴80 和 36 的最大公约数是 4.

秦九韶算法及其应用 (2015·福州高一检测)用秦九韶算法写出当 x=3 时 f(x)=2x -4x +3x -5x+1 的值. [解] ∵f(x)=((((2x+0)x-4)x+3)x-5)x+1, v0=2, v1=2×3+0=6, v2=6×3-4=14, v3=14×3+3=45, v4=45×3-5=130, v5=130×3+1=391, 所以 f(3)=391. 方法归纳 利用秦九韶算法将 f(x)改写成如下形式 f(x)=(?((anx+an-1)x+an-2)x+?+a1)x+a0, 其计算步骤为:先计算 v1=anx+an-1,再计算 v2=v1x+an-2,每次都是把上一次的结果乘以 x 再与下一个系数相加,其计算量为乘法 n 次,加法 n 次.
5 3 2

2.利用秦九韶算法求多项式 f(x)=3x +12x +8x -3.5x +7.2x +5x-13 当 x=6 时的 值,写出详细步骤. 解:f(x)=(((((3x+12)x+8)x-3.5)x+7.2)x+5)x-13. v0=3, v1=v0×6+12=30, v2=v1×6+8=188, v3=v2×6-3.5=1 124.5, v4=v3×6+7.2=6 754.2, v5=v4×6+5=40 530.2, v6=v5×6-13=243 168.2. 所以 f(6)=243 168.2.

6

5

4

3

2

进位制 (1)把二进制数 101 101(2)化为十进制数; (2)把十进制数 458 转化为四进制数. (链接教材 P41 例 3、例 4) 5 4 3 2 1 0 [解] (1)101 101(2)=1×2 +0×2 +1×2 +1×2 +0×2 +1×2 =32+8+4+1=45, 所以二进制数 101 101(2)转化为十进制数为 45.

-4-

(2)

458=13 022(4). [互动探究] 将本例(1)中的二进制数 101 101(2)转化为三进制数. 5 4 3 2 1 0 解:101 101(2)=1×2 +0×2 +1×2 +1×2 +0×2 +1×2 =45,

∴45=1 200(3),∴101 101(2)=1 200(3). 方法归纳 (1)将 k 进制转化为十进制的方法是:先将这个 k 进制数写成各个数位上的数字与 k 的幂 的乘积之和的形式,再按照十进制的运算规则计算出结果.(2)十进制转化为 k 进制,采用除 k 取余法,也就是除基数,倒取余.

3.(1)二进制数算式 1 010(2)+10(2)的值是( ) A.1 011(2) B.1 100(2) C.1 101(2) D.1 000(2) 解析:选 B.二进制数的加法是逢二进一,所以选 B. (2)下列各组数中最小的数是( ) A.1 111(2) B.210(6) C.1 000(4) D.101(8) 解析:选 A.统一化为十进制数为 1 111(2)=15;210(6)=78;1 000(4)=64;101(8)=65.

易错警示 (

因忽略零系数项而致误
6 5 4 2

利用秦九韶算法求多项式 f(x) = x - 5x + 6x + x + 3x + 2 当 x =- 2 时的值为 ) A.320 B.-160 C.-320 D.300 [解析] 将多项式变式为 f(x)=(((((x-5)x+6)x+0)x+1)x+3)x+2,v0=1,v1=-2 +(-5)=-7, v2=-7×(-2)+6=20, v3=20×(-2)+0=-40, v4=-40×(-2)+1=81, v5=81×(-2)+3=-159,v6=-159×(-2)+2=320. [答案] A [错因与防范] (1)考虑 x=-2 而认为多项式的值为负值. (2)易忽略多项式中系数为 0 的项,致使多项式改写不正确.
-5-

(3)解题时注意多项式变形后有几次乘法和几次加法. (4)要注意所给多项式的项数,特别是系数为 0 的项.

4. (1)用秦九韶算法计算多项式 f(x)=12+35x-8x +6x +5x +3x 在 x=-4 时的值时, v3 的值为( ) A.-144 B.-136 C.-57 D.34 解析:选 B.根据秦九韶算法多项式可化为 f(x)=(((((3x+5)x+6)x+0)x-8)x+35)x+12. 由内向外计算 v0=3; v1=3×(-4)+5=-7; v2=-7×(-4)+6=34; v3=34×(-4)+0=-136. 5 4 3 2 (2)已知多项式 f(x)=3x +8x -3x +5x +12x-6,则 f(2)=________. 解析:根据秦九韶算法,把多项式改写成如下形式: f(x)=((((3x+8)x-3)x+5)x+12)x-6. 按照从内到外的顺序,依次计算一次多项式当 x=2 时的值. v0=3, v1=3×2+8=14, v2=14×2-3=25, v3=25×2+5=55, v4=55×2+12=122, v5=122×2-6=238, 所以当 x=2 时,多项式的值为 238. 答案:238

2

4

5

6

1.下列关于利用更相减损术求 156 和 72 的最大公约数的说法中正确的是( ) A.都是偶数必须约简 B.可以约简,也可以不约简 C.第一步作差为 156-72=84;第二步作差为 72-84=-12 D.以上都不对 解析:选 B.约简是为了使运算更加简捷,故不一定要约简,A 错.C 中第二步应为 84- 72=12,故选 B. 2.用辗转相除法计算 294 与 84 的最大公约数时,需要做的除法次数是( ) A.1 B.2 C.3 D.4 解析:选 B.294=84×3+42,84=42×2,至此公约数已求出. 3.二进制数 1 101 111(2)化成十进制数是________. 0 1 2 3 4 5 6 解析:1 101 111(2)=1×2 +1×2 +1×2 +1×2 +0×2 +1×2 +1×2 =111. 答案:111 4.若 k 进制数 123(k)与十进制数 38 相等,则 k=________. 解析:由 k 进制数 123 可知 k≥4.

-6-

下面可用验证法: 若 k=4,则 38(10)=212(4),不合题意; 若 k=5,则 38(10)=123(5)成立,所以 k=5. 答案:5

[A.基础达标] 1.45 和 150 的最大公约数和最小公倍数分别是( ) A.5,150 B.15,450 C.450,15 D.15,150 解析:选 B.利用辗转相除法求 45 和 150 的最大公约数:150=45×3+15,45=15×3, 45 和 150 的最大公约数为 15.45 和 150 的最小公倍数为 15×(45÷15)×(150÷15)=450,故 选 B. 2.把 67 化为二进制数为( ) A.1 100 001(2) B.1 000 011(2) C.110 000(2) D.1 000 111(2) 解析:选 B.

∴把 67 化为二进制数为 1 000 011(2). 3.(2015·三明高一检测)计算机中常用十六进制,采用数字 0~9 和字母 A~F 共 16 个 计算符号与十进制的对应关系如下表: 十 六 进 制 十 进 制

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

例如用十六进制表示 D+E=1B,则(2×F+1)×4=( ) A.6E B.7C C.5F D.B0 解析: 选 B.(2×F+1)×4 用十进制可以表示为(2×15+1)×4=124, 而 124=16×7+12, 所以用十六进制表示为 7C,故选 B. 5 2 4.若用秦九韶算法求多项式 f(x)=4x -x +2 当 x=3 时的值,则需要做乘法运算和加减 法运算的次数分别为( ) A.4,2 B.5,3 C.5,2 D.6,2
-7-

解析:选 C.f(x)=4x -x +2=((((4x)x)x-1)x)x+2,所以需要做 5 次乘法运算和 2 次 加减运算. 5.(2015·青海调研)已知一个 k 进制的数 132 与十进制的数 30 相等,那么 k 等于( ) A.7 或 4 B.-7 C.4 D.都不对 2 2 解析:选 C.132(k)=1×k +3×k+2=k +3k+2, 2 2 ∴k +3k+2=30,即 k +3k-28=0, 解得 k=4 或 k=-7(舍去). 6.三个数 72,120,168 的最大公约数是________. 解析:由更相减损术,得 168-120=48,120-48=72,72-48=24,48-24=24, 故 120 和 168 的最大公约数是 24. 而 72-24=48,48-24=24, 故 72 和 24 的最大公约数也是 24, 所以 72,120,168 的最大公约数是 24. 答案:24 3 2 7.(2015·莱芜质检 ) 已知函数 f(x) = x - 2x - 5x + 6 ,用秦九韶算法,则 f(10) = ________. 3 2 解析:f(x)=x -2x -5x+6 2 =(x -2x-5)x+6 =((x-2)x-5)x+6. 当 x=10 时, f(10)=((10-2)×10-5)×10+6 =(8×10-5)×10+6 =75×10+6=756. 答案:756 8.(2015·福州高一检测)三进制数 2022(3)化为六进制数为 abc(6), 则 a+b+c=________. 3 2 1 0 解析:2 022(3)=2×3 +0×3 +2×3 +2×3 =62.

5

2

三进制数 2022(3)化为六进制数为 142(6), ∴a+b+c=7. 答案:7 3 2 9.已知函数 f(x)=x -3x -4x+5,试用秦九韶算法求 f(2)的值. 解:根据秦九韶算法,把多项式改写成如下形式: f(x)=x3-3x2-4x+5 2 =(x -3x-4)x+5 =((x-3)x-4)x+5. 把 x=2 代入函数式得 f(2)=((2-3)×2-4)×2+5=-7. 10.古时候,当边境有敌人来犯时,守边的官兵通过在烽火台上点火向境内报告来犯敌人

-8-

数,如图所示,烽火台上点火表示数字 1,未点火表示数字 0,约定二进制数对应的十进制数 的单位是 1 000,请你计算一下,这组烽火台表示有多少敌人入侵?

解:由题图可知这组烽火台表示的二进制数为 11 011(2),它表示的十进制数为 11 011(2) 4 3 2 1 0 =1×2 +1×2 +0×2 +1×2 +1×2 = 27 ,由于约定二进制数对应的十进制数的单位是 1 000,所以入侵的敌人的数目为 27×1 000=27 000(人). [B.能力提升] 1.将十进制数 389 化成四进制数的末位是 ( ) A.1 B.2 C.3 D.0 解析:选 A.389=4×97+1,即第一次用 389 除以 4 余 1,而这就是最后一位数字. 2.(2015·盐城质检)m 是一个正整数,对于两个正整数 a,b,如果 a-b 是 m 的倍数, 则称 a,b 对模 m 同余,用符号 a≡b(Mod m)表示,则下列各式中不正确的为( ) A.12≡7(Mod 5) B.21≡10(Mod 3) C.34≡20(Mod 2) D.47≡7(Mod 40) 解析:选 B.逐一验证,对于 A,12-7=5 是 5 的倍数;对于 B,21-10=11 不是 3 的倍 数;对于 C,34-20=14 是 2 的倍数;对于 D,47-7=40 是 40 的倍数,故选 B. 3.324,243,135 三个数的最大公约数是________. 解析:324=243×1+81, 243=81×3, 所以 243 与 324 的最大公约数是 81. 又 135=81×1+54, 81=54×1+27, 54=27×2+0, 所以 135 与 81 的最大公约数是 27. 答案:27 4.在计算机的运行过程中,常常要进行二进制数与十进制数的转换与计算.如十进制数 8 转换成二进制数是 1 000,记作 8(10)=1 000(2);二进制数 111 转换成十进制数是 7,记作 111(2) =7(10)等.二进制的四则运算,如 11(2)+101(2)=1 000(2).请计算:11(2)×111(2)=________,10 101(2)+1 111(2)=________. 解析:由题可知,在二进制数中的运算规律是“满二进一”, ∴11(2)×111(2)=10 101(2), 10 101(2)+1 111(2)=100 100(2). 答案:10 101(2) 100 100(2) 5.有甲、乙、丙三种溶液分别重 147 g、343 g、133 g,现要将它们分别全部装入小瓶 中,每个小瓶装入液体的质量相同,问每瓶最多装多少? 解:先求 147 与 343 的最大公约数. 343-147=196, 196-147=49, 147-49=98, 98-49=49.

-9-

所以 147 与 343 的最大公约数是 49. 再求 49 与 133 的最大公约数. 133-49=84, 84-49=35, 49-35=14, 35-14=21, 21-14=7, 14-7=7. 所以 147,343,133 的最大公约数为 7. 所以每瓶最多装 7 g. 6.(选做题)已知 175(r)=125(10),求在这种进制里的数 76(r)应记成十进制的什么数? 2 1 0 解:∵1×r +7×r +5×r =125, 2 ∴r +7r-120=0, ∴r=8 或 r=-15(舍去), ∴r=8. 1 0 76(r)=76(8)=7×8 +6×8 =62(10).

- 10 -


...数学高一必修3第一章算法初步1.3人教A版

算法案例 辗转相除法与更相减损术秦九韶算法与进位制第1课时练习-数学高一必修3第一章算法初步1.3人教A版_数学_高中教育_教育专区。人教 A 版 第一章 1.3 ...

人教A版高中数学必修三1.1.1《算法的概念》导学案2

人教A版高中数学必修三1.1.1《算法的概念》导学案2_教学案例/设计_教学研究_教育专区。第一章 算法初步 §1.1.1 算法的概念 目标 1.了解算法 的含义,体会...