《学案导学设计高中数学 1.3 算法案例课堂教学课件1 新人教A必修.ppt》由会员分享，可在线阅读，更多相关《学案导学设计高中数学 1.3 算法案例课堂教学课件1 新人教A必修.ppt（33页珍藏版）》请在金锄头文库上搜索。
1、第一章算法初步1 3算法案例 35 915 问题1 在小学 我们已经学过求最大公约数的知识 你能求出18与30的最大公约数吗 创设情景 揭示课题 1830 2 3 18和30的最大公约数是2 3 6 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 案例1辗转相除法与更相减损术 创设情景 揭示课题 问题2 我们都是利用找公约数的方法来求最大公约数 如果两个数比较大而且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公约数 比如求8251与6105的最大公约数 研探新知 1 辗转相除法 例1求两个正数8251和6105的最大公约数 分析 825
2、1与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的最大公约
3、数 以上我们求最大公约数的方法就是辗转相除法 也叫欧几里德算法 它是由欧几里德在公元前300年左右首先提出的 第一步 给定两个正数m n第二步 计算m除以n所得到余数r第三步 m n n r第四步 若r 0 则m n的最大公约数等于m 否则返回第二步 辗转相除法求最大公约数算法 思考 需不需要比较m n的大小 不需要 否 开始 输入两个正数m n r mMODn r 0 输出m 结束 m n n r 是 程序框图 练习1 利用辗转相除法求两数4081与20723的最大公约数 53 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0
4、2 更相减损术 我国早期也有解决求最大公约数问题的算法 就是更相减损术 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 翻译出来为 第一步 任意给出两个正数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 例2用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 即 98 63 35 63 35 28 35 28 7 28
5、7 21 21 7 14 14 7 7 所以 98与63的最大公约数是7 练习2 用更相减损术求两个正数84与72的最大公约数 12 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 教学设计 问题1 设计求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值的算法 并写出程序 点评 上述算法一共做了15次乘法运算 5次加法运算 优点
6、是简单 易懂 缺点是不通用 不能解决任意多项式求值问题 而且计算效率不高 n次多项式至多n n 1 2次乘法运算和n次加法运算 案例2秦九韶算法 这析计算上述多项式的值 一共需要9次乘法运算 5次加法运算 问题2 有没有更高效的算法 分析 计算x的幂时 可以利用前面的计算结果 以减少计算量 即先计算x2 然后依次计算 的值 第二种做法与第一种做法相比 乘法的运算次数减少了 因而能提高运算效率 而且对于计算机来说 做一次乘法所需的运算时间比做一次加法要长得多 因此第二种做法能更快地得到结果 问题3 能否探索更好的算法 来解决任意多项式的求值问题 f x 2x5 5x4 4x3 3x2 6x 7
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 这种求多项式值的方法就叫秦九韶算法 变为求几个一次式的值 几个乘法几个加法 秦九韶 数书九章 2 50 43 60 x 5 10 5 25 25 125 121 605 608 3040 303
8、4 所以 当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次多项式
9、 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 得 这是一个在秦九韶算法中反
10、复执行的步骤 因此可用循环结构来实现 第一步 输入多项式次数n 最高次项的系数an和x的值第二步 将v的值初始化为an 将i的值初始化为n 1第三步 输入i次项的系数ai第四步 v vx ai i i 1第五步 若i 0 则返回第三步 否则输出v 算法分析 否 程序框图 开始 输入n an x的值 输入ai i 0 i n 1 v an v vx ai i i 1 输出v 结束 是 问题1 我们常见的数字都是十进制的 但是并不是生活中的每一种数字都是十进制的 比如时间和角度的单位用六十进位制 电子计算机用的是二进制 那么什么是进位制 不同的进位制之间又有什么联系呢 进位制是人们为了计数和运算的
11、方便而约定的一种记数系统 约定满二进一 就是二进制 满十进一 就是十进制 满十六进一 就是十六进制 等等 满几进一 就是几进制 几进制的基数就是几 可使用数字符号的个数称为基数 基数都是大于1的整数 案例3进位制 如二进制可使用的数字有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中的
12、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 每一个
13、数字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两个数字 这正好与电路的通和断两种状态相对应 因此计算机内部都使用二进制 计算机在进行数的运算时 先把接受到的数转化成二进制数进行运算 再把运算结果转化为十进制数输出 那么二进制数与十进制数之间是如何转化的呢 例3 把二进制数110011 2 化为十进制数 分析 先把二进制数写成不同位上数字与2的幂的乘积之和的形式 再按照十进制数的运算规则计算出结果 解
14、110011 2 1 25 1 24 0 23 0 22 1 21 1 20 1 32 1 16 1 2 1 51 k进制数转化为十进制数的方法 先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 再按照十进制数的运算规则计算出结果 例4 把89化为二进制的数 分析 把89化为二进制的数 需想办法将89先写成如下形式 89 an 2n an 1 2n 1 a1 21 a0 20 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
15、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 例4 把89化为二进制的数 我们可以用下面的除法算式表示除2取余法 220 110 51 21 10 01 把算式中各步所得的余数从下到上排列 得到 89 1011001 2 这种方法也可以推广为把十进制数化为k进制数的算法 称为除k取余法 例5 把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
