1.4.1 算法案例(1)—辗转相除法、更相减损术与秦九韶算法doc.doc

1.4.1 算法案例（1）辗转相除法、更相减损术与秦九韶算法目标：理解并掌握辗转相除法、更相减损术与秦九韶算法一.辗转相除法实例1.求8251与6105的最大公约数.（辗转相除法思想的应用） 第一步：用较大的数除以较小的数，得. 分析：6105与2146的公约数一定是8251与6105的公约数；反之8251与6105的公约数也一定是6105与2146的公约数。因此， 求8251与6105的最大公约数等同于求6105与2146的最大公约数. 第二步：用较大的数除以较小的数，得. 分析：同理6105与2146的最大公约数等同于2146与1813的最大公约数. 第三步：用较大的数除以较小的数，得. 分析：同理2146与1813的最大公约数等同于1813与333的最大公约数. 第四步：用较大的数除以较小的数，得. 分析：. 第五步：用较大的数除以较小的数，得. 分析：. 第六步：用较大的数除以较小的数，得. 分析：148与37的最大公约数是37，所以，8251与6105的最大公约数就是37. 这个问题的解决，应用的就是辗转相除法，反复进行除法运算，直到余数为0，最大公约数也就出来了，反复相除的运算在计算机里我们可以应用循环语句来实现.实例2.设计一个算法，求两个正整数的最大公约数.解：问题的算法如下： 第一步：输入. 第二步：计算除以的余数. 第三步：.第四步：如果，则与的最大公约数为，否则返回第二步. 其相应的程序框图如下： 相应的计算机程序如下：INPUT m, nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND 二.更相减损术 九章算术是我们中国古代的数学专著，其中介绍了另一种求两个数的最大公约数的有效方法，即更相减损术.其具体算法如下： 第一步：任意给定两个正整数，判断它们是否都是偶数。如果是，用2约简；如果不是，执行第二步. 第二步：用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到某一步减数与差相等为止，则这个数或这个数与约简的数的积就是所求的最大公约数.实例3.用更相减损术求98与63的最大公约数.9863=356335=283528=7287=21217=14147=7所以98与63的最大公约数是7.三.秦九韶算法问题的引入：如何求多项式当时的值.方法一：一个自然的做法是把5带入多项式，计算各项的值，然后把它们加起来，这时，我们一共做了次乘法运算，次加法运算.方法二：先计算的值，然后依次计算，的值，每次都应用上一次的计算结果。这时我们一共做了4次乘法运算，5次加法运算。 把第二种算法与第一种算法相比较，很显然，乘法的次数减少了，因而能够提高运算效率。计算机做一次乘法所用的时间比做一次加法所用的时间要长得多，所以应用第二种方法，计算机能更快地得到结果。 第三种算法：我国南宋时期数学家秦九韶在他所著的数书九章中提出如下算法：求多项式的值时，首先计算最内层括号内一次多项式的值，即然后由内向外逐次计算一次多项式的值，即： 这样，求次多项式的值的问题就转化为求个一次因式的值的问题了，而且，从算法步骤上来看，一共只用了个乘法、个加法.实例4.已知一个多项式为，用秦九韶算法求这个多项式当时的值.解：根据秦九韶算法，我们把改写为：按从内到外的顺序依次计算每一个一次多项式当时的值：所以当时，的值为.秦九韶算法的程序框图与计算机语言：设计算法计算多项式的值.分析秦九韶算法，我们看到，用秦九韶算法计算一个次多项式时，若令，则有：，其中是一个要反复执行的步骤，因此可以用循环结构来实现. 算法如下：第一步：输入多项式的次数、最高次项的系数和的值.第二步：将的值初始化为，将的值初始化为.第三步：输入次项的系数.第四步：.第五步：判断是否大于或等于0，若是，则返回第三步，否则，输出多项式的值.其程序框图如图：根据程序框图，可以写出计算机程序如下：INPUT “n=”; nINPUT “an=”; aINPUT “x=”, xv=ai=n-1WHILE i=0PRINT iINPUT “ai”; av=v*x+ai=i-1WENDPRINT vEND四.课外练习：优化设计.五.补充练习1.用辗转相除法求294与84的最大公约数时，需要做除法的次数是 （ ） A.1 B.2 C.3 D.42.用更相减损术求459与357的最大公约数时，需要做减法的次数是 （ ） A.4 B.5 C.6 D.73.利用秦九韶算法求当时，的值， 下列说法中正确的是 （ ）A.先求B.先求，第二步求C.直接运算求解D.以上都不对4.求117与182的最大公