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

第一章算法初步 1 3算法案例 学习目标 1 理解辗转相除法与更相减损术的含义 了解其执行过程 2 理解秦九韶算法的计算过程 并了解它提高计算效率的实质 3 理解进位制的概念 能进行不同进位制间的转化 4 了解进位制的程序框图和程序 知识梳理自主学习 题型探究重点突破 当堂检测自查自纠 栏目索引 知识梳理自主学习 知识点一辗转相除法与更相减损术 1 辗转相除法 1 辗转相除法 又叫欧几里得算法 是一种求两个正整数的的古老而有效的算法 2 辗转相除法的算法步骤第一步 给定 第二步 计算 第三步 第四步 若r 0 则m n的最大公约数等于 否则 返回 最大公约数 两个正整数m n m除以n所得的余数r m n n r m 第二步 答案 2 更相减损术第一步 任意给定两个正整数 判断它们是否都是 若是 用约简 若不是 执行 第二步 以的数减去的数 接着把所得的差与的数比较 并以大数减小数 继续这个操作 直到所得的数为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 偶数 2 第二步 较大 较小 较小 相等 答案 3 辗转相除法和更相减损术的区别与联系 思考实际应用更相减损术时要做的第一步工作是什么 答先判断a b是否为偶数 若是 都除以2再进行 答案 知识点二秦九韶算法 1 秦九韶算法简介 1 秦九韶算法要解决的问题是求多项式的值 2 秦九韶算法的特点 通过一次式的反复计算 逐步得到高次多项式的值 即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题 3 秦九韶算法的原理 将f x anxn an 1xn 1 a1x a0改写为 f x anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 先计算最内层括号内一次多项式的值 即v1 anx an 1 再由内向外逐层计算一次多项式vk的值 2 秦九韶算法的操作方法 1 算法步骤如下 第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 2 程序框图如图所示 3 程序如下 知识点三进位制 1 进位制的概念进位制是为了计数和运算方便而约定的记数系统 约定 满几进一 就是几进制 几进制的基数 大于1的整数 就是几 2 常见的进位制 1 二进制 只使用0和1两个数学 满二进一 即1 1 10 2 2 八进制 使用0 1 2 3 4 5 6 7这八个不同数学 满八进一 即7 1 10 8 3 十六进制 使用0 9十个数字和a f表示10 15 f 1 10 16 思考任何进位制中都要用到的数字是什么 答0和1 返回 答案 题型探究重点突破 题型一求两个正整数的最大公约数 例1分别用辗转相除法和更相减损术求261和319的最大公约数 解方法一 辗转相除法 319 261 1 余58 261 58 4 余29 58 29 2 余0 所以319与261的最大公约数为29 方法二 更相减损术 319 261 58 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 29 29 0 所以319与261的最大公约数是29 解析答案 反思与感悟 反思与感悟 1 利用辗转相除法求给定的两个数的最大公约数 即利用带余除法 用数对中较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的数对 再利用带余除法 直到大数被小数除尽 则这时的较小数就是原来两个数的最大公约数 2 利用更相减损术求两个正整数的最大公约数的一般步骤是 首先判断两个正整数是否都是偶数 若是 用2约简 也可以不除以2 直接求最大公约数 这样不影响最后结果 跟踪训练1用辗转相除法求80与36的最大公约数 并用更相减损术检验你的结果 解80 36 2 8 36 8 4 4 8 4 2 0 即80与36的最大公约数是4 验证 80 2 40 36 2 18 40 2 20 18 2 9 20 9 11 11 9 2 9 2 7 7 2 5 5 2 3 3 2 1 2 1 1 1 2 2 4 所以80与36的最大公约数为4 解析答案 题型二秦九韶算法的应用 例2用秦九韶算法求多项式f x x5 5x4 10 x3 10 x2 5x 1当x 2时的值 解f x x5 5x4 10 x3 10 x2 5x 1 x 5 x 10 x 10 x 5 x 1 当x 2时 有v0 1 v1 v0 x a4 1 2 5 3 v2 v1x a3 3 2 10 4 v3 v2x a2 4 2 10 2 v4 v3x a1 2 2 5 1 v5 v4x a0 1 2 1 1 故f 2 1 解析答案 反思与感悟 反思与感悟 1 先将多项式写成一次多项式的形式 然后运算时从里到外 一步一步地做乘法和加法即可 这样比直接将x 2代入原式大大减少了计算量 若用计算机计算 则可提高运算效率 2 注意 当多项式中n次项不存在时 可将第n次项看作0 xn 跟踪训练2用秦九韶算法计算多项式f x x6 12x5 60 x4 160 x3 240 x2 192x 64当x 2时的值 解根据秦九韶算法 把多项式改写成如下形式 f x x 12 x 60 x 160 x 240 x 192 x 64 由内向外依次计算一次多项式当x 2时的值 v0 1 v1 1 2 12 10 v2 10 2 60 40 v3 40 2 160 80 v4 80 2 240 80 v5 80 2 192 32 v6 32 2 64 0 所以当x 2时 多项式的值为0 解析答案 题型三进位制之间的互化 例3 1 把二进制数1110011 2 化为十进制数 解1110011 2 1 26 1 25 1 24 0 23 0 22 1 21 1 115 2 将8进制数314706 8 化为十进制数 解314706 8 3 85 1 84 4 83 7 82 0 81 6 80 104902 所以 化为十进制数是104902 解析答案 反思与感悟 反思与感悟 1 将k进制转化为十进制的方法是 先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式 再按照十进制的运算规则计算出结果 2 十进制转化为k进制 采用除k取余法 也就是除基数 倒取余 跟踪训练3将53 8 转化为二进制数 解先将八进制数53 8 转化为十进制数 53 8 5 81 3 80 43 再将十进制数43转化为二进制数 所以53 8 101011 2 解析答案 转化与化归思想 思想方法 例4下列各数中 最小的数是 a 85 9 b 210 6 c 1000 4 d 111111 2 分析先将它们转化为十进制数 再进行比较 解析85 9 8 9 5 77 210 6 2 62 1 6 0 78 1000 4 1 43 64 111111 2 1 25 1 24 1 23 1 22 1 2 1 63 故最小的是63 d 解析答案 解后反思 分析 解后反思合理的转化是解题的关键 对于进位制之间的转化问题 一般要先把k进制数转化为十进制数 再转化为其他进制数 数制转化方法掌握不牢致错 易错点 例5把十字进制数49化为二进制数 分析对进位制间的换算 要弄清解题的办法 将十进制数转化为k进制数用 除k取余法 解 所以49 110001 2 解后反思本例常出现的错误是把上式中各步所得的余数从上到下排列 这是基本方法掌握不牢造成的 应加以注意 分析 解析答案 解后反思 返回 当堂检测 1 2 3 4 5 1 1337与382的最大公约数是 a 3b 382c 191d 201 解析利用辗转相除法 1337 382 3 191 382 191 2 故两数的最大公约数为191 c 解析答案 1 2 3 4 5 2 把189化为三进制数 则末位数字是 a 0b 1c 2d 3 解析采用 除k取余法 得 即189 21000 3 a 解析答案 1 2 3 4 5 3 用秦九韶算法求n次多项式f x anxn an 1xn 1 a1x a0当x x0时的值 求f x0 需要乘方 乘法 加法的次数分别为 a n nb n 2n nc 0 2n nd 0 n n 解析因为f x anx an 1 x an 2 x a1 x a0 所以乘方 乘法 加法的次数分别为0 n n d 解析答案 1 2 3 4 5 解析答案 4 秦九韶是我国南宋时期的数学家 普州 现四川省安岳县 人 他在所著的 数书九章 中提出的多项式求值的秦九韶算法 至今仍是比较先进的算法 如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例 若输入n x的值分别为3 2 则输出v的值为 a 9b 18c 20d 35 1 2 3 4 5 解析初始值n 3 x 2 程序运行过程如下v 1i 2v 1 2 2 4i 1v 4 2 1 9i 0v 9 2 0 18i 1跳出循环 输出v 18 选b 答案b 解析答案 1 2 3 4 5 5 用更相减损术求36与134的最大公约数 第一步应为 解析 36与134都是偶数 第一步应为 先除以2 得到18与67 先除以2 得到 18与67 解析答案 课堂小结 返回 1 求两个正整数的最大公约数的问题 可以用辗转相除法 也可以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b