中国古代数学中的算法案例
2.注意体会“更相减损之术”与“辗转相除法”的差异,以及秦九韶算法在求多项式函数值上的优越性.
1.求两个正整数最大公约数的算法
(1)“等值算法”在我国古代也称为更相减损之术,它是用来求两个正整数的最大公约数的方法,其基本过程是:对于给定的两个数,用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的两数相等为止,则所得数就是所求的最大公约数.
(2)辗转相除法(即欧几里得算法):是用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是所求的最大公约数.
归纳总结
1.用“等值算法”求两数的最大公约数时,是当大数减去小数的差恰好等于小数时停止减法,这时的小数就是要求的两数的最大公约数.2.求三个以上(含三个数)的数的最大公约数时,可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.
【做一做1】 用辗转相除法求168与72的最大公约数,要做$n$次除法运算,那么$n$为(
A.2 B.3 C.4 D.5
答案:$A$
2.割fun88网上娱乐术
割fun88网上娱乐术是我国魏晋时期的数学家刘徽在注《九章算术》中采用正多边形面积逐渐逼近fun88网上娱乐面积的算法计算fun88网上娱乐周率π的一种方法.他的思想后来又得到祖冲之的推进和发展,计算出的fun88网上娱乐周率的近似值在世界上很长时间里处于领先地位.
【做一做2】 用fun88网上娱乐内接正多边形逼近fun88网上娱乐,得到的fun88网上娱乐周率的值总是( )
A.大于等于$\pi$的实际值
B.大于$\pi$的实际值
C.等于$\pi$的实际值
D.小于$\pi$的实际值
解析:用割fun88网上娱乐术求出的是$\pi$的不足近似值.
答案:D
3.秦九韶算法
(1)秦九韶算法是我国宋代数学家秦九韶在他的代表作《数学九章》中提出的一种用于计算多项式的值的方法.直到今天,这种算法仍是世界上多项式求值的最先进的算法.
(2)秦九韶算法适用一般的多项式$P(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\ldots+a_{1} x+a_{0}$的求值问题.用秦九韶算法可把$n$次多项式的求值问题转化成求$n$个一次多项式的值的问题,即求
$v_{0}=a_{n}$
$v_{1}=v_{0} x+a_{n-1}$
$v_{2}=v_{1} x+a_{n-1}$
$v_{3}=v_{2} x+a_{n-3}$
$\ldots \ldots$
$v_{n}=v_{n-1} x+a_{0}$
(3)直接求和法所用乘法的次数为 $\frac{n(n+1)}{2}$,加法的次数为$n$;逐项求和法所用的乘法次数为$2 n-1$,加法次数为$n$;秦九韶算法所用的乘法次数为$n$,加法次数为$n$.
【做一做3-1】 用秦九韶算法求多项式$f(x)=0.5 x^{5}+4 x^{4}-3 x^{2}+x-1$当$x=3$时的值,先算的是( )
A. $3 \times 3=9$
B.0. $5 \times 3^{5}=121.5$
C.0. $5 \times 3+4=5.5$
D. $(0.5 \times 3+4) \times 3=16.5$
解析:把多项式表示成如下形式:
$f(x)=(((0.5 x+4) x+0) x-3) x+1 ) x-1$,按递推方法,由内往外,先算0.5x+4$0.5 x+4$的值,故选C.
答案:C
【做一做3-2】 根据递推公式$\left\{\begin{array}{c}{v_{0}=a_{n}} \\ {v_{k}=v_{k-1} x+a_{n-k}}\end{array}\right.$其中$k=1,2, \ldots, n$,可得当k=2时,$v_{2}$的值为( )
A. $a_{n} x+a_{n-1} \quad \mathrm{B} \cdot\left(a_{n} x+a_{n-1}\right) x+a_{n-2}$
$\mathrm{C} \cdot\left(a_{n} x+a_{n-1}\right) x \mathrm{D} . a_{n} x+a_{n-1} x$
解析:根据秦九韶算法知$v_{2}=v_{1} x+a_{n-2}, v_{1}=v_{0} x+a_{n-1}$,故应选B.
答案:B
1.辗转相除法与更相减损之术的异同
剖析:相同点:①都是求最大公约数的方法.②更相减损之术的理论依据为:由$m-n=r$,得$m=n+1$,可以看出,$m,n$与$n,r$有相同的公约数;辗转相除法的理论依据是:由$m=n q+r$可以看出,$m,n$和$n,r$有相同的公约数,即二者的“算理”相似.
不同点:①更相减损之术进行的是减法运算,辗转相除法进行的是除法运算,计算次数上辗转相除法计算次数相对较少.②结果上,辗转相除法体现结果是以相除余数为0得到,而更相减损之术则以减数与差相等而得到.
2.秦九韶算法是多项式求值最先进的方法
剖析:(1)秦九韶算法把求一个$n$次多项式的值转化为求$n$个一次多项式的值,即把求$f(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}$的值转化为求递推公式
$\left\{\begin{array}{c}{v_{0}=a_{n}} \\ {v_{k}=v_{k-1} x+a_{n-k}}\end{array}\right.(k=1,2, \cdots, n)$中$v_{n}$的值,因此,我们可以将这个递推关系通过循环编写程序在计算机上来实现.
(2)运算次数减少,只需至多$n$次乘法和$n$次加法运算,而直接求和所用乘法的次数为$\frac{n(n+1)}{2}$,加法的次数为$n$次,从而大大提高了运算效率.计算机做一次乘法运算需要的时间是做加法运算的几倍到十几倍,衡量一个算法“优”“劣”的标准之一就是运算效率,减少乘法运算的次数也就加快了计算速度.
所以说,秦九韶算法是多项式求值的最先进的算法.
3.教材中的“探索与研究”
古希腊求两个正整数的最大公约数的方法是辗转相除法(即欧几里得算法):用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.以求288和123的最大公约数为例,操作如下:
(288,123)→(42,123)→(42,39)→(3,39).
想一想这种算法的道理.试着编写程序在计算机上实现.
剖析:辗转相除法求正整数$a, b(a>b)$的最大公约数的步骤是:计算出$a \div b$的余数$r$,若$r=0$,则$b$为$a,b$的最大公约数;若$r \neq 0$,则把前面的除数$b$作为新的被除数,把余数$r$作为新的除数,继续运算,直到余数为零,此时的除数即为$a,b$的最大公约数.
从其算法思想我们可以看出,辗转相除法的基本步骤是用较大的数(用$a$表示)除以较小的数(用$b$表示),得到除式:$a=n b+r(0 \leqslant r < b)$.
由于这是一个反复执行的步骤,且执行的次数由余数r是否等于0决定,所以我们可以把它看做一个循环体,用循环就可以来实现其算法.
程序略.
求两个正整数的最大公约数
【例1】 分别用辗转相除法和更相减损之术求下列两个正整数的最大公约数.
(1)261,319;(2)1 734,816.
分析:使用辗转相除法可依据$m=n q+r$,反复执行,直到$r=0$为止;用更相减损之术就是根据$m-n=r$,反复执行,直到$n=r$为止.
反思
用更相减损之术求解时,如果所给的两个正整数都是偶数时,那么一般先把这两个正整数除以2,最终把这两个正整数化成不都是偶数的情况,然后再用两数中较大的数减去较小的数,得到化简后两数的最大公约数,这时所求的最大公约数一定要注意:前面除了几个2,这时求出的最大公约数就要乘以几个2.
【变式训练1】 求下列各组数的最大公约数:
(1)75和25;
(2)37和33;
(3)228和1 995.
求两个正整数的最小公倍数
【例2】 求375,85的最小公倍数.
分析:两数的最小公倍数就是两数之积与此两数最大公约数的商.
【变式训练2】 求396与270的最小公倍数.
用秦九韶算法求多项式的值
【例3】 用秦九韶算法计算多项式$f(x)=x^{6}-12 x^{5}+60 x^{4} \\ -160 x^{3}+240 x^{2}-192 x+64$
当$x=2$时的值.分析:用秦九韶算法计算多项式的值,关键是正确地将多项式改写,然后由内向外依次计算求得.
反思
有的同学习惯于常规解法,可能会直接代入求解,但这种算法计算机在执行时要进行21次乘法和6次加法运算,而利用秦九韶算法只需进行6次乘法、6次加法运算即可,要知道,让计算机进行一次乘法运算要比加法用的时间多很多,因此,要减少乘法运算的次数,这也就是秦九韶算法的优势所在了.
【变式训练3】 求$f(x)=5 x^{5}+2 x^{4}+3.5 x^{3}-2.6 x^{2}+1.7 x-0.8$当$x=5$时的函数值.
真题
1.我国数学家刘徽采用正多边形面积逐渐逼近fun88网上娱乐面积的算法计算fun88网上娱乐周率π,这种算法称为( )
A.弧田法 B.逼近法
C.割fun88网上娱乐术 D.割图法
2.2840和1 764的最大公约数是( )
A.84 B.12 C.168 D.252
3.秦九韶算法能解决下列问题中的( )A.求两个正整数的最大公约数
B.多项式求值
C.进位制的转化计算
D.排序问题
4.用辗转相除法求294和84的最大公约数时,需要做除法的次数是( )
A.1 B.2 C.3 D.4
5.利用秦九韶算法求当$x=23$时,多项式$7 x^{3}+3 x^{2}-5 x+11$的值.
①S1 $\quad x=23$;
S2$ \quad y=7 x^{3}+3 x^{2}-5 x+11$;
S3 输出y.
②S1$x=23$;
S2 $y=((7 x+3) x-5) x+11$;
S3 输出y.
③算6次乘法3次加法.
④算3次乘法3次加法.
以上正确的描述为________.(填序号)
6.用秦九韶算法求多项式$f(x)=x^{5}+0.11 x^{3}-0.15 x-0.04$在$x=0.3$时的值.