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

1 3算法案例 列为选学 学习目标1 通过案例体会算法思想 2 了解案例中的算法用途 课堂互动讲练 知能优化训练 1 3算法案例 列为选学 课前自主学案 课前自主学案 1 在两个正数的所有公约数中最大的一个公约数为它们的 如12和18的最大公约数为 4和20的最大公约数为 最大公约数 6 4 2 当x 2时 多项式f x x x x 1 1 1的值为 加法与乘法共有 次运算 3 在度 分 秒的互化中 其进制单位为 在 分米 与 米 的互化中 其进制单位为 15 5 60 10 1 辗转相除法是用于求两个正整数的 的一种方法 这种算法由欧几里得在公元前300年左右首先提出 因而又叫欧几里得算法 2 所谓辗转相除法 就是对于给定的两个正整数 用 除以 若余数不为零 则将 构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时 就是原来两个数的最大公约数 较大数 较小数 较小数 余数和较小数 3 更相减损术是我国古代数学专著 九章算术 中介绍的一种求两个正整数最大公约数的方法 其基本过程是 对于给定的两个正整数 判断它们是否都是偶数 若是 用2约简 若不是 则用 接着把所得的 与 比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 较大数减去较小数 差 较小数 相等 4 秦九韶算法是我国南宋数学家秦九韶在他的代表作 数学九章 中提出的一种用于计算一元n次多项式的值的方法 5 进位制是人们为了计数和运算方便而约定的记数系统 满k k是一个大于1的整数 进一 就是 k进制的基数是 k进制 k 6 将k进制的数化为十进制数的方法是 先把k进制数写成用各位上的数字与k的幂的乘积之和的形式 再按照十进制数的运算规则计算出结果 7 将十进制数化为k进制数的方法是 即用k连续去除十进制数或所得的商直到商为零为止 然后把各步得到的余数倒着写出就是相应的k进制数 1 实际应用更相减损术时要做的第一步工作是什么 提示 先判断a b是否全为偶数 若是 则先都除以2再进行 2 用秦九韶算法求x 2时f x x3 3x2 x 1的值 第一个一次多项式的值为多少 提示 由秦九韶算法知f x x 3 x 1 x 1 由内到外第一个一次多项式的值为2 3 5 课堂互动讲练 用辗转相除法求最大公约数时 相除余数为零时得结果 用更相减损术求最大公约数时 当被减数与差相等时一般它就是最大公约数 用辗转相除法求80和36的最大公约数 并用更相减损术检验所得结果 思路点拨 按定义一步步递推 解 辗转相除法 80 36 2 8 36 8 4 4 8 4 2 0 故80和36的最大公约数是4 用更相减损术检验 80 36 44 44 36 8 36 8 28 28 8 20 20 8 12 12 8 4 8 4 4 80和36的最大公约数是4 思维总结 辗转相除法的理论依据是 由m nq r可以看出m n和n r有相同的公约数 更相减损术的理论依据为 由m n r 得m n r 可以看出 m n与n r有相同的公约数 即二者的 算理 相似 设pn x anxn an 1xn 1 a1x a0 将其改写为pn x 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 然后由内向外依次计算 当多项式函数中出现空项时 要以系数为零的齐次项补充 用秦九韶算法求多项式f x 3x5 8x4 3x3 5x2 12x 6当x 2时的值 解 根据秦九韶算法 把多项式改写成如下形式 f x 3x 8 x 3 x 5 x 12 x 6 按照从内到外的顺序 依次计算当x 2时一次多项式的值 v0 3 v1 v0 2 8 3 2 8 14 v2 v1 2 3 14 2 3 25 v3 v2 2 5 25 2 5 55 v4 v3 2 12 55 2 12 122 v5 v4 2 6 122 2 6 238 所以当x 2时 多项式的值为238 思维总结 利用秦九韶算法计算多项式值的关键是能准确地将多项式改写 然后由内向外逐次计算 由于后项计算用到前项的结果 故应认真 细心 确保每项计算结果的准确性 变式训练1已知f x x5 x3 x2 x 1 求f 3 的值 解 原多项式可化为f x x 0 x 1 x 1 x 1 x 1 按照从内到外的顺序 依次计算一次多项式当x 3时的值 v0 1 v1 1 3 0 3 v2 3 3 1 10 v3 10 3 1 31 v4 31 3 1 94 v5 94 3 1 283 所以 当x 3时 f 3 283 十进制数与非十进制数之间可相互转化 完成下列进位制之间的转化 1 将本例 1 中的十进制数30转化为二进制数 2 将二进制数101111011 2 转化为十进制数 思路点拨 1 把一个十进制数转化为相应的二进制数 用2反复去除欲被转化的十进制数30 直到商为0为止 将各步所得余数倒着写出就是该十进制数30的二进制表示 2 这类问题是从这个数的左边数字写起 写为1 2m或0 2m的形式之和 解 1 30 10 11110 2 2 101111011 2 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379 思维总结 1 将k进制转化为十进制的方法是 先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式 再按照十进制的运算规则计算出结果 2 十进制转化为k进制 采用除k取余法 也就是除基数 倒取余 互动探究2将本例 1 中的十进制数30转化为八进制数 解 30 10 36 8 方法技巧1 求两个正数的公约数 当两数差别较大时 用辗转相除法 当两数差别不大时 用更相减损术较快