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

Bqr6401@126.com 普通高中课程标准 Liangxiangzhongxue 良乡中学数学组 任宝泉 　　　　　　　　　　　　　　　　 良乡中学数学组 制作：任宝泉 　　　　　　　　　　　　　　　　 普通高中课程标准数学3(必修) * 书 山 有 路 勤 为 径，学 海 无 崖 苦 作 舟 少 小 不 学 习，老 来 徒 伤 悲 成功=艰苦的劳动+正确的方法+少谈空话 天才就是百分之一的灵感，百分之九十九的汗水！ 天 才 在 于 勤 奋，努 力 才 能 成 功！ 勤劳的孩子展望未来, 但懒惰的孩子享受现在!!! 什 么 也 不 问 的 人 什 么 也 学 不 到 !!! 怀 天 下 ， 求 真 知 ， 学 做 人 1.3 中国古代数学中的算法案例 第一章 算法初步 一、复习引入 下面我们举一些我国古代代数学中“算法”的例子，让同学们体会“算法”的概念，看一看中国古代数学在算法上的伟大成就。 我们在小学、中学学到的算术、代数，从计数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年。我国人民在长期的生活、生产和劳动中，创造了很多数学的计算和思想方法。 二、提出问题 本节主要介绍的内容 一、更相减损之术（又称“等值算法”） ----研究如何求二个正整数的最大公约数。 二、割圆术 ----解决圆周率π的近似值问题。 三、秦九韶算法 ----解决求多项式函数值问题。 三、概念形成 概念1.求两个正整数的最大公约数 你记得在小学里是如何求最大公约数吗？ 对了，用短除法。例如求18和30的最大公约数： 所以，18与30的最大公约数是2×3=6。 这个方法可以总结为：用两个数连续除以他们的公约数，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。 三、概念形成 概念1.求两个正整数的最大公约数 当两个数比较大时（如8610与6300），使用上述方法求最大公约数就比较困难。下面我们介绍两种古老而有效的算法——辗转相除法与更相减损术。 （1）辗转相除法(*) 例子:辗转相除法求8610和6300的最大公约数。 为了简洁，我们把8610和6300的最大公约数记作（8610，6300）。 把8610变为下式 8610 = 6300×1 + 2310 三、概念形成 概念1.求两个正整数的最大公约数 我们来看一下（8610，6300）和（6300，2310）之间的关系 它们有相同的公约数，因此也有相同的最大公约数。难道这只是巧合吗? 可以证明它们有相同的公约数（略）。 三、概念形成 我们可以总结为： （被除数，除数）=（除数，余数） 概念1.求两个正整数的最大公约数 据此，我们可以用如下办法求8610和6300的最大公约数： 被除数 除数 余数 （8610，6300） 8610 = 6300×1 + 2310 =（6300，2310） 6300 = 2310×2 + 1680 =（2310，1680） 2310 = 1680×1 + 630 =（1680，630） 1680 = 630×2 + 420 =（630，420） 630 = 420×1 + 210 =（420，210） 420 = 210×2 + 0 =210 最大公约数 这就是辗转相除法。由除法的性质可知，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出最大公约数。 三、概念形成 辗转相除法算法分析 概念1.求两个正整数的最大公约数 从上面例子可以看出，辗转相除法中也包含重复的操作，因此可以用循环结构来构造算法。 S1：给定两个正数m，n。 S2：计算m 除以n所得的余数r。 S3：m=n，n=r。 S4：若r=0，则m，n的最大公约数等于m；否则，返回S2。 r = 0 ? n =r m =n r = m MOD n 输入：m，n 输出：m 开始 结束 三、概念形成 辗转相除法的Siclab程序 概念1.求两个正整数的最大公约数 r = 0 ? n =r m =n r = m MOD n 输入：m，n 输出：m 开始 结束 m=input(m=); n=input(n=); if m