2015-2016学年高中数学 1.3第1课时辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修3

2．秦九韶算法 (1)概念：求多项式f(x)＝anxn＋an－1xn－1＋„＋a1x＋a0的值
时，常用秦九韶算法，这种算法的运算次数较少，是多项式求
一次 多项式的 值比较先进的算法，其实质是转化为求 n 个 ______ n 次乘法运算和___ n 次加法运算．其过程是： 值，共进行___
改写多项式为：
4 ．用更相减损术求 294 和 84 的最大公约数时，第一步是
________． [答案] 用2约简 [解析] 由于294和85·云南省景洪一中月考 )用秦九韶算法计算多项式 f(x)＝3x6＋2x5＋4x4＋5x3＋7x2＋8x＋1在x＝0.5时的值，需做乘
●预习自测 1 ． 用 辗 转相 除 法 求 36 与 134 的最 大 公 约数 ， 第 一步 是
( ) A．134－36＝98 B．134＝36×3＋26 C．先除以2，得到18与67 D．36＝26×1＋10 [答案] B [解析] 求36与134的最大公约数，第一步是134＝36×3＋
26，第二步是36＝26×1＋10，故选D.
头 35 头 35 以下减上 35 以上减下 23 ( )―→( ) ――→ ( ) ――→ ( )．上 脚 94 脚 47 对 12 12 为鸡数，下为兔数． 当然也可以假设笼子里的返回物都是鸡(兔)， 那么多(少) 出的脚数除以 2 即为兔子(鸡)数，这就是“寓理于算”的方 法．如果用二元一次方程组求解，也会非常方便地解决．
(3)程序框图如图所示．
(4)程序：
INPUT INPUT INPUT v＝a “n＝”；n “an＝”；a “x＝”；x
i＝n－1
WHILE PRINT INPUT i>＝0 ___________ “i＝”；i “ai＝”；a
v*x＋a v＝_________ i＝i－1 WEND v PRINT ___ END
法和加法的次数分别是________．
[答案] 6次乘法，6次加法 [解析] 法． 将多项式改写为 f(x)＝(((((3x＋2)x＋4)x＋5)x＋7)x ＋ 8)x ＋ 1 ，化为 6 个一次因式求解，故只做了 6 次乘法和 6 次加
高效课堂
●互动探究
辗转相除法和更相减损术的应用
用辗转相除法求 80和36 的最大公约数，并用更
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. anx＋an－1 ， 设v ＝____________
n＝r
r＝0 LOOP UNTIL _______ PRINT END m ___
(2)更相减损术．
算法步骤： 第一步，任意给定两个正整数，判断它们是否都是 2 约简；若不是，执行第二步． 偶数 ．若是，用___ ______ 减 去较小的数，接着把所得的差与 第二步，以较大的数 ___ 大 数减___ 小 数．继续这个操作，直到所得 较小的数比较，并以___ 的差与减数相等为止，则这个数(等数)或这个数与约简的数的 乘积就是所求的最大公约数．
80－36＝44， 44－36＝8， 36－8＝28， 28－8＝20，
20－8＝12，
12－8＝4， 8－4＝4. 故80和36的最大公约数是4.
相减损术检验所得结果． [探究] 1.辗转相除法与更相减损术的主要区别是什么？ 2 ．将 80 作为大数， 36 作为小数，执行辗转相除法和更相 减损术的步骤即可．
[解析] 用辗转相除法： 80＝36×2＋8， 36＝8×4＋4， 8＝4×2＋0. 故80和36的最大公约数是4.
用更相减损术检验：
2．(2015·河北省廊坊一中月考)用辗转相除法求294和84的
最大公约数时，需要做除法的次数是( A．1 C．3 [答案] B B．2 D．4 )
[解析]
本题考查辗转相除法的过程.294＝84×3＋42,84＝
42×2，故选B.
3 ．设计程序框图，用秦九韶算法求多项式的值，所选用
的结构是( ) B．条件结构 D．以上都有 A．顺序结构 C．循环结构 [答案] D
1
v2＝v1x＋an－2， v3＝v2x＋an－3， „， vn－1x＋a0 vn＝___________.
(2)算法步骤：
第一步，输入多项式的次数 n 、最高次项的系数 an 和 x 的 值． 第二步，将v的值初始化为an，将i的值初始化为n－1. 第三步，输入i次项的系数ai. i－1 第四步，v＝vx＋ai，i＝________. 0 若是，则返回第三步； 第五步，判断i是否大于或等于___. v 否则，输出多项式的值___.
成才之路 ·数学
人教A版 ·必修3
路漫漫其修远兮 吾将上下而求索
第一章
算法初步
第一章
1.3 算法案例 第1课时 辗转相除法与更相减损 术、秦九韶算法
1
优 效 预 习
3
当 堂 检 测
2
高 效 课 堂
4
课 时 作 业
优效预习
●知识衔接 鸡兔同笼问题是中国古代数学名著《孙子算法》中的一道
名题，题目是这样的：“今有鸡兔同笼，上有三十五头，下有 九十四足，问鸡兔各几何？”书中给出的解法是：鸡有两只 脚，兔有四只脚，把脚数除以 2 ，共有 47 对脚．由于鸡有 1 对 脚，兔有2 对脚，所以从 47 中减去 25 ，得 12即为兔子数．因为 如要笼子里的动物每只都只有 1对脚，就会多出 12对脚来，把 这12对脚分别加到有 2对脚的动物身上，就有 12 只脚动物，即 兔子数．整个解题过程可以简单地写作：
●自主预习 1．辗转相除法与更相减损术
(1)辗转相除法． ①算法步骤： 第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数r. 第三步，m＝n，n＝r. 0 ，则m，n的最大公约数等于m；否则返 第四步，若r＝___ 二 步． 回 第___
②程序框图如图所示．
③程序：
INPUT DO r＝m MOD m＝n n m，n