辗转相除法与更相减损术、秦九韶算法
2.掌握秦九韶算法,了解它提高计算效率的实质,并会求多项式的值.
3.进一步体会算法的基本思想.
(4)程序:
1.辗转相除法与更相减损术
(1)辗转相除法.
①算法步骤:
第一步,给定两个正整数$m n$.
第二步,计算$m$除以$n$所得的余数r.
第三步,$m=n$,$n=$r.
第四步,若$r=__$,则$m$,$n$的最大公约数等于$m$;否则,返回第__步.
②程序框图:
③程序:
(2)更相减损术.
算法分析:
第一步,任意给定两个正整数,判断它们是否都是____.若是,用____约简;若不是,执行第二步.
第二步,以较大的数____去较小的数,接着把所得的差与较小的数比较,并以____数减____数.继续这个操作,直到所得的差与减数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
【做一做1】 用更相减损术求156和48的最大公约数时,第一步是________________.
答案:用2约简
2.秦九韶算法
(1)概念:求多项式$f(x)=a_{n} x^{n+}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}$的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求n个一次多项式的值,共进行n次乘法运算和n次加法运算.其过程是:
改写多项式为:
$f(x)=a_{n} x^{n+} a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}$
$=\left(a_{n} x^{n-1}+a_{n-1} x^{n-2}+\cdots+a_{1}\right) x \\ + a_{0}$
$=\left(\left(a_{n} x^{n-2}+a_{n-1} x^{n-3}+\cdots+a_{2}\right) x+a_{1}\right) x \\ +a_{0}$
$=\cdots$
$=\left(\cdots\left(\left(a_{n} x+a_{n-1}\right) x+a_{n-2}\right) x+\cdots+a_{1}\right) x \\ +a_{0}$
设$v_{1}=a_{n}x+a_{n-1}$,
$v_{2}=v_{1} x+a_{n-2}, v_{3}=v_{2} x+a_{n-3}, \cdots$
$v_{n}=v_{n-1}x+a_{0}$
(2)算法步骤:
第一步,输入多项式的次数$n$、最高次项的系数$an$和$x$的值.
第二步,将v的值初始化为$an$,将$$i的值初始化为$n-1$.
第三步,输入$i$次项的系数$a_{i}$.
第四步,$v=v x+a_{i}, i=i-1$
第五步,判断i是否大于或等于__.若是,则返回第三步;否则,输出多项式的值___.
(3)程序框图:
(4)程序:
【做一做2】 用秦九韶算法求$f(x)=2 x^{3}+x-3$当$x=3$时的值的过程中,$v_{2}=$____.
解析:$f(x)=((2 x+0) x+1) x-3$,
$v_{0}=2$;
$v_{1}=2 \times 3+0=6$;
$v_{2}=6 \times 3+1=19$.
答案:19
1.更相减损术与辗转相除法的区别与联系
剖析:如表所示.
辗转相除法
更相减损术
区别
①以除法为主.
②两个整数差值较大时运算次数较少.
③相除余数为零时得结果
①以减法为主.
②两个整数的差值较大时,运算次数较多.
③相减,差与减数相等得结果.
④相减前先判断这两个正整数是否都是偶数
联系
①都是求最大公约数的方法.
②二者的实质都是递归的过程.
③二者都要用循环来实现
2.秦九韶算法是比较先进的算法
剖析:同一个问题有多种算法,如果某个算法比其他算法的步骤少,运算的次数少,那么这个算法就是比较先进的算法.判断算法是否先进的一个重要标志就是运算的次数越少越好.
求多项式$f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+…+a_{1}x+a_{0}$的值时,通常是先计算$a_{n}x^{n}$,进行n次乘法运算;再计算$a_{n-1}x^{n-1}$,进行n-1次乘法运算;这样继续下去
共进行$n+n-1+\cdots+2+1=\frac{n(n+1)}{2}$(其计算方法以后学习)次乘法运算,还需要进行$n$次加法运算,总共进行$\frac{n(n+1)}{2}+n$运算.
但是用秦九韶算法时,改写多项式为
$f(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}$
$=\left(a_{n} x^{n-1}+a_{n-1} x^{n-2}+\cdots+a_{1}\right) x \\ +a_{0}$
$=\left(\left(a_{n} x^{n-2}+a_{n-1} x^{n-3}+\cdots+a_{2}\right) x+a_{1}\right) x \\ +a_{0}$
$=\cdots$
$=\left(\cdots\left(\left(a_{n} x+a_{n-1}\right) x+a_{n-2}\right) x+\cdots+a_{1}\right) x \\ +a_{0}$
先计算$v_{1}=a_{n} x+a_{n-1}$,需1次乘法运算,1次加法运算;
$v_{2}=v_{1} x+a_{n-2}$,需1次乘法运算,1次加法运算;
……
$v_{n}=v_{n-1} x+a_{0}$需1次乘法运算,1次加法运算.
所以需进行$n$次乘法运算,$n$次加法运算,共进行$2n$次运算.
由于$\left[\frac{n(n+1)}{2}+n\right]-2 n=\frac{n(n-1)}{2} \geqslant 0,$ 则 $\frac{n(n+1)}{2}+n \geqslant 2 n$
因此说秦九韶算法与其他算法相比运算次数少,秦九韶算法是比较先进的算法.
【例1】 (1)用辗转相除法求840与1 785的最大公约数;
(2)用更相减损术求612与468的最大公约数.
分析:本题是关于辗转相除法和更相减损术的直接应用.辗转相除法的操作是较大的数除以较小的数;更相减损术的操作是以大数减小数.
反思
求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相减损术.用辗转相除法,即根据$a=n b+r$这个式子,反复相除,直到$r=0$为止;用更相减损术,即根据$r=|a-b|$这个式子,反复相减,直到$r=0$为止.
【变式训练1】 求228与1 995的最大公约数.
求多项式的值
【例2】 用秦九韶算法求多项式$f(x)=7 x^{7}+6 x^{6}+5 x^{5}+4 x^{4}+ \\ 3 x^{3}+2 x^{2}+x$
当$x=3$时的值.分析:解决本题首先需要将原多项式化成$f(x)=(((((7 x+6) x+5) x+4) x+3) x \\ +2) x+1 ) x$的形式,其次再弄清$v_{0}, v_{1}, v_{2}, \cdots, v_{7}$分别是多少,再针对这些式子进行计算.
反思秦九韶算法的关键在于把n次多项式转化为一次多项式,注意体会递推的实现过程,实施运算时要由内向外,一步一步执行.
【变式训练2】 用秦九韶算法求$f(x)=3 x^{5}+8 x^{4}-3 x^{3}+5 x^{2}+12 x-6$当$x=2$时的值.
易错辨析
易错点:利用秦九韶算法求含空项的$n$次多项式的值时易出现错误
【例3】 已知$f(x)=3 x^{4}+2 x^{2}+4 x+2$,利用秦九韶算法求$f(-2)$的值.
反思
利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写,依次计算一次多项式,由于后项计算用到前项的结果,故应认真、细心,确保中间结果的准确性.若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看成0$\cdot x^{n}$.
【变式训练3】 用秦九韶算法求多项式$f(x)=8 x^{7}+5 x^{6}+3 x^{4}+2 x+1$当$x=2$时的值.