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

1 3算法案例 案例1辗转相除法与更相减损术 35 915 问题1 在小学 我们已经学过求最大公约数的知识 你能求出18与30的最大公约数吗 创设情景 揭示课题 1830 2 3 18和30的最大公约数是2 3 6 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 问题2 我们都是利用找公约数的方法来求最大公约数 如果公约数比较大而且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公约数 比如求8251与6105的最大公约数 研探新知 1 辗转相除法 例1求两个正数8251和6105的最大公约数 分析 8251与6105两数都比较大 而且没有明显的公约数 如能把它们都变小一点 根据已有的知识即可求出最大公约数 解 8251 6105 1 2146 显然8251与6105的最大公约数也必是2146的约数 同样6105与2146的公约数也必是8251的约数 所以8251与6105的最大公约数也是6105与2146的最大公约数 研探新知 1 辗转相除法 例1求两个正数8251和6105的最大公约数 解 8251 6105 1 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 m n q0 r0 第二步 若r0 0 则n为m n的最大公约数 若r0 0 则用除数n除以余数r0得到一个商q1和一个余数r1 n r0 q1 r1 第三步 若r1 0 则r0为m n的最大公约数 若r1 0 则用除数r0除以余数r1得到一个商q2和一个余数r2 r0 r1 q2 r2 依次计算直至rn 0 此时所得到的rn 1即为所求的最大公约数 第一步 给定两个正数m n第二步 计算m除以n所得到余数r第三步 m n n r第四步 若r 0 则m n的最大公约数等于m 否则返回第二步 辗转相除法求最大公约数算法 否 4 辗转相除法的程序框图及程序 开始 输入两个正数m n m n r mMODn r 0 输出n 结束 m x m n n r 否 是 是 x n n m 练习1 利用辗转相除法求两数4081与20723的最大公约数 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 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 练习2 用更相减损术求两个正数84与72的最大公约数 第一步 给定两个正整数 不妨设m n 第二步 若m n都是偶数 则不断用2约简 使他们不同时是偶数 约简后的两个数仍记为m n第三步 d m n第四步 判断 d0 是否成立 若是 则将n d中较大者记为m 较小的记为n 返回第三步 否则 2 k d k是约简整数的2的个数 为所求的最大公约数 更相减损术算法 是 否 N d 是 是 否 INPUT m n m nIFm nTHENa mm nn aENDIFK 0WHILEmMOD2 0ANDnMOD2 0m m 2n n 2k k 1WENDd m n WhilednIFd nthenm dELSEm nn dEndifd m nWendd 2 k dPRINTdEnd 3 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 作业 课本P45页练习T1 P48页A组T1 案例2秦九韶算法 教学设计 问题1 设计求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值的算法 并写出程序 点评 上述算法一共做了15次乘法运算 5次加法运算 优点是简单 易懂 缺点是不通用 不能解决任意多项多求值问题 而且计算效率不高 这析计算上述多项式的值 一共需要9次乘法运算 5次加法运算 问题2 有没有更高效的算法 分析 计算x的幂时 可以利用前面的计算结果 以减少计算量 即先计算x2 然后依次计算 的值 第二种做法与第一种做法相比 乘法的运算次数减少了 因而能提高运算效率 而且对于计算机来说 做一次乘法所需的运算时间比做一次加法要长得多 因此第二种做法能更快地得到结果 问题3 能否探索更好的算法 来解决任意多项式的求值问题 f x 2x5 5x4 4x3 3x2 6x 7 2x4 5x3 4x2 3x 6 x 7 2x3 5x2 4x 3 x 6 x 7 2x2 5x 4 x 3 x 6 x 7 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 所以 当x 5时 多项式的值是2677 这种求多项式值的方法就叫秦九韶算法 例1 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法一 首先将原多项式改写成如下形式 f x 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 所以 当x 5时 多项式的值是2677 然后由内向外逐层计算一次多项式的值 即 2 5 43 67 x 5 10 5 25 21 105 108 540 534 2670 2677 所以 当x 5时 多项式的值是2677 原多项式的系数 多项式的值 例1 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法二 列表 2 2 50 43 60 x 5 10 5 25 25 125 121 605 608 3040 3034 所以 当x 5时 多项式的值是15170 练一练 用秦九韶算法求多项式f x 2x6 5x5 4x3 3x2 6x当x 5时的值 解 原多项式先化为 f x 2x6 5x5 0 x4 4x3 3x2 6x 0列表 2 15170 15170 注意 n次多项式有n 1项 因此缺少哪一项应将其系数补0 f x anxn an 1xn 1 an 2xn 2 a1x a0 我们可以改写成如下形式 f x anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算最内层括号内一次多项式的值 即 v1 anx an 1 然后由内向外逐层计算一次多项式的值 即 一般地 对于一个n次多项式 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 这种算法称为秦九韶算法 点评 秦九韶算法是求一元多项式的值的一种方法 它的特点是 把求一个n次多项式的值转化为求n个一次多项式的值 通过这种转化 把运算的次数由至多n n 1 2次乘法运算和n次加法运算 减少为n次乘法运算和n次加法运算 大大提高了运算效率 v1 anx an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 观察上述秦九韶算法中的n个一次式 可见vk的计算要用到vk 1的值 若令v0 an 得 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 问题 画出程序框图 表示用秦九韶算法求5次多项式f x a5x5 a4x4 a3x3 a2x2 a1x a0当x x0 x0是任意实数 时的值的过程 然后写出程序 否 程序框图 开始 输入a0 a1 a2 a3 a4 a5 输入x0 n 5 n 1 v a5 v vx0 a5 n n n 1 输出v 结束 是 课本P45页练习T2 P48页A组T2 案例3进位制 一 三维目标 a 知识与技能了解各种进位制与十进制之间转换的规律 会利用各种进位制与十进制之间的联系进行各种进位制之间的转换 b 过程与方法学习各种进位制转换成十进制的计算方法 研究十进制转换为各种进位制的除k去余法 并理解其中的数学规律 c 情感态度与价值观领悟十进制 二进制的特点 了解计算机的电路与二进制的联系 进一步认识到计算机与数学的联系 二 教学重难点重点 各进位制表示数的方法及各进位制之间的转换难点 除k去余法的理解以及各进位制之间转换的程序框图的设计三 学法在学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系 熟悉各种进位制表示数的方法 从而理解十进制转换为各种进位制的除k去余法 问题1 我们常见的数字都是十进制的 但是并不是生活中的每一种数字都是十进制的 比如时间和角度的单位用六十进位制 电子计算机用的是二进制 那么什么是进位制 不同的进位制之间又有什么联系呢 进位制是人们为了计数和运算的方便而约定的一种记数系统 约定满二进一 就是二进制 满十进一 就是十进制 满十六进一 就是十六进制 等等 满几进一 就是几进制 几进制的基数就是几 可使用数字符号的个数称为基数 基数都是大于1的整数 如二进制可使用的数字有0和1 基数是2 十进制可使用的数字有0 1 2 8 9等十个数字 基数是10 十六进制可使用的数字或符号有0 9等10个数字以及A F等6个字母 规定字母A F对应10 15 十六进制的基数是16 注意 为了区分不同的进位制 常在数字的右下脚标明基数 如111001 2 表示二进制数 34 5 表示5进制数 十进制数一般不标注基数 问题2 十进制数3721中的3表示3个千 7表示7个百 2表示2个十 1表示1个一 从而它可以写成下面的形式 3721 3 103 7 102 2 101 1 100 想一想二进制数1011 2 可以类似的写成什么形式 1011 2 1 23 0 22 1 21 1 20 同理 3421 5 3 53 4 52 2 51 1 50 C7A16 16 12 164 7 163 10 162 1 161 6 160 一般地 若k是一个大于1的整数 那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 anan 1 a1a0 k 0 an k 0 an 1 a1 a0 k 意思是 1 第一个数字an不能等于0 2 每一个数字an an 1 a1 a0都须小于k k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 注意这是一个n 1位数 问题3 二进制只用0和1两个数字 这正好与电路的通和断两种状态相对应 因此计算机内部都使用二进制 计算机在进行数的运算时 先把接受到的数转化成二进制数进行运算 再把运算结果转化为十进制数输出 那么二进制数与十进制数之间是如何转化的呢 例1 把二进制数110011 2 化为十进制数 分析 先把二进制数写成不同位上数字与2的幂的乘积之和的形式 再按照十进制数的运算规则计算出结果 解 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 1 32 1 16 1 2 1 51 问题4 你会把三进制数10221 3 化为十进制数吗 解 10221 3 1 34 0 33 2 32 2 31 1 30 81 18 6 1 106 k进制数转化为十进制数的方法 先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 再按照十进制数的运算规则计算出结果 例2 把89化为二进制的数 分析 把89化为二进制的数 需想办法将89先写成如下形式 89 an 2n an 1 2n 1 a1 21 a0 20 89 64 16 8 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1011001 2 但如果数太大 我们是无法这样凑出来的 怎么办 89 44 2 1 44 22 2 0 22 11 2 0 11 5 2 1 5 2 2 1 2 1 2 0 1 0 2 1 89 44 2 1 44 22 2 0 22 11 2 0 11 5 2 1 5 2 2 1 89 44 2 1 22 2 0 2 1 11 2 0 2 0 2 1 5 2 1 2 0 2 0 2 1 2 2 1 2 1 2 0 2 0 2 1 1 2 0 2 1 2 1 2 0 2 0 2 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1011001 2 可以用2连续去除89或所得商 一直到商为0为止 然后取余数 除2取余法 2 1 2 0 1 0 2 1 441 例2 把89化为二进制的数 我们可以用下面的除法算式表示除2取余法 220 110 51 21 10 01 把算式中各步所得的余数从下到上排列 得到 89 1011001 2 这种方法也可以推广为把十进制数化为k进制数的算法 称为除k取余法 例3 把89化为五进制的数 解 以5作为除数 相应的除法算式为 174 32 03 89 324 5 问题5 你会把三进制数10221 3 化为二进制数吗 解 第一步 先把三进制数化为十进制数 10221 3 1 34 0 33 2 32 2 31 1 30 81 18 6 1 106 第二步 再把十进制数化为二进制数 106 1101010 2 小结 进位制的概念及表示方法 各种进位制之间的相互转化 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 作业 1 课本P45页A组T3