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

时间:2019/9/9 19:05:03   作者:数学名师王老师
1.理解中国古代三个问题(求两个正整数的最大公约数、割fun88网上娱乐术、求多项式函数值)的算法.
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$时的值.

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

相关推荐

向量的加法

1.掌握向量加法的运算,并理解其几何意义. 2.理解向量加法的三角形法则、平行四边形法则、多边形法则的适用范围,并能应用向量加法的运算律进行相关运算.