1.3 中国古代数学中的算法案例

时间:2019-9-9 19:05:03   作者:数学名师王老师
1.理解中国古代三个问题(求两个正整数的最大公约数、割圆术、求多项式函数值)的算法.
2.注意体会“更相减损之术”与“辗转相除法”的差异,以及秦九韶算法在求多项式函数值上的优越性.
知识点
  • 1.求两个正整数最大公约数的算法

    (1)“等值算法”在我国古代也称为更相减损之术,它是用来求两个正整数的最大公约数的方法,其基本过程是:对于给定的两个数,用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的两数相等为止,则所得数就是所求的最大公约数.

    (2)辗转相除法(即欧几里得算法):是用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是所求的最大公约数.

    归纳总结
    1.用“等值算法”求两数的最大公约数时,是当大数减去小数的差恰好等于小数时停止减法,这时的小数就是要求的两数的最大公约数.

    2.求三个以上(含三个数)的数的最大公约数时,可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.

    【做一做1】 用辗转相除法求168与72的最大公约数,要做$n$次除法运算,那么$n$为(                  

    A.2  B.3  C.4  D.5

    答案:$A$

  • 2.割圆术

    割圆术是我国魏晋时期的数学家刘徽在注《九章算术》中采用正多边形面积逐渐逼近圆面积的算法计算圆周率π的一种方法.他的思想后来又得到祖冲之的推进和发展,计算出的圆周率的近似值在世界上很长时间里处于领先地位.

    【做一做2】 用圆内接正多边形逼近圆,得到的圆周率的值总是(  )

    A.大于等于$\pi$的实际值

    B.大于$\pi$的实际值

    C.等于$\pi$的实际值

    D.小于$\pi$的实际值

    解析:用割圆术求出的是$\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.我国数学家刘徽采用正多边形面积逐渐逼近圆面积的算法计算圆周率π,这种算法称为(  )

    A.弧田法  B.逼近法

    C.割圆术  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$时的值.

声明:本站部分内容搜集整理自互联网,如果涉及侵犯您的版权,请联系我们举报,并提供相关证据,工作人员会在5个工作日内回复您,一经查实,本站将立刻删除涉嫌侵权内容。