算法案例(第二课时)sakura概要课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例,（第二课时）,算法案例（第二课时）,1,秦九韶,南宋，数学家。他在1247年（淳佑七年）著成数书九章十八卷全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。这是一部划时代的巨着，它总结了前人在开方中所使用的列筹方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去，其中对大衍求一术一次同余组解法）和正负开方术高次方程的数值解法）等有十分深入的研究。其中的”大衍求一术”一次同余组解法），在世界数学史上占有崇高的地位。在古代孙子算经中载有”物不知数”这个问题，举例说明：有一数，三三数之余二，五五数之余二，七七数之余二，问此数为何？这一类问题的解法可以推广成解一次同余式组的一般方法奏九韶给出了理论上的证明，并将它定名为”大衍求一术”。,秦 九 韶,秦九韶,南宋，数学家。他在1247年（淳佑七年）著成数书九,2,计算多项式,（,）,=,当,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=,3,计算任意一个四次多项式当 x=5 时的值：,计算任意一个四次多项式当 x=5 时的值：,4,计算任意一个四次多项式当 x=5 时的值：,然后，由内到外逐层计算一次多项式的值，即,你从中看到了怎样的规律？怎么用程序框图来描述呢？,计算任意一个四次多项式当 x=5 时的值：然后，由内到外,5,数书九章秦九韶算法,设,是一个,n,次的多项式,对该多项式按下面的方式进行改写：,思考：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,数书九章秦九韶算法设是一个n次的多项式对该多项式按下,6,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个n次多项式,f,（x）的值转化成求n个一次多项式的值的方法，称为,秦九韶算法,。,思考：在求多项式的值上，这是怎样的一个转化？,要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内,7,例2 已知一个五次多项式为,用秦九韶算法求这个多项式当x=5的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x=5时的值：,所以，当x=5时，多项式的值等于17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,例2 已知一个五次多项式为用秦九韶算法求这个多项式当x=,8,开始,输入f(x)的系数：,a,0、,a,1、,a,2、,a,3、,a,4、,a,5,输入x,0,n=0,v=a,5,v=vx0+a5-n,n=n+1,n 5?,输出v,结束,否,是,注意：要想使用检验功能，请使用前，先要减低宏的安全限制,开始输入f(x)的系数：输入x0n=0v=a5v=vx,9,排序的算法,将下面数字按由小到大的顺序排列,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，,10,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,方法1：,过程演示,8,3,2,5,9,6,开始,排第1次,排第2次,排第3次,排第4次,8,3,2,5,9,6,3,8,2,5,9,6,2,3,8,5,9,6,2,3,5,8,9,6,2,3,5,8,9,6,排第5次,2,3,5,6,8,9,直接排序法,排序的算法将下面数字按由小到大的顺序排列8，3，2，5，9，,11,排序的算法,将下面数字按由小到大的顺序排列,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，,12,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第1趟,8,3,2,5,9,6,3,8,2,5,9,6,3,2,8,5,9,6,3,2,5,8,9,6,3,2,5,8,9,6,3,2,5,8,6,9,该趟中交换的次数为_次,4,排序的算法将下面数字按由小到大的顺序排列8，3，2，5，9，,13,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第2趟,3,2,5,8,6,9,2,3,5,8,6,9,2,3,5,8,6,9,2,3,5,8,6,9,2,3,5,6,8,9,2,3,5,6,8,9,该趟中交换的次数为_次,2,排序的算法将下面数字按由小到大的顺序排列8，3，2，5，9，,14,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第3趟,2,3,5,6,8,9,2,3,5,6,8,9,2,3,5,6,8,9,2,3,5,6,8,9,2,3,5,6,8,9,2,3,5,6,8,9,该趟中交换的次数为_次，,0,所以排序的结果为：,2，3，5，6，8，9,排序的算法将下面数字按由小到大的顺序排列8，3，2，5，9，,15,秦九韶的数学成就 宋理宗淳祐四年（1244年），十一月，秦九韶解官建康通判，回湖州丁母忧，一边为母亲守灵，一边把自己几十年勤奋学习、苦心钻研、实践、总结的数学成就结晶，精选出来的较有代表性的81个问题，分为9类，每类9题，编辑成18卷，淳祐七年，世界最高水平的数学名著数书九章成书。秦九韶在数学上的主要成就是系统地总结和发展了高次方程数值解法和一次同余组解法，提出了相当完备的“正负开方术”和“大衍求一术”，达到了当时世界数学的最高水平 秦九韶在前人工作的基础上，提出一套完整的利用随乘随加逐步求出高次方程正根的程序，亦称“正负开方术”，现称秦九韶法 这也是“增乘开方法”的主要特点。有人说，计算机发明以后，解方程变得有趣了确实是这样，秦九韶的高次方程数值解法，可以毫无困难地转化为计算机程序。在数书九章中，秦九韶列举了20多个解方程问题，次数最高达10次除一般方法外，还讨论了“投胎”、“换骨”、“玲珑”、“同体连枝”等特 殊情形，并将其广泛应用于面积、体积、测量等方面的实际问题在西方，关于高次方程数值解法的探讨，经历了漫长的历史过程，直到1840年，意大利数学家P鲁菲尼(Ruffini，1765-1822)才创立了一种逐次近似法解决数字高次方程无理数根的近似值问题，而1819年英国数学家WG霍纳(Horner，17861837)在英国皇家学会发表的论文“用连续逼近法解任何次数字方程的新方法”中，才提出与增乘开方法演算步骤相同的算法，后被称为“霍纳法”秦九韶的成就要比鲁菲尼和霍纳早五六百年。秦九韶对于一次同余组解法的理论概括，是他在数学史上的另一杰出贡献中算家对于一次同余式问题解法的研究是适应天文学家推算上元积年的需要而产生的最早见于记载的一次同余问题是孙子算经中的“物不知数问题”(亦称“孙子问题”)：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几有何？”这相当于求解一次同余组。秦九韶的大衍求一术与他的高次方程数值解法一样，简洁、明确、带有很强的机械性，其程序亦可毫无因难地转化为算法语言，用计算机来实现在数书九章中，秦九韶通过大量例题，如“古历会积”、“治历演纪”“积尺寻源”、“推计土功”、“程行计地”等等，展示了大衍求一术在解决历法、工程、赋役和军旅等实际问题中的广泛应用由于在许多问题中，模数Ai并非两两互素，而中国传统数学没有素数概念，所以将模数化为两两互素是相当困难的问题秦九韶所设计的将模数比为两两互素的算法，尽管还不完善，但仍比较成功地解决了这一难题，有人称之为“没有素数的素数论”。综观他在求解一次同余组问题的各项成就，正如中科院研究员李文林、袁向东所说：“所有这些系统的理论，周密的考虑，即使以今天的眼光看来也很不简单，充分显示了秦九韶高超的数学水平和计算技巧。”在西方，最早接触一次同余式的是意大利数学家L斐波那契(Fibonacci，约1170-1250)他在算盘书中给出了两个一次同余问题，但没有一般算法直到1819世纪，L欧拉(Euler，1743)、GF高斯(Gauss，1801)才对一次同余组进行深入研究，重新获得与中国剩余定理相同的定理，并对模数两两互素的情形给出了严格证明。1852年，英国传教士、汉学家伟烈亚力(AWylie，1815-1887)发表中国数学科学札记(Jottings on the science of Chinese arithmetic)，其中谈到了大衍求一术从1856年到1876年，德国人L马蒂生(Matthiessen，1830-1906)等西方学者又多次指出大衍求一术原理与高斯方法的一致性，从而更加引起了欧洲学者的瞩目德国著名数学史家M康托尔(Cantor，1829-1920)高度评价了大衍求一术，他称赞发现这一算法的中国数学家是“最幸运的天才”。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。数书九章中，除了前面提到的大衍求一术和正负开方术两项重要成就外，还记载了不少其他方面的成就例如，他改进了线性方程组的解法，普遍应用互乘相消法代替传统的直除法，已同今天所用的方法完全一致；在开方中，他发展了刘徽开方不尽求微数的思想，最早使用十进小数来表示无理根的近似值；他对于九章算术和海岛算经的勾股测量术也多所阐发；他在几何方面的另一项杰出成果是“三斜求积术”，即已知三角形三边之长求其面积的公式。数书九章的内容非常丰富，我们不仅可以找到数学和天文历法乃至雨雪量等方面的珍贵资料，而且还可以从中了解到南宋时期户口增长、耕地扩展、赋税、利贷、度量衡以及货币流通、海外贸易等等社会经济领域的真实情况。,秦九韶的数学成就 宋理宗淳祐四年（12,16,