算法案例(第二课时)sakura.ppt

算法案例 第二课时 秦九韶 计算多项式 当x 5的值 算法1 因为 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 算法2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 分析 两种算法中各用了几次乘法运算 和几次加法运算 计算任意一个四次多项式当x 5时的值 计算任意一个四次多项式当x 5时的值 然后 由内到外逐层计算一次多项式的值 即 你从中看到了怎样的规律 怎么用程序框图来描述呢 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 这是怎样的一种改写方式 最后的结果是什么 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考 在求多项式的值上 这是怎样的一个转化 例2已知一个五次多项式为 用秦九韶算法求这个多项式当x 5的值 解 将多项式变形 按由里到外的顺序 依此计算一次多项式当x 5时的值 所以 当x 5时 多项式的值等于17255 2 你从中看到了怎样的规律 怎么用程序框图来描述呢 开始 输入f x 的系数 a0 a1 a2 a3 a4 a5 输入x0 n 0 v a5 v v x0 a5 n n n 1 n 5 输出v 结束 否 是 注意 要想使用检验功能 请使用前 先要减低宏的安全限制 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 方法1 S1 比较第2个数与第1个数的大小 并排序得3 8 S2 将第3个数与S1中的数比较 插入适当的位置 得到2 3 8 S3 将第4个数与S2中的数比较 并插入适当的位置 如此继续下去 直到把最后一个数插入到上一步已排好的数列的合适位置为止 得到 2 3 5 8 2 3 5 8 9 2 3 5 6 8 9 S4 S5 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 方法1 过程演示 开始 排第1次 排第2次 排第3次 排第4次 排第5次 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 方法2 S1 用第1个数与第2个数比较 若前者小则两数不变 否则 交换这两个数的位置 S2 按这样的原则 比较第2个数和第3个数 前者小则两数不变 否则 交换这两个数的位置 直到比完最后两个数 称为 一趟 S3 如果前一趟的比较中交换的次数为0 说明排序已完成 否则回到S2 根据题意 一趟后的结果是什么 为什么说前一趟的比较中交换为0次时 排序完成 3 2 5 8 6 9 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 请将每一趟的结果写出来 第1趟 该趟中交换的次数为 次 4 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 请将每一趟的结果写出来 第2趟 该趟中交换的次数为 次 2 排序的算法 将下面数字按由小到大的顺序排列 8 3 2 5 9 6 请将每一趟的结果写出来 第3趟 该趟中交换的次数为 次 0 所以排序的结果为 2 3 5 6 8 9 秦九韶的数学成就宋理宗淳祐四年 1244年 十一月 秦九韶解官建康通判 回湖州丁母忧 一边为母亲守灵 一边把自己几十年勤奋学习 苦心钻研 实践 总结的数学成就结晶 精选出来的较有代表性的81个问题 分为9类 每类9题 编辑成18卷 淳祐七年 世界最高水平的数学名著 数书九章 成书 秦九韶在数学上的主要成就是系统地总结和发展了高次方程数值解法和一次同余组解法 提出了相当完备的 正负开方术 和 大衍求一术 达到了当时世界数学的最高水平 秦九韶在前人工作的基础上 提出一套完整的利用随乘随加逐步求出高次方程正根的程序 亦称 正负开方术 现称秦九韶法 这也是 增乘开方法 的主要特点 有人说 计算机发明以后 解方程变得有趣了 确实是这样 秦九韶的高次方程数值解法 可以毫无困难地转化为计算机程序 在 数书九章 中 秦九韶列举了20多个解方程问题 次数最高达10次 除一般方法外 还讨论了 投胎 换骨 玲珑 同体连枝 等特殊情形 并将其广泛应用于面积 体积 测量等方面的实际问题 在西方 关于高次方程数值解法的探讨 经历了漫长的历史过程 直到1840年 意大利数学家P 鲁菲尼 Ruffini 1765 1822 才创立了一种逐次近似法解决数字高次方程无理数根的近似值问题 而1819年英国数学家W G 霍纳 Horner 1786 1837 在英国皇家学会发表的论文 用连续逼近法解任何次数字方程的新方法 中 才提出与增乘开方法演算步骤相同的算法 后被称为 霍纳法 秦九韶的成就要比鲁菲尼和霍纳早五六百年 秦九韶对于一次同余组解法的理论概括 是他在数学史上的另一杰出贡献 中算家对于一次同余式问题解法的研究是适应天文学家推算上元积年的需要而产生的 最早见于记载的一次同余问题是 孙子算经 中的 物不知数问题 亦称 孙子问题 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几有何 这相当于求解一次同余组 秦九韶的大衍求一术与他的高次方程数值解法一样 简洁 明确 带有很强的机械性 其程序亦可毫无因难地转化为算法语言 用计算机来实现 在 数书九章 中 秦九韶通过大量例题 如 古历会积 治历演纪 积尺寻源 推计土功 程行计地 等等 展示了大衍求一术在解决历法 工程 赋役和军旅等实际问题中的广泛应用 由于在许多问题中 模数Ai并非两两互素 而中国传统数学没有素数概念 所以将模数化为两两互素是相当困难的问题 秦九韶所设计的将模数比为两两互素的算法 尽管还不完善 但仍比较成功地解决了这一难题 有人称之为 没有素数的素数论 综观他在求解一次同余组问题的各项成就 正如中科院研究员李文林 袁向东所说 所有这些系统的理论 周密的考虑 即使以今天的眼光看来也很不简单 充分显示了秦九韶高超的数学水平和计算技巧 在西方 最早接触一次同余式的是意大利数学家L 斐波那契 Fibonacci 约1170 1250 他在 算盘书 中给出了两个一次同余问题 但没有一般算法 直到18 19世纪 L 欧拉 Euler 1743 G F 高斯 Gauss 1801 才对一次同余组进行深入研究 重新获得与中国剩余定理相同的定理 并对模数两两互素的情形给出了严格证明 1852年 英国传教士 汉学家伟烈亚力 A Wylie 1815 1887 发表 中国数学科学札记 JottingsonthescienceofChinesearithmetic 其中谈到了大衍求一术 从1856年到1876年 德国人L 马蒂生 Matthiessen 1830 1906 等西方学者又多次指出大衍求一术原理与高斯方法的一致性 从而更加引起了欧洲学者的瞩目 德国著名数学史家M 康托尔 Cantor 1829 1920 高度评价了大衍求一术 他称赞发现这一算法的中国数学家是 最幸运的天才 从此 中国古代数学的这一创造逐渐受到世界学者的瞩目 并在西方数学史著作中正式被称为 中国剩余定理 数书九章 中 除了前面提到的大衍求一术和正负开方术两项重要成就外 还记载了不少其他方面的成就 例如 他改进了线性方程组的解法 普遍应用互乘相消法代替传统的直除法 已同今天所用的方法完全一致 在开方中 他发展了刘徽开方不尽求微数的思想 最早使用十进小数来表示无理根的近似值 他对于