（新编资料）2013-2014学年高中数学 1.3《算法案例》导学案 新人教A版必修3

1 1 3 1 3 算法案例算法案例 学习目标学习目标 1 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进行算法分析 2 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序 重点难点重点难点 重点 理解辗转相除法与更相减损术求最大公约数的方法 难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 学习过程学习过程 情境导入 情境导入 1 教师首先提出问题 在初中 我们已经学过求最大公约数的知识 你能求出 18 与 30 的公约数吗 2 接着教师进一步提出问题 我们都是利用找公约数的方法来求最大公约数 如果公约数比较大而 且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公约数 比如求 8251 与 6105 的最大公约数 这就是我们这一堂课所要探讨的内容 新知探究 新知探究 1 辗转相除法 例 1 求两个正数 8251 和 6105 的最大公约数 分析 8251 与 6105 两数都比较大 而且没有明显的公约数 如能把它们都变小一点 根据已有 的知识即可求出最大公约数 解 8251 6105 1 2146 显然 8251 的最大公约数也必是 2146 的约数 同样 6105 与 2146 的公约数也必是 8251 的约数 所 以 8251 与 6105 的最大公约数也是 6105 与 2146 的最大公约数 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 则 37 为 8251 与 6105 的最大公约数 以上我们求最大公约数的方法就是辗转相除法 也叫欧几里德算法 它是由欧几里德在公元前 300 年左右首先提出的 利用辗转相除法求最大公约数的步骤如下 第一步 用较大的数 m 除以较小的数 n 得到一个商 q0和一个余数 r0 第二步 若 r0 0 则 n 为 m n 的最大公约数 若 r0 0 则用除数 n 除以余数 r0得到一个商 q1和 一个余数 r1 第三步 若 r1 0 则 r1为 m n 的最大公约数 若 r1 0 则用除数 r0除以余数 r1得到一个商 q2 和一个余数 r2 依次计算直至 rn 0 此时所得到的 rn 1即为所求的最大公约数 练习 利用辗转相除法求两数 4081 与 20723 的最大公约数 答案 53 2 更相减损术 我国早期也有解决求最大公约数问题的算法 就是更相减损术 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母 子之数 以少减多 更 相减损 求其等也 以等数约之 翻译出来为 第一步 任意给出两个正数 判断它们是否都是偶数 若是 用 2 约简 若不是 执行第二步 2 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小数 继续这个 操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 例 2 用更相减损术求 98 与 63 的最大公约数 解 由于 63 不是偶数 把 98 和 63 以大数减小数 并辗转相减 即 98 63 35 63 35 28 35 28 7 28 7 21 21 7 14 14 7 7 所以 98 与 63 的最大公约数是 7 练习 用更相减损术求两个正数 84 与 72 的最大公约数 答案 12 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次 数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为 0 则得到 而更相减损术则以减 数与差相等而得到 3 秦九韶算法 秦九韶计算多项式的方法 令 则有 其中 这样 我们便可由依次求出 显然 用秦九韶算法求 n 次多项式的值时只需要做 n 次乘法和 n 次加法运算 4 进位制 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 可使用数字符号的个数 称为基数 基数为 n 即可称 n 进位制 简称 n 进制 现在最常用的是十进制 通常使用 10 个阿拉 伯数字 0 9 进行记数 对于任何一个数 我们可以用不同的进位制来表示 比如 十进数 57 可以用二进制表示为 111001 也可以用八进制表示为 71 用十六进制表示为 39 它们所代表的数值都是一样的 表示各种进位制数一般在数字右下脚加注来表示 如 111001 2 表示二进制数 34 5 表示 5 进制 数 1 k 进制转换为十进制的方法 3 2 十进制转化为 k 进制数 b 的步骤为 第一步 将给定的十进制整数除以基数 k 余数便是等值的 k 进制的最低位 第二 步 将上一步的商再除以基数 k 余数便是等值的 k 进制数的次低位 第三步 重复第二步 直到最后所得的商等于 0 为止 各次所得的余数 便是 k 进制各位的数 最后一次余数是最高位 即除 k 取余法 要点诠释 1 在 k 进制中 具有 k 个数字符号 如二进制有 0 1 两个数字 2 在 k 进制中 由低位向高位是按 逢 k 进一 的规则进行计数 3 非 k 进制数之间的转化一般应先转化成十进制 再将这个十进制数转化为另一种进制的数 有的也可以相互转化 基础达标基础达标 1 求 324 243 135 这三个数的最大公约数 求三个数的最大公约数可以先求出两个数的最大公约数 第三个数与前两个数的最大公约数的最大 公约数即为所求 2 用更相减损术求 98 与 63 的最大公约数 解 由于 63 不是偶数 把 98 和 63 以大数减小数 并辗转相减 98 63 35 63 35 28 35 28 7 28 7 21 21 7 21 14 7 7 所以 98 和 63 的最大公约数等于 7 3 已知一个五次多项式为用秦九韶算法求这个多项8 07 16 25 325 2345 xxxxxxf 式当 x 5的值 解 将多项式变形 按由里到外的顺序 依此计8 0 7 1 6 2 5 3 25 xxxxxxf 算一次多项式当 x 5 时的值 5 0 v27255 1 v 5 1385 3527 2 v 9 6896 25 5 138 3 v 所以 当 x 5 时 多项式的值等 2 34517 15 9 689 4 v 2 172558 05 2 3451 5 v 于 17255 2 4 将二进制数 110011 2 化成十进制数 解 根据进位制的定义可知 012345 2 212120202121110011 121161321 51 所以 110011 2 51 4 5 1 3 1 3 算法案例算法案例 导学案导学案 一 预习目标 学习目标学习目标 1 会用辗转相除法与更相减损术求最大公约数的方法 2 会利用秦九韶算法求多项式的值 3 各进位制之间能灵活转化 重点难点重点难点 重点 辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值 难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 知识链接知识链接 1 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进行算法分析 2 理解秦九韶算法的思想 二 预习内容 什么是进位制 最常见的进位制是什么 除此之外还有哪些常见的进位制 请举例说明 三 提出疑惑 思考 辗转相除法中的关键步骤是哪种逻辑结构 学习过程学习过程 辗转相除法思路 可以利用除法将大数化小 找两数的最大公约数 适于两数较大时 1 用较大的数 m 除以较小的数 n 得到一个商和一个余数 0 S 0 R 2 若 0 则 n 为 m n 的最大公约数 若 0 则用除数 n 除以余数得到一个 0 R 0 R 0 R 1 S 和一个余数 3 若 0 则为 m n 的最大公约数 若 0 则用除数除以余数得到 1 R 1 R 1 R 1 R 0 R 1 R 一个商和一个余数 依次计算直至 0 此时所得到的即为所求的最大公约数 2 S 2 R n R 1n R 例题 1 求两个正数 1424 和 801 的最大公约数 以上我们求最大公约数的方法就是辗转相除法 也叫欧几里德算法 由上述步骤可以看出 辗转相除法中的除法是一个反复执行的步骤 且执行次数由余数 是否等 于 0 来决定 所以可把它看成一循环体 写出辗转相除法完整的程序框图和程序语言 教学更相减损术 我国早期也有求最大公约数问题的算法 就是更相减损术 在 九章算 术 中 有更相减损术求最大公约数的步骤 可半者半之 不可半者 副置 分母 子之数 以少减多 更相 减损 求其等也 以等数约之 6 翻译为 1 任意给出两个正数 判断它们是否都是偶数 若是 用 2 约简 若不是 执 行第二 步 2 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小 数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最 大公约数 例题 2 用更相减损术求 91 和 49 的最大公约数 秦九韶算法 1 设计求多项式当 x 5时的值的算法 并写出程序 763452 2345 xxxxxxf 2 有没有更高效的算法 能否探求更好的算法 来解决任意多项式的求解问题 引导学生把多项式变形为 7 6 3 4 52 763452 2345 xxxxx xxxxxxf 并提问 从内到外 如果把每一个括号都看成一个常数 那么变形后的式子中有哪些 一次式 x 的系数依次是什么 用秦九韶算法求多项式的值 与多项式组成有直接关系吗 用秦九韶算法计算上述多项式的值 需 要多少次乘法运算和多少次加法运算 秦九韶算法适用于一般的多项式 的求值问题吗 01 1 1 axaxaxaxf n n n n 怎样用程序框图表示秦九韶算法 观察秦九韶算法的数学模型 计算时要用到的值 若令 k v 1 k v 我们可以得到下面的递推公式 n av 0 这是一个在秦九韶算法中反复执行的步骤 可以用循环结构来实 2 1 1 0 nk axvv av knkk n 现 请画出程序框图 例题 3 已知一个五次多项式为用秦九韶算法求这8 07 16 25 325 2345 xxxxxxf 个多项式当 x 5 的值 7 进位制 我们了解十进制吗 所谓的十进制 它是如何构成的 其它进位制的数又是如何的呢 进位制是人们为了计数和运算方便而约定的记数系统 进位制是一种记数方式 用有限的数字在不 同的位置表示不同的数值 可使用数字符号的个数称为基数 基数为 n 即可称 n 进位制 简称 n 进制 例题 4 将二进制数 110011 2 化成十进制数 精讲点拨 1 求两个正数 8251 和 2146 228 和 1995 5280 和 12155 的最大公约数 2 求两个正数 8251 和 2146 的最大公约数 3 用秦九韶算法计算多项式 在 x 4 时的值时 V3的值为 学习反思学习反思 比较辗转相除法与更相减损术的区别 1 都是求 的方法 计算上辗转相除法以 法为主 更相减损术以 法为主 计算 次数上 法计算次数相对较少 特别当两个数字 时计算次数的区别较明 显 2 从结果体现形式来看 辗转相除法体现结果是