nbhkdz.com冰点文库

高中数学第一章算法初步第3节算法案例课件新人教A版必修3_图文

时间:

[核心必知] 1.预习教材,问题导入 根据以下提纲,预习教材 P34~P45,回答下列问题. (1)小学学过的求两个正整数的最大公约数的方法 是什么?

提示:先用两个数公有的质因数连续去除,一 直除到所得的商是互质数为止,然后把所有的除数 连乘起来.

(2)辗转相除法的操作步骤是什么?
提示: 两个数中用较大的数除以较小的数, 求得 商和余数,再用除数除以余数,如此重复,直到所得 余数为 0,即可求得两个数的最大公约数.

(3)更相减损术的操作步骤什么?
提示:第一步,任意给定两个正整数,判定它们是 否都是偶数.若是,用 2 约简;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的 差与较小的数比较,并以大数减小数.继续这个操作, 直到所得的数相等为止,则这个数(等数)或这个数与约 简的数的乘积就是所求的最大公约数.

(4)应用秦九韶算法求多项式的值时应怎样操作?
提示:求多项式的值时,先计算最内层括号内一次 多项式的值,即 v1=anx+an-1,再由内向外逐层计算一 次多项式 vk(k=2,3,4,…,n)的值.

(5)将 k 进制数转化为十进制的方法是什么?
提示:“除 k 取余法”.

2.归纳总结,核心必记 (1)辗转相除法与更相减损术 ①辗转相除法:又叫欧几里得算法,是一种求两个正整数 的 最大公约数的古老而有效的算法. ②更相减损术:我国古代数学专著《九章算术》中介绍的 一种求两个正整数的 最大公约数的算法.

(2)秦九韶算法 求多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 的值时, 常用秦九韶算法, 这种算法的运算次数较少, 是多项式求值 比较先进的算法,其实质是转化为求 n 个 一次 多项式的 值,共进行 n 次乘法运算和 n 次加法运算.其过程是:

