高中数学 第一章 算法初步 3 算法案例课件 新人教B版必修3.ppt

1 3中国古代数学中的算法案例 1 理解算法案例的算法步骤和程序框图 2 引导学生得出自己设计的算法程序 新课讲授部分 讲解两种算法的应用与优点 例题部分 通过典例讲解让学生熟悉两种中国古代算法 复习巩固部分通过练习对知识巩固 让学生更系统掌握本节课的所学知识 算法案例一更相减损之术 等值算法 思考1小学学过的求两个数的最大公约数的方法是怎样呢 先用两个公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 解答 例1 求下面两个正整数的最大公约数 1 求25和35的最大公约数 2 求49和63的最大公约数 所以 25和35的最大公约数为5 所以 49和63的最大公约数为7 解答 思考2如何算出98与63的最大公约数 除了用这种方法外还有没有其他方法 辗转相除法 解答 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所以 98和63的最大公约数等于7 思考3什么是更相减损之术 有什么具体作用呢 解答 所谓更相减损之术 就是对给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 更相减损之术 是我国古代数学算法的叫法 现代数学中称作等值算法 主要的作用是求两个正整数的最大公约数 思考4你能根据更相减损之术设计程序 求两个正整数的最大公约数吗 程序 a input pleasegivethefirstnumber b input pleasegivethesecondnumber Whileabifa ba a b elseb b a endendprint io 2 a b 算法案例二秦九韶算法 思考1想想怎样求多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 算法1 计算多项式 x x x x x 1当x 5的值的算法 因为 x x x x x 1 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 解答 算法2 5 55 54 53 52 5 5 54 53 52 5 5 5 5 52 5 5 5 5 52 5 5 5 5 5 5 思考2两种算法各用了几次乘法运算和几次加法运算 算法一共做了1 2 3 4 10次乘法运算 5次加法运算 算法二共做了4次乘法运算 5次加法运算 解答 通过对比 很明显 算法二比算法一优越 这种算法就是秦九韶算法 对该多项式按下面的方式进行改写 思考3秦九韶算法的概念和特点是怎样的呢 解答 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 秦九韶算法的特点 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做n次乘法和n次加法即可 另外这种算法还避免了对自变量x单独做幂的计算 而是与系数一起逐次增长幂次 从而可提高计算的精度 例2 已知一个五次多项式为 用秦九韶算法求这个多项式当x 0 2的值 将多项式变形 解答 所以 当x 0 2时 多项式的值等于0 81873 1 在对16和12求最大公约数时 整个操作如下 16 12 4 12 4 8 4 4 由此可以看出12和16的最大公约数是 A 4B 12C 16D 8 A 2 已知一个5次多项式为用秦九韶算法求f 5 的值 解 f x 5x 2 x 3 5 x 2 6 x 1 7 x 0 8 v1 5 5 2 27 v2 27 5 3 5 138 5 v3 138 5 5 2 6 689 9 v4 689 9 5 1 7 3451 2 v5 3451 2 5 0 8 17255 2 所以f 5 17255 2 1 近三年各地的高考中 对算法案例都不作考查 高考虽然没有考查 但在平时的考试中通常以选择或填空的形式出现 且难度适中 2 我们学习算法案例 主要是为了进一步理解算法的思想 能够用程序来解决生活中常见的数学问题 所以应该认真学习