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－1xn－1＋…＋a1x＋a0的值的算法 求n次多项式的值的算法，有一种比较好的算法叫秦九韶算法. 秦九韶算法的一般步骤： 把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋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 ... ...