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

中国古代数学中的算法案例 最大公约数 定义 如果有一个自然数a能被自然数b整除 则称a为b的倍数 b为a的约数 几个自然数公有的约数 叫做这几个自然数的公约数 公约数中最大的一个公约数 称为这几个自然数的最大公约数 更相减损术 出自 九章算术 求得最大公约数的方法 辗转相除法 欧几里得算法 更相减损术 简介 更相减损术是出自 九章算术 的一种求最大公约数的算法 它原本是为约分而设计的 但它适用于任何需要求最大公约数的场合 如何使用 求98与63的最大公约数 98 63 35 63 35 2835 28 7 28 7 2121 7 14 14 7 7 98 63 63 35 35 28 28 7 14 7 98和63的最大公约数等于7 1 求16与12的最大公约数 2 求78与36的最大公约数 更相减损术步骤 1 大数减小数 2 差数和较小的数再组成数对 大数减小数 3 产生的一对相等数就是最大公约数 得与有相同的公约数 理论依据 算法表示 S1 输入两个正数a b a b S2 如果a b 则执行S3 否则转到S5 S3 将a b的值赋予r S4 若b r 则把b赋予a 把r赋予b 否则把r赋予a 重新执行S2 S5 输出最大公约数b 输出b Y N 输入a b a b 结束 开始 a b b b a a a b Y N 程序 a input a b input b whileabifa ba a b elseb b a endendprint io 2 b 两数的最大公约数为 辗转相除法 辗转相除法 辗转相除法最早出现在欧几里得的几何原本中 大约公元前300年 所以它是现在仍在使用的算法中最早出现的 欧几里得 如何使用 以求288和123的最大公约数为例 操作如下 S1 288 123 2 42S2 123 42 2 39S3 42 39 1 3S4 39 3 13 288 123 123 42 42 39 39 3 3就是288和123的最大公约数 这是一个辗转相处的过程 辗转相除的步骤 1 大数除以小数 求余数 2 用余数和较小的数组成一对 再用大数除以小数 求余数 3 直到余数为0 4 最后一个除数为最大公约数 1 求98与63的最大公约数 2 求78与36的最大公约数 理论依据 得与有相同的公约数 第一步 输入两个正整数a b a b 第二步 求出a b的余数r 第三步 令a b b r 若r 0 重复第二步 第四步 输出最大公约数a 更相减损术和辗转相除法的主要区别在于 前者所使用的运算是 减 后者是 除 从算法思想上看 两者并没有本质上的区别 但是在计算过程中 如果遇到一个数很大 另一个数比较小的情况 可能要进行很多次减法才能达到一次除法的效果 所以辗转相除法更好一些 割圆术 早在我国先秦时期 墨经 上就已经给出了圆的定义 我国古代数学经典 九章算术 在第一章 方田 章中写到 半周半径相乘得积步 也就是我们现在所熟悉的公式 为了证明这个公式 我国魏晋时期数学家刘徽写了一篇1800余字的注记 这篇注记就是数学史上著名的 割圆术 刘徽形容他的 割圆术 说 割之弥细 所失弥少 割之又割 以至于不可割 则与圆合体 而无所失矣 简单来说所谓 割圆术 是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法 计算方法 第一 从半径为1的圆内接正六边形开始 计算它的面积S6 第二 逐步加倍圆内接正多边形的边数 分别计算圆内接正十二边形 正二十四边形 正四十八边形 的面积 到一定的边数 设为2m 为止 得到一列递增的数 S6 S12 S24 S48 S2n 第三 S2n近似等于圆面积 下面的关键是找出正n边形的面积与正2n边形的面积之间的关系 以便递推 设圆的半径为1 正n边形的边长AB为xn 弦心距OG为hn 面积为Sn 根据勾股定理 得 容易知道x6 1 正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积 即 于是由 求得S12 3 S24 3 105828 按照这样的思路 刘徽把圆内接正多边形的面积一直算到了正3072边形 并由此而求得了圆周率为3 14和3 1416这两个近似数值 这个结果是当时世界上圆周率计算的最精确的数据 n 6 x 1 s 6 sqrt 3 4 fori 1 1 5h sqrt 1 x 2 2 s s n x 1 h 2 n 2 n x sqrt x 2 2 1 h 2 endprint io 2 n s 程序编写 秦九韶算法 秦九韶 1208年 1261年 南宋官员 数学家 与李冶 杨辉 朱世杰并称宋元数学四大家 字道古 汉族 自称鲁郡 今山东曲阜 人 生于普州安岳 今属四川 精研星象 音律 算术 诗词 弓剑 营造之学 历任琼州知府 司农丞 后遭贬 卒于梅州任所 著作 数书九章 其中的大衍求一术 三斜求积术和秦九韶算法是具有世界意义的重要贡献 人物介绍 数书九章 在数学内容上颇多创新 中国算筹式记数法及其演算式在此得以完整保存 自然数 分数 小数 负数都有专条论述 还第一次用小数表示无理根的近似值 卷1大衍类中灵活运用最大公约数和最小公倍数 并首创连环求等 借以求几个数的最小公倍数 在 孙子算经 中 物不知数 问题的基础上总结成大衍求一术 使一次同余式组的解法规格化 程序化 比西方高斯创用的同类方法早500多年 被公认为 中国剩余定理此外 秦九韶还改进了一次方程组的解法 用互乘对减法消元 与现今的加减消元法完全一致 成就 已知一个一元n次多项式函数 P x anxn an 1xn 1 a1x ao 当知道x值时 我们可以按顺序一项一项的计算 然后相加 求出P x 秦九韶算法 设有n 1项的n次函数 即 再将括号内的前n 1项提取公因数x 得 将前n项提取公因数x 得 秦九韶算法 如此反复提取公因数x 最后将函数化为 则 fn即为所求 秦九韶算法 怎样用程序框图表示秦九韶算法 观察秦九韶算法的数学模型 计算vk时要用到fk 1的值 若令f0 an 我们可以得到下面的递推公式 f0 anfk fk 1 x an k k 1 2 n 这是一个在秦九韶算法中反复执行的步骤 可以用循环结构来实现 用秦九韶方法求多项式 开始 输入x n a0 a1 a2 an k k 1 f f x ak 输出S 结束 k n f an 开始 输入x n a0 a1 a2 an k 0 是 否 Scilab语言 x input x n input n result input Thefirstxishu fori 1 1 na input xishu result result x a enddisp result Theresultis n input n 输入多项式次数a zeros 1 n 1 定义带下标的变量fori 1 1 n 1a i input a i 顺次输入系数a0 a1 anendx input x 输入自变量的值y a n 1 fori 1 1 ny y x a n 1 i endy 这种计算方法 称之为秦九韶方法 直到今天 这