中国古代算法案例1

1.3 1.3 中国古代数学中国古代数学中的算法案例中的算法案例oo 我国人民在长期的生活，生产和劳动过我国人民在长期的生活，生产和劳动过程中，创造了整数、分数、小数、正负数程中，创造了整数、分数、小数、正负数的概念及其运算，在代数学、几何学等方的概念及其运算，在代数学、几何学等方面，我国在宋，元之前也都处于世界的前面，我国在宋，元之前也都处于世界的前列。我们在小学、中学学到的算术，代数，列。我们在小学、中学学到的算术，代数，从记数到多元一次联立方程的求根方法，从记数到多元一次联立方程的求根方法，都是我国古代数学家最先创造的。更为重都是我国古代数学家最先创造的。更为重要的是我国古代数学的开展有着自己鲜明要的是我国古代数学的开展有着自己鲜明的特色，也就是的特色，也就是“寓理于算，即把解决寓理于算，即把解决的问题的问题“算法化。算法化。3 59 15 问题问题1 1：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？18 30231818和和3030的最大公约的最大公约数是数是23=6.23=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到所得一直除到所得的商是互质数为止的商是互质数为止,然后然后把所有的除数连乘起来把所有的除数连乘起来.问题问题2:2:我们都是利用找公约数的方法来求最大我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比方求的最大公约数？比方求82518251与与61056105的最大公约数的最大公约数?1、求两个正整数的最大公约数的算法、求两个正整数的最大公约数的算法我国早期也有解决求最大公约数问题的算法，我国早期也有解决求最大公约数问题的算法，就是更相减损术。就是更相减损术。更相减损术求最大公约数的步骤如下：更相减损术求最大公约数的步骤如下：可半者半可半者半之，不可半者，副置分母之，不可半者，副置分母子之数，以少减多，更相子之数，以少减多，更相减损，求其等也，以等数约之。减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。假设是，用们是否都是偶数。假设是，用2 2约简；假设不是，执行第约简；假设不是，执行第二步。二步。第二步：以较大的数减去较小的数，接着把较小的第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，那么这个数等数就是所求的最到所得的数相等为止，那么这个数等数就是所求的最大公约数。大公约数。更相减损术更相减损术oo例1 用更相减损术求91与49的最大公约数.oo解：由于49不是偶数，把91和49以大数减小数，并辗转相减，oo即：914942 49427 42735 oo 35728 28721 21714oo 1477oo所以，91与49的最大公约数是7。更相减损术更相减损术练习练习1 1 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减，即：即：986335;633528;35287;28721;21714;1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习练习2 2：用更相减损术求两个正数：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。(12)(12)我国魏晋时期的数学家刘徽，他在注我国魏晋时期的数学家刘徽，他在注?九九章算术章算术?中采用正多边形面积逐渐逼近圆面积中采用正多边形面积逐渐逼近圆面积的算法计算圆周率的算法计算圆周率，用刘徽自己的原话就，用刘徽自己的原话就是：是：“割之弥细，所失弥少；割之又割，以割之弥细，所失弥少；割之又割，以至于不可割，那么与圆合体而无所失矣至于不可割，那么与圆合体而无所失矣 ，这段注文充分说明了刘徽对极限概念这段注文充分说明了刘徽对极限概念.他的他的思想后来又得到祖冲之的推进和开展，计算思想后来又得到祖冲之的推进和开展，计算出圆周率的近似值在世界上很长时间里处于出圆周率的近似值在世界上很长时间里处于领先地位。领先地位。2.刘徽割圆术刘徽割圆术2.刘徽割圆术刘徽割圆术一、刘徽首先指出利用一、刘徽首先指出利用=3=3这一数值算得的这一数值算得的结果不是圆面积，而是圆内接正十二边形的结果不是圆面积，而是圆内接正十二边形的面积，这个结果比面积，这个结果比的真值少的真值少.二、他由圆内接正六边形算起，逐渐把边数二、他由圆内接正六边形算起，逐渐把边数加倍，逐个算出正加倍，逐个算出正1212边形、正边形、正2424边形、正边形、正4848边形、正边形、正9696边形边形的面积，这些面积会逐的面积，这些面积会逐渐地接近圆面积渐地接近圆面积.最后求出圆面积的近似值。最后求出圆面积的近似值。三、正三、正6边形一边恰与半径等长边形一边恰与半径等长)即求得正即求得正12边形边长，边形边长，.由正由正12边形求正边形求正24边形一边之长时，刘徽反复地边形一边之长时，刘徽反复地应用到勾股定理或称商高、勾股定理，如图：应用到勾股定理或称商高、勾股定理，如图：割圆术。不断地利用勾股定理，来计算割圆术。不断地利用勾股定理，来计算正正N边形的边长。边形的边长。刘徽先将直径为刘徽先将直径为2 2的圆分割为的圆分割为6 6等分，等分，再分割成再分割成1212等分，等分，2424等分，等分，.，这样，这样继续下去，并利用勾股定理计算其面积，继续下去，并利用勾股定理计算其面积，从而求出圆周率的近似值，他一直计算从而求出圆周率的近似值，他一直计算到圆内接正到圆内接正192192边形的面积。因为圆的边形的面积。因为圆的半径为半径为1 1，所以随着边数的增大，面积，所以随着边数的增大，面积不断趋近于圆周率，这样不断计算下去，不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值。就可以得到越来越精密的圆周率近似值。祖冲之 祖冲之祖冲之:公元公元429-500年是我国南北朝时年是我国南北朝时期，河北省涞源县人他从小就阅读期，河北省涞源县人他从小就阅读了许多天文、数学方面的书籍，勤奋了许多天文、数学方面的书籍，勤奋好学，刻苦实践，终于使他成为我国好学，刻苦实践，终于使他成为我国古代杰出的数学家、天文学家古代杰出的数学家、天文学家 圆周率是指圆周率是指平面平面上圆的上圆的周长周长与直径之比。早在一千四百多年与直径之比。早在一千四百多年以前，我国古代著名的数学家祖以前，我国古代著名的数学家祖冲之，就精密地计算出圆的周长冲之，就精密地计算出圆的周长是它直径的倍之间。这是当时世是它直径的倍之间。这是当时世界上算得最精确的数值界上算得最精确的数值-圆周圆周率。率。“圆周率是说一个圆的周长同它的直径有一个固定的比例。我们的圆周率是说一个圆的周长同它的直径有一个固定的比例。我们的祖先很早就有祖先很早就有“径一周三的说法，就是说，假设一个圆的直径是径一周三的说法，就是说，假设一个圆的直径是1尺，尺，那它的周长就是那它的周长就是3尺。后来，人们发现这个说法并不准确。东汉的大科学尺。后来，人们发现这个说法并不准确。东汉的大科学家张衡认为应该是家张衡认为应该是3.162。三国到西晋时期的数学家刘徽经过计算，求出。三国到西晋时期的数学家刘徽经过计算，求出了了3.14159的圆周率，这在当时是最先进的，但是刘徽只算到这里就没的圆周率，这在当时是最先进的，但是刘徽只算到这里就没有继续算。祖冲之打算采用刘徽有继续算。祖冲之打算采用刘徽“割圆术在圆内做正割圆术在圆内做正6边形，边形，6边形边形的周长刚好是直径的的周长刚好是直径的3倍，然后再做倍，然后再做12边形、边形、24边形边形边数越多，它边数越多，它的周长就和圆的周长越接近的方法算下去。的周长就和圆的周长越接近的方法算下去。在当时的情况下，不但没有计算机，也没有笔算，只能用长在当时的情况下，不但没有计算机，也没有笔算，只能用长4寸，寸，方方3寸的小竹棍来计算。工作是艰巨的，这时祖冲之的儿子也能帮助他了。寸的小竹棍来计算。工作是艰巨的，这时祖冲之的儿子也能帮助他了。父子俩算了一天又一天，眼睛熬红了，人也渐渐瘦了下来，可大圆父子俩算了一天又一天，眼睛熬红了，人也渐渐瘦了下来，可大圆里的边形却越画越多，里的边形却越画越多，3072边、边、6144边边边数越多，边长越短。父子边数越多，边长越短。父子俩蹲在地上，一个认真地画，一个细心地算，谁也不敢走神。最后，他俩蹲在地上，一个认真地画，一个细心地算，谁也不敢走神。最后，他们在那个大圆里画出了们在那个大圆里画出了24576边形，并计算出它的周长是边形，并计算出它的周长是3.1415926。俩人看看摆在地上密密麻麻的小木棍，再看看画在地上的大圆里的俩人看看摆在地上密密麻麻的小木棍，再看看画在地上的大圆里的图形，快乐地笑了。图形，快乐地笑了。后来，祖冲之推算出，后来，祖冲之推算出，49152边形的周长不会超过边形的周长不会超过3.1415927。所以，。所以，他得出结论，圆周率是在他得出结论，圆周率是在3.1415926和和3.1415927这两个数之间。这两个数之间。祖冲之是世界上第一个计算圆周率精确到小数点后祖冲之是世界上第一个计算圆周率精确到小数点后7位的人，比欧位的人，比欧洲人早了洲人早了1000多年，这是我国古代一项非常了不起的奉献！多年，这是我国古代一项非常了不起的奉献！祖冲之计算得出的密率分数近似值355/113，外国数学家获得同样结果，已是一千多年以后的事了为了纪念祖冲之的杰出奉献，有些外国数学史家建议把叫做祖率 祖冲之在天文历法方面的成就，祖冲之在天文历法方面的成就，大都包含在他所编制的大都包含在他所编制的?大明历大明历?及及为为?大明历大明历?所写的所写的?驳议驳议?中。中。oo秦九韶秦九韶 公元公元1202-12611202-1261年南宋，数学家。他在年南宋，数学家。他在12471247年年淳佑七年著成数书九章十八卷全书共淳佑七年著成数书九章十八卷全书共8181道题，道题，分为九大类：大衍类、天时类、田域类、测望类、赋役分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。这是一部划时类、钱谷类、营建类、军旅类、市易类。这是一部划时代的巨著，它总结了前人在开方中所使用的列筹方法，代的巨著，它总结了前人在开方中所使用的列筹方法，将其整齐而有系统地应用到高次方程的有理或无理根的将其整齐而有系统地应用到高次方程的有理或无理根的求解上去，其中对大衍求一术求解上去，其中对大衍求一术一次同余组解法一次同余组解法和正负开方术和正负开方术高次方程的数值解法等有十分深高次方程的数值解法等有十分深入的研究。其中的入的研究。其中的“大衍求一术大衍求一术一次同余组解法，一次同余组解法，在世界数学史上占有崇高的地位。在世界数学史上占有崇高的地位。3.秦九韶算法秦九韶算法秦九韶算法秦九韶算法 设计求多项式设计求多项式f(x)=2x55x44x3+3x26x+7当当x=5时的值的算法，并写出程序。时的值的算法，并写出程序。一般的解决方案一般的解决方案 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+7 =(2x5)x4)x+3)x6)x+7这样共作了这样共作了5次加法，次加法，5次乘法次乘法.第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运乘法的运算次数减少了算次数减少了,因而能提高运算效率因而能提高运算效率.而且对于而且对于计算机来说计算机来说,做一次乘法所需的运算时间比做做一次乘法所需的运算时间比做一次加法要长得多一次加法要长得多,因此第二种做法能更快地因此第二种做法能更快地得到结果得到结果.求多项式求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一:首先将原多项式改写成如下形式首先将原多项式改写成如下形式:f(x)=(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+a1)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)这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步骤骤,因此可用循环结构来实现因此可用循环结构来实现.点评点评:秦九韶算法是求一元多项式的秦九韶算法是求一元多项式的值的一种方法值的一种方法.它的特点是它的特点是:把求一个把求一个n次多项式的值次多项式的值转化为求转化为求n个一次多项式的值个一次多项式的值,通过这种转通过这种转化化,把运算的次数由至多把运算的次数由至多1+2+3+n=n(n+1)/2次乘法运算和次乘法运算和n次加法运算次加法运算,减少为减少为n次乘法运算和次乘法运算和n次加次加法运算法运算,大大提高了运算效率大大提高了运算效率.直到今天，这种算法仍是世界上多直到今天，这种算法仍是世界上多项式求值的最先进的算法。项式求值的最先进的算法。