1、1.3 算法案例(一),第一章 算法初步,学习目标 1.了解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析. 2.了解秦九韶算法及利用它提高计算效率的本质. 3.对简单的案例能设计程序框图并写出算法程序.,问题导学,达标检测,题型探究,内容索引,问题导学,知识点一 求两个数的最大公约数的算法,思考 注意到8 2516 10512 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的最大
2、公约数也是6 105与2 146的最大公约数.,梳理 求两个数的最大公约数有2种算法： (1)辗转相除法 辗转相除法，又叫欧几里得算法，是一种求两个正整数的_ 的古老而有效的算法. 辗转相除法的算法步骤 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r0，则m，n的最大公约数等于 ； 否则，返回 .,最大公约数,两个正整数m，n,m除以n所得的余数r,mn，nr,m,第二步,(2)更相减损术的运算步骤 第一步，任意给定两个正整数，判断它们是否都是 .若是，用_ 约简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的
3、数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,偶数,2,第二步,较大,较小,较小,相等,求n次多项式的值的算法，有一种比较好的算法叫秦九韶算法. 秦九韶算法的一般步骤： 把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式： (anxan1)xan2)xa1)xa0，求多项式的值时，首先计算 一次多项式的值，即v1 ，然后由内向外逐层计算一次多项式的值，即 v2 ， v3 ，,知识点二 求n次多项式f(x)anxnan1xn1a1xa0的值的算法,最内层括号内,anxan1,v1xan2,v2xan3, vn ， 这样，求n次多项式f(x)的值就转化
4、为求 的值.,vn1xa0,n个一次多项式,思考辨析 判断正误 1.辗转相除法的基本步骤是用较大的数除以较小的数.( ) 2.求最大公约数的方法除辗转相除法之外，没有其他方法.( ) 3.编写辗转相除法的程序时，要用到循环语句.( ),题型探究,例1 试用辗转相除法求325,130,270的最大公约数. 解 325130265,130652， 325与130的最大公约数是65. 27065410,651065,1052， 65与270的最大公约数是5， 故325,130,270这三个数的最大公约数为5.,类型一 辗转相除法,解答,反思与感悟 辗转相除法的实质：对于给定的两个正整数，用较大的数除
5、以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数.,跟踪训练1 用辗转相除法求204与85的最大公约数时，需要做除法的次数是 . 解析 用辗转相除法可得20485234,8534217,34172， 此时可以判断204与85的最大公约数是17， 做了3次除法得出结果.,解析,答案,3,类型二 更相减损术,例2 试用更相减损术求612,396的最大公约数. 解 方法一 6122306,3962198,3062153,198299， 1539954,995445,54459,45936,36927,27918,
6、1899. 612,396的最大公约数为92236. 方法二 612396216,396216180,21618036,18036144,14436108,1083672,723636. 故36为612,396的最大公约数.,解答,反思与感悟 用更相减损术的算法步骤 第一步，给定两个正整数m，n，不妨设mn. 第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n. 第三步，dmn. 第四步，判断“dn”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd(k是约简整数2的个数)为所求的最大公约数.,跟踪训练2 用更相减损术求26
7、1和319的最大公约数. 解 31926158， 26158203， 20358145， 1455887， 875829， 582929， 319与261的最大公约数为29.,解答,类型三 秦九韶算法的应用,例3 用秦九韶算法求多项式f(x)x55x410x310x25x1当x2时的值. 解 f(x)x55x410x310x25x1(x5)x10)x10)x5)x1. 当x2时，有v01； v1v0xa41(2)53； v2v1xa33(2)104； v3v2xa24(2)102； v4v3xa12(2)51； v5v4xa01(2)11. 故f(2)1.,解答,反思与感悟 (1)先将多项式写
8、成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可.这样比直接将x2代入原式大大减少了计算量.若用计算机计算，则可提高运算效率. (2)注意：当多项式中n次项不存在时，可将第n次项看作0xn.,跟踪训练3 用秦九韶算法计算多项式f(x)x612x560x4160x3240x2192x64当x2时的值.,解答,解 根据秦九韶算法，把多项式改写成如下形式： f(x)(x12)x60)x160)x240)x192)x64. 由内向外依次计算一次多项式当x2时的值：v01； v1121210； v21026040； v340216080； v480224080； v580219232；
9、 v6322640. 所以当x2时，多项式的值为0.,达标检测,答案,解析,1.1 337与382的最大公约数是 A.3 B.382 C.191 D.201 解析 1 3373823191,3821912， 所以1 337与382的最大公约数是191.,1,2,3,4,5,答案,解析,2.用秦九韶算法计算多项式f(x)6x65x54x43x32x2x7在x0.4时的值时，需做加法和乘法的次数的和为 A.10 B.9 C.12 D.8 解析 f(x)(6x5)x4)x3)x2)x1)x7， 做加法6次，乘法6次，6612(次)，故选C.,1,2,3,4,5,3.用更相减损术求36与134的最大公
10、约数，第一步应为_. 解析 36与134都是偶数， 第一步应为先除以2， 得到18与67.,1,2,3,4,5,解析,答案,先除以2，得到,18与67,答案,解析,4.已知a333，b24，则使得abqr(q，r均为自然数，且0rb)成立的q和r的值分别为 . 解析 用333除以24，商即为q，余数就是r.333241321.,1,2,3,4,5,13,21,1,2,3,4,5,5.用辗转相除法求85与51的最大公约数时，需要做除法的次数为 . 解析 8551134， 5134117， 341720.,3,答案,解析,1.辗转相除法，就是对于给定的两个正整数，用较大的数除 以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数. 3.用秦九韶算法求多项式f(x)当xx0的值的思路为(1)改写；(2)计算(3)结论f(x0)vn.,规律与方法,
浙公网安备33030202001339号