人教A版必修三 算法案例(一) 学案.docx

1.3算法案例(一)学习目标1.了解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析.2.了解秦九韶算法及利用它提高计算效率的本质.3.对简单的案例能设计程序框图并写出算法程序.知识点一求两个数的最大公约数的算法思考注意到8251610512146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.梳理求两个数的最大公约数有2种算法：(1)辗转相除法辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法.辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步.(2)更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.知识点二求n次多项式f(x)anxnan1xn1a1xa0的值的算法求n次多项式的值的算法，有一种比较好的算法叫秦九韶算法.秦九韶算法的一般步骤：把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：(anxan1)xan2)xa1)xa0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值.1.辗转相除法的基本步骤是用较大的数除以较小的数.()2.求最大公约数的方法除辗转相除法之外，没有其他方法.()3.编写辗转相除法的程序时，要用到循环语句.()类型一辗转相除法例1试用辗转相除法求325,130,270的最大公约数.考点辗转相除法题点利用辗转相除法求三个数的最大公约数解325130265,130652，325与130的最大公约数是65.27065410,651065,1052，65与270的最大公约数是5，故325,130,270这三个数的最大公约数为5.反思与感悟辗转相除法的实质：对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数.跟踪训练1用辗转相除法求204与85的最大公约数时，需要做除法的次数是.考点辗转相除法题点用辗转相除法求两个数的最大公约数答案3解析用辗转相除法可得20485234,8534217,34172，此时可以判断204与85的最大公约数是17，做了3次除法得出结果.类型二更相减损术例2试用更相减损术求612,396的最大公约数.考点更相减损术题点利用更相减损术求最大公约数解方法一6122306,3962198,3062153,198299，1539954,995445,54459,45936,36927,27918,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用更相减损术求261和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)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可.这样比直接将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；v6322640.所以当x2时，多项式的值为0.1.1337与382的最大公约数是()a.3b.382c.191d.201考点辗转相除法题点利用辗转相除法求两个数的最大公约数答案c解3821912，所以1337与382的最大公约数是191.2.用秦九韶算法计算多项式f(x)6x65x54x43x32x2x7在x0.4时的值时，需做加法和乘法的次数的和为()a.10b.9c.12d.8考点秦九韶算法题点秦九韶算法中算法的次数问题答案c解析f(x)(6x5)x4)x3)x2)x1)x7，做加法6次，乘法6次，6612(次)，故选c.3.用更相减损术求36与134的最大公约数，第一步应为.考点更相减损术题点更相减损术的应用答案先除以2，得到18与67解析36与134都是偶数，第一步应为先除以2，得到18与67.4.已知a333，b24，则使得abqr(q，r均为自然数，且0rb)成立的q和r的值分别为.考点辗转相除法题点辗转相除法的简单应用答案13,21解析用333除以24，商即为q，余数就是r.333241321.5.用辗转相除法求85与51的最大公约数时，需要做除法的次数为.考点辗转相除法题点辗转相除法中除法次数问题答案3解析8551134，5134117，341720.1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数