高中数学 专题1.5 算法案例课件 新人教A版必修3.ppt

算法案例 1 辗转相除法 所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时较小的数就是原来两个数的最大公约数 基础回顾 2 作用 辗转相除法是用于求两个正整数 的一种算法 这种算法是由欧几里得在公元前300年左右首先提出的 因此又叫 最大公约数 欧几里得算法 小结 辗转相除法的步骤 第一步 给定两个正整数m n 不妨令m n 第二步 计算m除以n所得的余数r 第三步 第四步 若r 0 则m n的最大公约数等于 否则 返回第二步 m n n r m 1 算理 所谓更相减损术 就是对于给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤 直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 类型二 更相减损术 2 作用 更相减损术是我国古代数学专著 中介绍的一种求两个正整数最大公约数的方法 九章算术 1 算法步骤第一步 输入两个正整数a b a b 第二步 若a不等于b 则执行第三步 否则转到第五步 第三步 把a b的差赋予r 第四步 如果b r 那么把b赋给a 把r赋给b 否则把r赋给a 执行第二步 第五步 输出最大公约数b 3 试根据更相减损术设计一个计算机程序 求两个正整数的最大公约数 类型三 秦九韶算法 1 秦九韶算法 秦九韶算法的是通过一次式的反复计算 逐步求出n次多项式的值 因此对于一个n次多项式 利用秦九韶算法求多项式的值 只要做n次乘法运算和n次加法运算即可 2 作用 用秦九韶算法求n次多项式f x anxn an 1xn 1 a1x a0 当x x0时的值 3 基本原理 首先将多项式改写成如下形式 f 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 求多项式的值时 首先计算最内层括号内的一次多项式的值 即v1 然后由内向外逐层计算一次多项式的值 即v2 v1x an 2 v3 v2x an 3 vn 这样 求n次多项式f x 的值就转化为求 anx an 1 vn 1x a0 n个一次多项式的值 小结 秦九韶算法的步骤 1 进位制的概念 进位制是人们为计数和运算方便而约定的计数系统 约定满二进一 就是 进制 满十进一 就是 进制 也就是说 满几进一 就是 进制 几进制的基数就是 二 十 几 几 类型四 二进制 2 表示 一般地 若k是一个大于1的整数 那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 anan 1 a1a0 k an an 1 a1 a0 n 0 an 0 an 1 a1 a0 k k 3 进位制之间的转化 1 k进制的数转化为十进制 若anan 1 a1a0 k 表示一个k进制的数 则转化为十进制数为 anan 1 a1a0 k 2 将十进制化为k进制 用除k取余法 用k连续去除 直到 为止 然后将所得的余数 即为相应的k进制数 an kn an 1 kn 1 a1 k1 a0 十进制数所得的商 商为零 倒序写出 类型一 求最大公约数 问题探讨与解题研究 例1 分别用辗转相除法和更相减损术求779与209的最大公约数 分析 1 辗转相除法的操作是较大的数除以较小的数 直到余数为零 2 更相减损术的操作是以大数减小数 直到减数和差相等 解析 方法一 辗转相除法779 209 3 152 209 152 1 57 152 57 2 38 57 38 1 19 38 19 2 所以 779与209的最大公约数为19 方法二 更相减损术779 209 570 570 209 361 361 209 152 209 152 57 152 57 95 95 57 38 57 38 19 38 19 19 所以779和209的最大公约数为19 练习 1 用更相减损术求78与36的最大公约数 2 用辗转相除法求78与36的最大公约数 解析 1 78 36 42 42 36 6 36 6 30 30 6 24 24 6 18 18 6 12 12 6 6 2 由辗转相除法得 78 36 2 6 36 6 6 故78与36的最大公约数是6 小结 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 例2 已知f x 5x4 10 x3 10 x2 5x 1 用秦九韶算法求x 2时f x 的值 类型二 利用秦九韶算法求多项式的值 分析 根据秦九韶算法的运算法则 将函数f x 化为下面的形式 f x 5x 10 x 10 x 5 x 1 然后从里向外逐步计算 共进行4次乘法 5次加法运算 就得到x 2时f x 的值 解析 因为f x 5x4 10 x3 10 x2 5x 1所以f x 5x 10 x 10 x 5 x 1 v0 5 v1 5 2 10 0 v2 0 2 10 10 v3 10 2 5 15 v4 15 2 1 29 所以 当x 2时 f x 29 练习 已知一个5次多项式为f x 4x5 2x4 3 5x3 2 6x2 1 7x 0 8 用秦九韶算法求这个多项式当x 5时的值 解析 将f x 改写为f x 4x 2 x 3 5 x 2 6 x 1 7 x 0 8 由内向外依次计算一次多项式 当x 5时的值 v0 4 v1 4 5 2 22 v2 22 5 3 5 113 5 v3 113 5 5 2 6 564 9 v4 564 9 5 1 7 2826 2 v5 2826 2 5 0 8 14130 2 所以当x 5时 多项式的值等于14130 2 小结 秦九韶算法是求一元多项式的值的一种方法 它的特点是 把求一个n次多项式的值转化为求n个一次多项式的值 通过这种转化 把运算的次数由至多n n 1 2次乘法运算和n次加法运算 减少为n次乘法运算和n次加法运算 大大提高了运算效率 例1 已知一个k进制数132与十进制数30相等 那么k等于 a 7或4 b 7 c 4 d 都不对 类型三 利用秦九韶算法求多项式的值 分析 1 根据k进制数化十进制数的规则列出k的方程即可 解析 选c 由1 k2 3 k1 2 k0 30 得k2 3k 28 0即k 4或k 7 舍 例2 把十进制数111化为五进制数是 a 421 5 b 521 5 c 423 5 d 332 5 分析 用5连续去除111 直到商为0为止 然后将各步所得的余数倒序写出 即为相应的五进制数 解析 选a 练习 210 6 化成十进制数为 85化成七进制数为 解析 210 6 2 62 1 6 78 所以85 151 7 答案 78151 7 b 课堂检测 2 490和910的最大公约数为 a 2b 10c 30d 70 解析 d 解析 b 3 利用秦九韶算法求当x 2时 的值时 下列说法正确的是 a 先求b 先求 第二步求c 直接运算求解d 以上皆错 课堂小结 1 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小