中国古代算法案例1

1、3 59 15 问题问题1 1 ：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？18 30231818和和3030的最大公约的最大公约数是数是2 23=6.3=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到所得一直除到所得的商是互质数为止的商是互质数为止,然后然后把所有的除数连乘起来把所有的除数连乘起来. 问题问题2 2:我们都是利用找公约数的方法来求最大我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察公约数，如果公约数比较大而且根据我

2、们的观察又不能得到一些公约数，我们又应该怎样求它们又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求的最大公约数？比如求82518251与与61056105的最大公约数的最大公约数? ? 1、求两个正整数的最大公约数的算法、求两个正整数的最大公约数的算法我国早期也有解决求最大公约数问题的算法，我国早期也有解决求最大公约数问题的算法，就是更相减损术。就是更相减损术。更相减损术求最大公约数的步骤如下：更相减损术求最大公约数的步骤如下：可半者可半者半之，不可半者，副置分母半之，不可半者，副置分母子之数，以少减多，更相子之数，以少减多，更相减损，求其等也，以等数约之。减损，求其等也，以等数

3、约之。翻译出来为：第一步：任意给出两个正数；判断它翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用们是否都是偶数。若是，用2 2约简；若不是，执行第二步。约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大到所得的数相等为止，则这个数（等数）就是所求的最大公约数。公约数。练习练习1 1 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数. .解

4、：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减， 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习练习2 2：用更相减损术求两个正数：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。 (12)(12) 我国魏晋时期的数学家刘徽，他在注我国魏晋时期的数学家刘徽，他在注九章算术中采用正多边形面积逐渐逼近九章算术中采用正多边形面积逐渐逼近圆面积的算法计算圆周率圆面积的算法计算圆周率，用刘徽自己的

5、，用刘徽自己的原话就是原话就是：“割之弥细，所失弥少；割之又割之弥细，所失弥少；割之又割，以至于不可割，则与圆合体而无所失割，以至于不可割，则与圆合体而无所失矣矣” ，这段注文充分说明了刘徽对极限概念，这段注文充分说明了刘徽对极限概念. . 他的思想后来又得到祖冲之的推进和发展，他的思想后来又得到祖冲之的推进和发展，计算出圆周率的近似值在世界上很长时间里计算出圆周率的近似值在世界上很长时间里处于领先地位。处于领先地位。2.刘徽割圆术刘徽割圆术2.刘徽割圆术刘徽割圆术一、刘徽首先指出利用一、刘徽首先指出利用=3=3这一数值算得的这一数值算得的结果不是圆面积，而是圆内接正十二边形的结果不是圆面积，

6、而是圆内接正十二边形的面积，这个结果比面积，这个结果比的真值少的真值少. .二、他由圆内接正六边形算起，逐渐把边数二、他由圆内接正六边形算起，逐渐把边数加倍，逐个算出正加倍，逐个算出正1212边形、正边形、正2424边形、正边形、正4848边形、正边形、正9696边形边形的面积，这些面积会逐的面积，这些面积会逐渐地接近圆面积渐地接近圆面积. .最后求出圆面积的近似值。最后求出圆面积的近似值。三、已知正三、已知正6边形一边（恰与半径等长边形一边（恰与半径等长)即求得正即求得正12边形边形边长，边长，.由正由正12边形求正边形求正24边形一边之长时，刘徽反边形一边之长时，刘徽反复地应用到勾股定理（

7、或称商高、勾股定理），如图：复地应用到勾股定理（或称商高、勾股定理），如图：割圆术。不断地利用勾股定理，来计算割圆术。不断地利用勾股定理，来计算正正N边形的边长。边形的边长。 刘徽先将直径为刘徽先将直径为2 2的圆分割为的圆分割为6 6等分，等分，再分割成再分割成1212等分，等分，2424等分，等分，.，这样，这样继续下去，并利用勾股定理计算其面积，继续下去，并利用勾股定理计算其面积，从而求出圆周率的近似值，他一直计算从而求出圆周率的近似值，他一直计算到圆内接正到圆内接正192192边形的面积。因为圆的边形的面积。因为圆的半径为半径为1 1，所以随着边数的增大，面积，所以随着边数的增大，面积

8、不断趋近于圆周率，这样不断计算下去，不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值。就可以得到越来越精密的圆周率近似值。祖冲之 祖冲之祖冲之:（公元（公元429-500年）是我国南北朝时年）是我国南北朝时期，河北省涞源县人他从小就阅读期，河北省涞源县人他从小就阅读了许多天文、数学方面的书籍，勤奋了许多天文、数学方面的书籍，勤奋好学，刻苦实践，终于使他成为我国好学，刻苦实践，终于使他成为我国古代杰出的数学家、天文学家古代杰出的数学家、天文学家 圆周率是指圆周率是指平面平面上圆的上圆的周长周长与直径之比。早在一千四百多年与直径之比。早在一千四百多年以前，我国古代著名的数学家

9、祖以前，我国古代著名的数学家祖冲之，就精密地计算出圆的周长冲之，就精密地计算出圆的周长是它直径的是它直径的3.1415926-3.1415926-3.14159273.1415927倍之间。这是当时世界倍之间。这是当时世界上算得最精确的数值上算得最精确的数值-圆周率。圆周率。 “圆周率圆周率”是说一个圆的周长同它的直径有一个固定的比例。我们是说一个圆的周长同它的直径有一个固定的比例。我们的祖先很早就有的祖先很早就有“径一周三径一周三”的说法，就是说，假如一个圆的直径是的说法，就是说，假如一个圆的直径是1尺，那它的周长就是尺，那它的周长就是3尺。后来，人们发现这个说法并不准确。东汉的尺。后来，人

