高考数学总复习 第1章1.4 算法案例课件 苏教版必修3.ppt

1 4算法案例 学习目标 1 体会三个案例的算法思想 2 会用辗转相除法求两个正数的最大公约数 课堂互动讲练 知能优化训练 1 4算法案例 课前自主学案 课前自主学案 1 三种循环语句的一般形式分别是什么 当型语句whilep循环体endwhile直到型语句do循环体untilpenddofor语句forifrom 初值 to 终值 step 步长 循环体endfor 2 当型循环与直到型循环语句的区别 1 当型循环是先判断 条件 后执行 循环体 而直到型循环则是先执行 循环体 后判断 条件 2 当型循环是当条件满足时执行循环体 不满足时结束循环 而直到型循环则是条件不满足时执行循环体 条件满足时结束循环 3 直到型循环至少执行一次循环体 而当型循环可能一次也不执行循环体 1 辗转相除法所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时的较小的数就是原来两个数的 最大公约数 2 更相减损术所谓更相减损术就是对于给定的两个数 以两数中较大的数减去较小的数 然后将差和较小的数构成一对新数 再用较大的数减去较小的数 反复执行此步骤直到差和较小的数相等 此时相等的两数便为原来两数的 最大公约数 3 中国剩余定理 或孙子剩余定理 其最早出现在我国 算经十书 之一的 孙子算经 中 原文是 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 答曰 二十三 自从 孙子算经 中提出这个 物不知数 问题之后 它便引起了人们很大的兴趣 孙子算经 中给出了求解的关键步骤 南宋数学家秦九韶对该问题加以推广 又发现了一种新的算法 叫 大衍求一术 人们将这种问题的通用解法称为 或 中国剩余定理 孙子剩余定理 4 秦九韶算法 课堂互动讲练 求两个正整数的最大公约数可用辗转相除法或更相减损术 二者的主要区别在于辗转相除法进行的是除法运算 即辗转相除 而更相减损术进行的是减法运算 即辗转相减 它们在步骤上虽然略有不同 但在理论上是一致的 都是一个不断的递归过程 用辗转相除法求612与468的最大公约数 并用更相减损术检验所得结果 思路点拨 将612作大数 468作小数 执行辗转相除法和更相减损术即可 解 用辗转相除法 612 468 1 144 468 144 3 36 144 36 4 即612和468的最大公约数是36 用更相减损术 612和468为偶数 两次用2约简得153和117 153 117 36 117 36 81 81 36 45 45 36 9 36 9 27 27 9 18 18 9 9 所以612和468的最大公约数为9 2 2 36 思维总结 辗转相除法是当大数被小数除尽时 结束除法运算 较小的数就是最大公约数 更相减损术是先判断两个数是否均为偶数 若是 用2约简 否则用大数减小数 当大数减小数的差等于小数时减法停止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 自我挑战1用辗转相除法 更相减损术求228 1995的最大公约数 解 用辗转相除法 1995 8 228 171228 1 171 57171 3 57 0所以 57就是228和1995的最大公约数 用更相减损术 1995 228 17671767 228 1539 1539 228 13111311 228 10831083 228 855855 228 627627 228 399399 228 171228 171 57171 57 114114 57 5757 57 0则57就是228 1995的最大公约数 秦九韶算法适用于一般的多项式f x anxn an 1xn 1 a1x a0的求值问题 秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值 即把求f x anxn an 1xn 1 a1x a0的值转为求递推公式 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做到n次乘法和n次加法运算即可 从而提高了运算效率 用秦九韶算法求多项式f x 3x5 8x4 3x3 5x2 12x 6 当x 2时的值 思路点拨 秦九韶算法的关键在于把n次多项式转化为求一次多项式的值 注意体会递推的实现过程 解 根据秦九韶算法 把多项式改写成如下形式 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 思维总结 利用秦九韶算法计算多项式的值 关键是正确地将所给多项式改写 然后由内向外逐次计算 由于后项计算需要用到前项的结果 故应认真 细心 确保中间结果的准确性 利用秦九韶算法计算多项式的值 通过列表则能简化书写 自我挑战2用秦九韶算法求多项式f x 8x7 5x6 3x4 2x 1当x 2时的值 解 根据秦九韶算法 把多项式改写成如下形式 f x 8x7 5x6 0 x5 3 x4 0 x3 0 x2 2x 1 8x 5 x 0 x 3 x 0 x 0 x 2 x 1 按照从内到外的顺序 依次计算一次多项式当x 2时的值 v0 8 v1 8 2 5 21 v2 21 2 0 42 v3 42 2 3 87 v4 87 2 0 174 v5 174 2 0 348 v6 348 2 2 698 v7 698 2 1 1397 当x 2时 多项式的值为1397 进位制是人们为了计数和运算方便而约定的记数系统 约定满二进一 就是二进制 满十进一 就是十进制 满十二进一 就是十二进制 满六十进一 就是六十进制 等等 也就是说 满几进一 就是几进制 几进制的基数就是几 把十进制数化为k进制数用 除k取余法 即把所给十进制数除以k 得到商和余数 再对商除以k 得到商数和余数 直到商数为0 把上面各步所得的余数从下到上排列 即得到k进制数 本题满分14分 1 把二进制数11011 2 化为十进制数 2 把十进制数281化为二进制数 思路点拨 按公式或步骤进行 规范解答 1 11011 2 1 24 1 23 0 22 1 2 1 16 8 2 1 27 6分 2 281化为二进制数为100011001 2 14分 名师点评 1 把二进制数化为十进制数的方法 anan 1 a1a0 2 an 2n an 1 2n 1 a1 2 a0 2 把十进制数化为二进制数的方法 把十进制数连续除以2 直到商为0为止 同时将各步的余数写出 将各步所得的余数倒序写出 即为所求的二进制数 称为除2取余法 自我挑战3 1 110010 2 化为十进制数为 2 93化为二进制数为 解析 1 110010 2 化为十进制数为1 25 1 24 0 23 0 22 1 2 0 32 16 2 50 2 93化为二进制数是1011101 2 答案 1 50 2 1011101 2 1 用辗转相除法求两数最大公约数时 是当大数恰好被小数整除时停止除法 这时的小数就是两数的最大公约数 用更相减损术求两数最大公约数时 是当大数减小数恰好等于小数时停止减法 这时的小数就是两数的最大公约数 求三个以上 含三个数 的数的最大公约数时 可依次通过求两个数的最大公约数与第