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

1、1.4.1算法案例（1）辗转相除法、更相减损术与秦九韶算法目标：理解并掌握辗转相除法、更相减损术与秦九韶算法.辗转相除法实例1.求8251与6105的最大公约数.（辗转相除法思想的应用）第一步：用较大的数除以较小的数，得 匸、丨2!- .分析：6105与2146的公约数一定是8251与6105的公约数；反之8251与6105的 公约数也一定是6105与2146的公约数。因此，求8251与6105的最大公约数等同于求6105与2146的最大公约数.第二步：用较大的数除以较小的数，得 汀以 汁;1-分析：同理6105与2146的最大公约数等同于2146与1813的最大公约数.第三步：用较大的数除以

2、较小的数，得- IS13 - + 芫；.分析：同理2146与1813的最大公约数等同于1813与333的最大公约数.第四步：用较大的数除以较小的数，得分析：. .第五步：用较大的数除以较小的数，得 分析：. .第六步：用较大的数除以较小的数，得 分析：148与37的最大公约数是37, 所以，8251与6105的最大公约数就是37.这个问题的解决，应用的就是辗转相除法，反复进行除法运算，直到余数为0,最大公约数也就出来了，反复相除的运算在计算机里我们可以应用循环语句来实现.实例2.设计一个算法，求两个正整数： 的最大公约数.解：问题的算法如下：1X13 = 333 x 5 + 148.333 =

3、 148 x 2 + 37.148 = 37x4.第一步：输入，.第二步：计算t除以訂的余数.第三步:讯=込盒=二第四步：如果；，则小与訝的最大公约数为,否则返回第二步INPUT m, nDOr=m MOD nm=n n=rLOOP UNTIL r=0PRINT mEND二更相减损术九章算术是我们中国古代的数学专著，其中介绍了另一种求两个数的最大公约 数的有效方法，即更相减损术其具体算法如下：第一步：任意给定两个正整数，判断它们是否都是偶数。如果是，用2约简；如果不是，执行第二步.第二步：用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减 小数。继续这个操作，直到某一步减数与差相

4、等为止，则这个数或这个数与约简的 数的积就是所求的最大公约数.实例3用更相减损术求98与63的最大公约数.98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以98与63的最大公约数是7.三.秦九韶算法问题的引入：如何求多项式H -1十，：十斗十.当可二时的值.方法一：一个自然的做法是把5带入多项式“，计算各项的值，然后把它们加 起来，这时，我们一共做了+*1 I次乘法运算，、次加法运算.方法二：先计算的值，然后依次计算I ;I 的值，每次都应用上一次的计算结果。这时我们一共做了4次乘法运算，5次加法运把第二种算法与第一种算法相比较，很显然，乘法的次数减少了

5、，因而能够提高运 算效率。计算机做一次乘法所用的时间比做一次加法所用的时间要长得多，所以应 用第二种方法，计算机能更快地得到结果。第三种算法：我国南宋时期数学家秦九韶在他所著的数书九章中提出如下算 法：f（x） =anxn+ 占心* |%片+ 町=（占+备i* +占片+占J%+竝=（%*3+和X4+碍）北+込）x+）A十召p n yi fl求多项式的值时，首先计算最内层括号内一次多项式的值，即然后由内向外逐次计算一次多项式的值，即: 片F + %V = V 这样，求匸次多项式的值的问题就转化为求 门个一次因式的值的问题了，而且，从 算法步骤上来看，一共只用了匸个乘法、门个加法解：根据秦九韶算法

6、，我们把改写为：f(x) = (4x+ 2)x+35)x-2.6)x+ L7)-0.8按从内到外的顺序依次计算每一个一次多项式当亍二：时的值: = 5 + 2 = 22K = 5 + V5 = II.V5v, =K*5 - 2.6 = 564,9片=10 + 1.7 = 2826.2E5=V45-0.8 = 14130.2所以当时，的值为7.秦九韶算法的程序框图与计算机语言：设计算法计算多项式分析秦九韶算法，我们看到，用秦九韶算法计算一个口次多项式时，若令：，则有：用秦九韶算法求这个多项式当;时的值0+俎的值.人=%* r怙 T+e；kn，其中% -X+打/是一个要反复执行的步骤，因此可以用循

7、环结构来实现算法如下：第一步：输入多项式的次数门、最高次项的系数.和-的值a第二步：将丨的值初始化为，将的值初始化为；.第三步：输入次项的系数，.第四步: 第五步：判断是否大于或等于0，若是，贝U返回第三步，否则，输出多项式的值.其程序框图如图：根据程序框图，可以写出计算机程序如下：INPUT“n=”；nINPUT“an=”; aINPUT“x=”, xv=ai=n-1WHILE i=0PRINT iINPUT“ai”; av=v*x+ai=i-1WENDPRINT vENDP四.课外练习：优化设计.五补充练习1用辗转相除法求294与84的最大公约数时，需要做除法的次数是 （）A.1 B.2 C.3 D.42.用更相减损术求459与357的最大公约数时，需要做减法的次数是（）A.4 B.5 C.6 D.73利用秦九韶算法求当】时，门-, 的值,下列说法中正确的是 （）A.先求：1B.先求 第二步求；1C.门_*-直接运算求解D.以上都不对4.求