10、们发现这个说法并不准确。东汉的大科学家张衡认为应该是大科学家张衡认为应该是3.162。三国到西晋时期的数学家刘徽经过计算，。三国到西晋时期的数学家刘徽经过计算，求出了求出了3. 14159的圆周率，这在当时是最先进的，但是刘徽只算到这里的圆周率，这在当时是最先进的，但是刘徽只算到这里就没有继续算。祖冲之打算采用刘徽就没有继续算。祖冲之打算采用刘徽“割圆术割圆术”（在圆内做正（在圆内做正6边形，边形，6边形的周长刚好是直径的边形的周长刚好是直径的3倍，然后再做倍，然后再做12边形、边形、24边形边形边数越多，边数越多，它的周长就和圆的周长越接近）的方法算下去。它的周长就和圆的周长越接近）的方法算

11、下去。 在当时的情况下，不但没有计算机，也没有笔算，只能用长在当时的情况下，不但没有计算机，也没有笔算，只能用长4寸，寸，方方3寸的小竹棍来计算。工作是艰巨的，这时祖冲之的儿子也能帮助他寸的小竹棍来计算。工作是艰巨的，这时祖冲之的儿子也能帮助他了。了。 父子俩算了一天又一天，眼睛熬红了，人也渐渐瘦了下来，可大圆父子俩算了一天又一天，眼睛熬红了，人也渐渐瘦了下来，可大圆里的边形却越画越多，里的边形却越画越多，3072边、边、6144边边边数越多，边长越短。父子边数越多，边长越短。父子俩蹲在地上，一个认真地画，一个细心地算，谁也不敢走神。最后，他俩蹲在地上，一个认真地画，一个细心地算，谁也不敢走神

12、。最后，他们在那个大圆里画出了们在那个大圆里画出了24576边形，并计算出它的周长是边形，并计算出它的周长是3.1415926。 俩人看看摆在地上密密麻麻的小木棍，再看看画在地上的大圆里的俩人看看摆在地上密密麻麻的小木棍，再看看画在地上的大圆里的图形，高兴地笑了。图形，高兴地笑了。 后来，祖冲之推算出，后来，祖冲之推算出，49152边形的周长不会超过边形的周长不会超过3.1415927。所。所以，他得出结论，圆周率是在以，他得出结论，圆周率是在3.1415926和和3.1415927这两个数之间。这两个数之间。 祖冲之是世界上第一个计算圆周率精确到小数点后祖冲之是世界上第一个计算圆周率精确到小

13、数点后7位的人，比欧位的人，比欧洲人早了洲人早了1000多年，这是我国古代一项非常了不起的贡献！多年，这是我国古代一项非常了不起的贡献！ 祖冲之计算得出的密率分数近似值355/113 ，外国数学家获得同样结果，已是一千多年以后的事了为了纪念祖冲之的杰出贡献，有些外国数学史家建议把叫做祖率 祖冲之在天文历法方面的成就，祖冲之在天文历法方面的成就，大都包含在他所编制的大都包含在他所编制的大明历大明历及为及为大明历大明历所写的所写的驳议驳议中。中。 秦九韶算法秦九韶算法 设计求多项式设计求多项式f(x)=2x55x44x3+3x26x+7当当x=5时的值的算法，并写出程序。时的值的算法，并写出程序。

14、 一般的解决方案一般的解决方案 x=5;f=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7;f 上述算法一共做了解上述算法一共做了解15次乘法运算次乘法运算，5次加法运算次加法运算. 优点是简单，易懂优点是简单，易懂; 缺点是不通用，不能解决任意多项式缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。的求值问题，而且计算效率不高。有没有更高效的算法？有没有更高效的算法？ 用提取公因式的方法多项式变形为用提取公因式的方法多项式变形为 f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x

15、+7 =(2x5)x4)x+3)x6)x+7这样共作了这样共作了5次加法，次加法，5次乘法次乘法.第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运乘法的运算次数减少了算次数减少了,因而能提高运算效率因而能提高运算效率.而且对于而且对于计算机来说计算机来说,做一次乘法所需的运算时间比做一做一次乘法所需的运算时间比做一次加法要长得多次加法要长得多,因此第二种做法能更快地得到因此第二种做法能更快地得到结果结果.求多项式求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一:首先将原多项式改写成如下形式首先将原多项式改写成如下形式 : f(x)=

16、(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,当当x=5时时,多多项式的值是项式的值是2677.然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即这种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我们可以改写成如下形式我们可以改写成如下形式:f(x)=(anx+an-1)x+an-2)x+a

17、1)x+a0.求多项式的值时求多项式的值时,首先计算最内层括号内一首先计算最内层括号内一次多项式的值次多项式的值,即即 v1=v0 x+an-1,然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即一般地一般地,对于一个对于一个n次多项式次多项式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.这样这样,求求n次多项式次多项式f(x)的值就转化为求的值就转化为求n个个一次多项式的值一次多项式的值.这种算法称为这种算法称为秦九韶算法秦九韶算法.v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.观察上述秦九韶算法中的观察上述秦九韶算法中的n个一次式个一次式,可见可见vk的计算要用到的计算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步骤骤,因此可用循环结构来实现因此可用循环结构来实现.点评点