辽宁省大连市第二十四中学高考数学复习《古代算法》课件.ppt

古代算法案例 1 回顾算法的四种表示方法 1 自然语言 3 程序框图 4 程序语言 三种逻辑结构 五种基本语句 复习引入 2 数学语言 x 5 y 20 ifx 0 x y 3 elsey y 3 endprint io 2 x y y x b 复习引入 d 3 执行如图的程序 最后一个输出的数是多少 1999 2002 复习引入 c 复习引入 c 高考真题 b 高考真题 c 高考真题 d 高考真题 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 九章算术 中的更相减损术 背景介绍 一 求两个正整数最大公约数的算法 1 更相减损术 等值算法 例如 求78和36的最大公约数 操作如下 78 36 42 36 6 36 6 30 6 24 6 18 6 12 6 6 原理 对任意两个数 每次操作后所得的两数与前两数有相同的最大公约数 而两数的值逐渐减小 经过有限步的操作后 总能得到相等的两个数 即求得两数的最大公约数 7步 算法如下 s1输入两个正数a b s2如果a b 则执行s3 否则转到s5 s3若a b 则把a b的值重新赋予a 否则 a b 则把b a重新赋予b 重新执行s2 s5输出最大公约数 程序框图 程序语言 a input a b input b whileabifa ba a b elseb b a endendprint io 2 a 两数的最大公约数为 2 辗转相除法 求两个数的最大公约数 其基本步骤是带余除法m nq r 0 r n 反复执行 直到余数r 0为止 欧几里得算法 78 36 6 36 1步 288 123 42 123 42 39 3 39 3步 思考 你能把辗转相除法编成一个计算机程序吗 1 算法步骤 第一步 输入两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则转到第二步 第五步 输出最大公约数m 2 程序框图 3 程序 m input m n input n whilemodulo m n 0 r modulo m n m n n r endd r 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 小结 二 秦九韶算法 设计求多项式f x 5x5 3x4 2x3 3x2 x 1当x 2时的函数值 一般的解决方案 x 2 y 5 x 5 3 x 4 2 x 3 3 x 2 x 1 y 设计求多项式f x 5x5 3x4 2x3 3x2 x 1当x 2时的函数值 次加法 次乘法 秦九韶算法适用一般的多项式p x anxn an 1xn 1 a1x a0的求值问题 p x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 n次乘法 n次加法 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 2 n次乘法和n次加法 秦九韶算法的特点 得递推公式为 1 降幂 世界上多项式求值最先进算法 用秦九韶算法求函数 1 几次加