高中数学人教版必修三：1.3算法案例ppt课件.pptVIP

算法案例 第一课时 1 求两个正整数的最大公约数 1 求25和35的最大公约数 2 求225和135的最大公约数 2 求8251和6105的最大公约数 所以 25和35的最大公约数为5 所以 225和135的最大公约数为45 辗转相除法 欧几里得算法 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 思考 从上述的过程你体会到了什么 完整的过程 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 例2用辗转相除法求225和135的最大公约数 225 135 1 90 135 90 1 45 90 45 2 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 思考1 从上面的两个例子可以看出计算的规律是什么 S1 用大数除以小数 S2 除数变成被除数 余数变成除数 S3 重复S1 直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mMODn m n n r r 0 是 否 思考2 辗转相除法中的关键步骤是哪种逻辑结构 INPUTm nDOr mmodnm nn rLOOPUNTILr 0PRINTmEnd 九章算术 更相减损术 算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是 则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数或这个等数与约简的数的乘积就是所求的最大公约数 例3用更相减损术求225与135的最大公约数 解 由于两数不是偶数 把225和135以大数减小数 并辗转相减 225 135 90135 90 4590 45 45 所以 225和135的最大公约数等于45 INPUTa bWHILEabIFa bTHENa a bELSEb b aENDIFWENDPRINTaEND 九章算术 更相减损术的算法程序语句 练习 用辗转相除法求294与84的最大公约数 再用更相减损术验证 思考 求三个数 168 54 264的最大公约数 算法案例 第二课时 计算多项式 当x 5的值 算法1 x x x x x x x x x x x x x x x 1 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 算法2 5 5 5 5 5 5 5 5 5 5 5 分析 两种算法中各用了几次乘法运算 和几次加法运算 x 1 x 1 x 1 x 1 x 1 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 这样改写的目的是什么 简化计算的次数 尤其是乘法的次数 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考 在求多项式的值上 这是怎样的一个转化 例2已知一个五次多项式为 用秦九韶算法求这个多项式当x 5的值 解 将多项式变形 按由里到外的顺序 依此计算一次多项式当x 5时的值 所以 当x 5时 多项式的值等于17255 2 你从中看到了怎样的规律 怎么用程序框图来描述呢 练习 2 已知多项式f x 2x7 5x5 4x3 x2 x 6用秦九韶算法求这个多项式当x 2时的值 INPUT n nINPUT an aiINPUT x xV ani n 1DOPRINT i iINPUT ai aiv v x aii i 1LOOPUNTILi 0PRINTvEND 算法案例 第三课时 一 进位制 1 什么是进位制 2 最常见的进位制是什么 除此之外还有哪些常见的进位制 请举例说明 进位制是人们为了计数和运算方便而约定的记数系统 1 我们了解十进制吗 所谓的十进制 它是如何构成的 十进制由两个部分构成 例如 3721 其它进位制的数又是如何的呢 第一 它有0 1 2 3 4 5 6 7 8 9十个数字 第二 它有 权位 即从右往左为个位 十位 百位 千位等等 用10个数字来记数 称基数为10 表示有 1个1 2个十 7个百即7个10的平方 3个千即3个10的立方 2 二进制 二进制是用0 1两个数字来描述的 如11001等 二进制的表示方法 区分的写法 11001 2 或者 11001 2 8进制呢 如7342 8 k进制呢 anan 1an 2 a2a1 k 二 二进制与十进制的转换 1 二进制数转化为十进制数 例1将二进制数110011 2 化成十进制数 解 根据进位制的定义可知 所以 110011 2 51 将 1 10303 4 2 1234 5 化为十进制数 练习 将下面的二进制数化为十进制数 1 11 2 101 3 1101 4 10101 例2已知10b1 2 a02 3 求数字a b的值 所以2b 9 9a 2 即9a 2b 7 10b1 2 1 23 b 2 1 2b 9 a02 3 a 32 2 9a 2 故a 1 b 1 将k进制数a转换为十进制数 共有n位 的程序 a anan 1 a3a2a1 k ank n 1 an 1k n 2 a3k2 a2k1 a1k0 b a1k0 b a2k1 b b a3k2 b b ankn 1 b ai GETa i GET函数用于取出a的右数第i位数 i i 1 i 1 b aiki 1 b INPUT a k n a k nb 0i 0t aMOD10DOb b t k i 1 a a 10t aMOD10i i 1LOOPUNTILi nPRINTbEND 2 十进制转换为二进制 除2取余法 用2连续去除89或所得的商 然后取余数 例2把89化为二进制数 解 根据 逢二进一 的原则 有 89 2 44 1 2 2 22 0 1 2 2 2 11 0 0 1 2 2 2 2 5 1 0 0 1 5 2 2 1 2 2 2 2 22 1 1 0 0 1 89 1 26 0 25 1 24 1 23 0 22 0 21 1 20 所以 89 1011001 2 2 2 2 23 2 1 0 0 1 2 2 24 22 2 0 0 1 2 25 23 22 0 0 1 26 24 23 0 0 21 89 2 44 1 44 2 22 0 22 2 11 0 11 2 5 1 2 2 2 2 2 2 1 1 0 0 1 所以89 2 2 2 2 2 2 1 1 0 0 1 2 十进制转换为二进制 例2把89化为二进制数 5 2 2 2 1 2 0 1 0 余数 11 22 48 89 2 2 2 2 0 1 1 0 1 注意 1 最后一步商为0 2 将上式各步所得的余数从下到上排列 得到 89 1011001 2 练习 将下面的十进制数化为二进制数 1 10 2 20 3 128 4 256 例3把89化为五进制数 3 十进制转换为其它进制 解 根据除k取余