《fu算法案例》PPT课件.ppt

1 3算法案例 第二课时 2 求三个数324 243 135的最大公约数 解 324 243 1 81243 81 3 0则324与243的最大公约数为81又135 81 1 5481 54 1 2754 27 2 0则81与135的最大公约数为27所以 三个数324 243 135的最大公约数为27 1 用辗转相除法与更相减损术求72 168的最大公约数 复习回顾 24 从内向外计算 秦九韶算法 从内向外计算 问题 用秦九韶算法计算上面n次多项式的值 需要多少次乘法 多少次加法 每运算一个一次式都进行了一次乘法运算和一次加法运算 所以共做了n次乘法 n次加法 秦九韶算法 例3 已知一个5次的多项式为用秦九韶算法求这个多项式当x 5时的值 解 根据秦九韶算法 把多项式改写成如下形式 按照从内到外的顺序 依次计算一次多项式当x 5时的值 所以当x 5时 多项式的值等于17225 5 秦九韶算法 用秦九韶算法求多项式 当x 3时的值 练习 f 3 21324 进 位 1101 2 制 7426 8 进位制 人们为了计数和运算方便而约定的记数系统例如 满二进一 就是二进制 计算机 满十进一 就是十进制 手指头 满十二进一 就是十二进制 月份 满六十进一 就是六十进制 分钟 满几进一 就是几进制 一 引入 二 表示 十进制 87935 10 8 104 7 103 9 102 3 101 5 100同理二进制 110011 2 1 25 1 24 0 23 0 22 1 21 1 20八进制 7342 8 7 83 3 82 4 81 2 80十六进制 45972 16 4 164 5 163 9 162 7 161 2 160 三 探究 若anan 1 a1a0 k 0 an k o an 1 a1 a0 k 表示一个k进制的数 请你把它写成各位上数字与k的幂的乘积之和的形式 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 四 转化 例3 把二进制数110011 2 化为十进制数 解 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 1 32 1 16 0 8 0 4 1 2 1 1 51所以 110011 2 51 练习 把下列进位制数化为十进制数 1 20121 3 2 20121 4 答案 1 178 2 537 分析 根据二进制数 满二进一 的原则 可以用2连续去除89获所得的商 然后取余数解 89 2 44 144 2 22 022 2 11 011 2 5 15 2 2 12 2 1 01 2 0 1 89 2 2 2 2 2 2 1 1 0 0 1 2 2 2 2 22 1 1 0 0 1 2 2 2 23 21 1 0 0 1 2 2 24 22 21 0 0 1 2 25 23 22 0 0 1 26 24 23 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 例4 把89化为二进制数 所以 89 1011001 2 这种算法叫做除2取余法 还可以用下面的除法算式表示 89 44 22 11 5 2 1 0 2 2 2 2 2 2 2 1001101 解 以2作除数 相应的除法算式为 余数 所以 89 1011001 2 例4 把89化为二进制数 上述这种方法也可以推广为把十进制数化为k进制数的算法 称为除k取余法 针对性练习 1 把97化为5进制数 答案 342 5 2 把30化为2进制数 答案 11110 2 小结 2 利用 除k取余法 将十进制数转化为其他进制数 1 学会将一个k进制数转化为十进制数 2 将1231 5 化为7进制的数 练习 解 1231 5 1 53 2 52 3 51 1 50 191 10 191 10 362 7 所以1231 5 362 7 1 用 除k取余法 将十进制数2008转化为二进制数和八进制数 3 完成下列进制间的转化 2 1010111 2 4 答案 1113 4 1 213 4 3 答案 1110 3 11111011000 2 3730 8 作业 P48习题1 3A组3 要求写出过程 问题 有6个鸡蛋 用十进制数表示为 若用二进制表示呢 6 程序 x 5f x 5 x 4 x 3 x 2 x 1PRINT f 5 fEND 优点 简单易懂缺点 不通用 不能解决任意多项式的求值问题 而且计算效率不高 思考 这个程序中 一共用了几次乘法 几次加法 10 5 秦九韶算法 x 7 2x4 5x3 4x2 3x 6 问题二 1 从内到外 如果把每一个括号都看成一个常数 那么变形后的式子中有哪些 一次式 x的系数依次是什么 2 若将x 5代入变形后的式了中 那么求值的过程是怎样的 3 你能把这个过程描述出来吗 改进算法 秦九韶算法 问题三 用秦九韶算法计算上述多项式的值 需要多少次乘法 多少次加法 每运算一个一次式都进行了一次乘法运算和一次加法运算 所以共做了5次乘法 5次加法 问题四 怎样用秦九韶算法求n次多项式的值 秦九韶算法 算法 秦九韶算法 i 0 i i 1 否 INPUT n nINPUT an aINPUT x xv ai n 1WHILEi 0PRINT i iINPUT ai av v x ai i 1WENDPRINTvEND 是 程序 例4设计一个算法 把k进制数a 共有n位 化为十进制数b 算法 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 开始 输入a k n b 0 i 1 把a的右数第i位数字附给t i i 1 i n 输出b 结束 否 是 INPUTa k ni 1b 0t aMOD10DOb b t k i 1 a a 10t aMOD10i i 1LOOPUNTILi nPRINTbEND 程序 程序框图 输入a k n 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 十进制数a化为k进制数的b步骤 第一步 将给定的十进制整数a除以基数k 余数便是等值的k进制数的最低位 第二步 将上一步的商再除以基数k 余数便是等值的k进制数的次低位 第三步 重复第二步 直到最后所得的商等于0为止 各次除得的余数 便是k进制数各位的数 最后一次的余数是最高位 第四步 将所得的余数从下至上写出得到b 例6设计一个程序 实现 除k取余法 算法 程序框图 开始 输入a k 求a除以k的商q 求a除以k的余数r a q q 0 输出全部余数r排列得到的k进制数 结束 把得到的余数依次从右到左排列 是 否 INPUT a k a kb 0i 0DOq a kr aMODkb b r 10 ii i 1a qLOOPUNTILq 0PRINTbEND 程序 例6设计一个程序 实现 除k取余法 537 20121 4