步步高必修3高中数学2019年复习资料第一章 1.3（一）

§1.3 算法案例(一)

学习目标 1.了解辗转相除法与更相减损术中的数学原理,并能根据这些原理进行算法分析.2.了解秦九韶算法及利用它提高计算效率的本质.3.对简单的案例能设计程序框图并写出算法程序.

知识点一 求两个数的最大公约数的算法

思考 注意到8 251＝6 105×1＋2 146,那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？

答案 显然8 251与6 105的公约数也必是2 146的约数,同样6 105与2 146的公约数也必是8 251的约数,所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数. 梳理 求两个数的最大公约数有2种算法： (1)辗转相除法

①辗转相除法,又叫欧几里得算法,是一种求两个正整数的最大公约数的古老而有效的算法. ②辗转相除法的算法步骤 第一步,给定两个正整数m,n. 第二步,计算m除以n所得的余数r. 第三步,m＝n,n＝r.

第四步,若r＝0,则m,n的最大公约数等于m; 否则,返回第二步. (2)更相减损术的运算步骤

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

知识点二 求n次多项式f(x)＝anxn＋an－1xn1＋…＋a1x＋a0的值的算法

－

求n次多项式的值的算法,有一种比较好的算法叫秦九韶算法. 秦九韶算法的一般步骤：

把一个n次多项式f(x)＝anxn＋an－1xn1＋…＋a1x＋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, 这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.

1.辗转相除法的基本步骤是用较大的数除以较小的数.( √ ) 2.求最大公约数的方法除辗转相除法之外,没有其他方法.( × ) 3.编写辗转相除法的程序时,要用到循环语句.( √ )

类型一 辗转相除法

例1 试用辗转相除法求325,130,270的最大公约数. 考点 辗转相除法

题点 利用辗转相除法求三个数的最大公约数

解 ∵325＝130×2＋65,130＝65×2,∴325与130的最大公约数是65.∵270＝65×4＋10,65＝10×6＋5,10＝5×2,∴65与270的最大公约数是5,故325,130,270这三个数的最大公约数为5.

反思与感悟 辗转相除法的实质：对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到大数被小数除尽,则这时的小数就是原来两个正整数的最大公约数.

跟踪训练1 用辗转相除法求204与85的最大公约数时,需要做除法的次数是 . 考点 辗转相除法

题点 用辗转相除法求两个数的最大公约数 答案 3

解析 用辗转相除法可得204÷85＝2……34,85÷34＝2……17,34÷17＝2,此时可以判断204与85的最大公约数是17,做了3次除法得出结果. 类型二 更相减损术

例2 试用更相减损术求612,396的最大公约数. 考点 更相减损术

题点 利用更相减损术求最大公约数

解 方法一 612÷2＝306,396÷2＝198,306÷2＝153,198÷2＝99,∴153－99＝54,99－54＝45,54－45＝9,45－9＝36,36－9＝27,27－9＝18,18－9＝9.∴612,396的最大公约数为9×22＝36. 方法二 612－396＝216,396－216＝180,216－180＝36,180－36＝144,144－36＝108,108－36

＝72,72－36＝36.故36为612,396的最大公约数. 反思与感悟 用更相减损术的算法步骤 第一步,给定两个正整数m,n,不妨设m＞n.

第二步,若m,n都是偶数,则不断用2约简,使它们不同时是偶数,约简后的两个数仍记为m,n. 第三步,d＝m－n.

第四步,判断“d≠n”是否成立,若是,则将n,d中的较大者记为m,较小者记为n,返回第三步;否则,2kd(k是约简整数2的个数)为所求的最大公约数. 跟踪训练2 用更相减损术求261和319的最大公约数. 考点 更相减损术

题点 利用更相减损术求最大公约数 解 ∵319－261＝58, 261－58＝203, 203－58＝145, 145－58＝87, 87－58＝29, 58－29＝29,

∴319与261的最大公约数为29. 类型三 秦九韶算法的应用

例3 用秦九韶算法求多项式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.

反思与感悟 (1)先将多项式写成一次多项式的形式,然后运算时从里到外,一步一步地做乘法和加法即可.这样比直接将x＝－2代入原式大大减少了计算量.若用计算机计算,则可提高运算

本文来源：https://www.bwwdw.com/article/d4x8.html