改写多项式为: f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a1)x+a0 =((anxn-2+an-1xn-3+…+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 .

(3)进位制 ①进位制 进位制是人们为了 计数 和 运算 方便而约定的记数系 统,“满几进一”就是 几进 制, 几进 制的基数就是几 . ②其他进位制与十进制间的转化 (ⅰ)其他进位制化成十进制 其他进位制的数化成十进制时,

不同位上数字与基数的幂的乘积之和的形式. 表示成
(ⅱ)十进制化成 k 进制的方法——“ 除 k 取余法 ”.

[问题思考] (1)辗转相除法与更相减损术有什么联系? 提示:①都是求两个正整数的最大公约数的方法. ②二者的实质都是递推的过程. ③二者都是用循环结构来实现.

(2)辗转相除法与更相减损术有什么区别?
提示: 辗转相除法 更相减损术 ①以减法为主. ①以除法为主. 区 别 ②两个整数差值较大时运 算次数较少. ②两个整数的差值较大时,运 算次数较多. ③相减, 差与减数相等得结果.

③相除余数为零时得结果 ④相减前要做是否都是偶数的 判断

(3)当所给的多项式按 x 的降幂排列“缺项”时,用 秦九韶算法改写多项式时,应注意什么?

提示:所缺的项写成系数为零的形式,即写成 0· xn 的形式.

[课前反思] 通过以上预习,必须掌握的几个知识点: (1)辗转相除法是什么? ; (2)更相减损术是什么? ; (3)秦九韶算法是什么? ; (4)进位制及进位制间的互化: .

观察如图所示的内容:

[思考 1] 辗转相除法的算理是什么?

名师指津:所谓辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数.若余数不为零,则将余数和较 小的数构成新的一对数,继续上面的除法,直到大数被小 数除尽,则这时较小的数就是原来两个数的最大公约数.

[思考 2] 更相减损术的算理是什么? 名师指津:所谓更相减损术,就是对于给定的两个数, 用较大的数减去较小的数,然后将差和较小的数构成新的 一对数,再用较大的数减去较小的数,反复执行此步骤, 直到差数和较小的数相等,此时相等的两数便为原来两个 数的最大公约数.

讲一讲 1.用辗转相除法求 612 与 468 的最大公约数,并 用更相减损术检验所得结果.

[尝试解答] 用辗转相除法: 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.用辗转相除法求 840 与 1 785 的最大公约数;
解:因为 1 785=840×2+105, 840=105×8. 所以 840 和 1 785 的最大公约数是 105.

观察如图所示的内容:

[思考] 秦九韶算法的原理是什么?

名师指津: 秦九韶算法是按从内到外的顺序依次计 算求值的. 设 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 =… =(…((anx+an-1)x+an-2)x+…+a1)x+a0



? ?v0=an, v0 = an , 则 有 公 式 ? ? ?vk= vk-1x+an-k,

其中 k=

1,2,…,n. 这样我们便可由 v0 依次求出 v1, v2,…,vn: v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,…, vn=vn-1x+a0.

讲一讲 2.利用秦九韶算法求多项式 f(x)=x6-5x5+6x4+x2+ 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,即 x=-2 时,多项式的值为 320.

答案:A

利用秦九韶算法计算多项式的值的关键是能正确地将 所给多项式改写,然后由内向外逐次计算,由于后项计算 需用到前项的结果,故应认真、细心,确保中间结果的准 确性.

练一练 2.用秦九韶算法计算多项式 f(x)=12+35x-8x2+6x4 +5x5+3x6 在 x=-4 时的值时,v3 的值为( A.-144 C.-57 B.-136 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.

观察如图所示的内容:

[思考 1] 进位制应如何表示?

名师指津:若一个数为十进制数,其基数可以省略 不写,若是其他进位制,在没有特别说明的前提下,其 基数必须写出,常在数的右下角标明基数.

[思考 2] 常见的进位制有哪些?
名师指津:(1)二进制: ①只使用 0 和 1 两个数字;②满二进一,如 1+1=10(2). (2)八进制: ①使用 0,1,2,3,4,5,6,7 八个不同数字; ②满八进一,如 7+1=10(8); (3)十六进制: ①使用 0,1,2,3,4,5,6,7,8,9,A,B,C, D,E,F 这十六个不 同的数码,其中 A , B , C , D , E , F 分别代表十进制中的 10,11,12,13,14,15; ②满十六进一,如 F+1=2+E=10(16).

讲一讲 3.(1)把二进制数 101 101(2)化为十进制数; (2)把十进制数 458 转化为四进制数.

[尝试解答]

(1)101 101(2)=1×25+0×24+1×23+1×22

+0×21+1×20=32+8+4+1=45, 所以二进制数 101 101(2)转化为十进制数为 45. (2)

458=13 022(4).

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

练一练 3.(1)二进制数算式 1 010(2)+10(2)的值是( A.1 011(2) C.1 101(2) B.1 100(2) D.1 000(2) ) )

(2)下列各组数中最小的数是( A.1 111(2) C.1 000(4) B.210(6) D.101(8)

解析:(1)选 B 二进制数的加法是逢二进一, 所以选 B.
(2)选 A 统一化为十进制数为 1 111(2)=15; 210(6)=78;1 000(4)=64;101(8)=65.

———————[课堂归纳· 感悟提升]——————— 1.本节课的重点是会用辗转相除法与更相减损术求两个 数的最大公约数,会用秦九韶算法求多项式的值,会在不同进 位制间进行相互转化.难点是会用秦九韶算法求多项式的值. 2.本节课要掌握以下几类问题: (1)掌握求最大公约数的两种方法步骤,见讲 1. (2)掌握秦九韶算法步骤,见讲 2. (3)进位制的转换方法,见讲 3.

3.本节课的易错点有两个: (1)弄不清秦九韶算法的原理而致错,如讲 2; (2)进位制之间转换的方法混淆而致错,如讲 3.