高中数学 1.3中国古代数学中的算法案例课件 新人教B版必修3.ppt

成才之路 数学 路漫漫其修远兮吾将上下而求索 人教B版 必修3 算法初步 第一章 1 3中国古代数学中的算法案例 第一章 韩信是秦末汉初的著名军事家 据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场 刘邦问韩信有什么方法 不要逐个报数 就能知道场上的士兵的人数 韩信先令士兵排成3列纵队 结果有2个人多余 接着下令将队形改为5列纵队 这一改 又多出3人 随后他又下令改为7列纵队 这次又剩下2人无法成整行 在场的人都哈哈大笑 以为韩信不能清点出准确的人数 不料笑声刚落 韩信高声报告共有士兵2333人 众人听了一愣 不知道韩信用什么方法这么快就能得出正确的结果的 1 求两个正整数最大公约数的算法 1 更相减损之术 等值算法 用两数中较大的数减去较小的数 再用 和 构成新的一对数 再用大数减小数 以同样的操作一直做下去 直到产生 这个数就是最大公约数 差数 较小的数 一对相等的数 while a a b b b a end 2 割圆术用圆内接正多边形面积逐渐逼近 的算法是计算圆周率的一种方法 3 秦九韶算法 1 把一元n次多项式P x anxn an 1xn 1 a1x a0改写为P x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 圆的面积 v0 an vk vk 1x an k 最内层的括号 由内向外 最外层括号 常数项 1 秦九韶算法与直接计算相比较 下列说法错误的是 A 秦九韶算法与直接计算相比 大大节省乘法的次数 使计算量减少 并且逻辑结构简单B 秦九韶算法减少做乘法的次数 在计算机上也就加快了计算的速度C 秦九韶算法减少做乘法的次数 在计算机上也就降低了计算的速度D 秦九韶算法避免对自变量x单独做幂的计算 而是与系数一起逐次增长幂次 从而可提高计算的精度 答案 C 2 用圆内接正多边形逼近圆 因而得到的圆周率总是 的实际值 A 大于等于B 小于等于C 等于D 小于 答案 D 解析 用割圆术法求出的是 的不足近似值 故选D 3 用更相减损之术求88与24的最大公约数为 A 2B 7C 8D 12 答案 C 解析 88 24 64 24 40 24 24 16 16 8 8 8 故88与24的最大公约数为8 4 三个数72 120 168的最大公约数是 答案 24 解析 72 120 168 72 120 168 120 72 120 48 72 120 72 48 72 48 48 72 48 48 48 24 48 48 24 48 24 48 24 24 48 24 24 48 24 24 24 24 5 用秦九韶算法计算f x 9x6 3x5 4x4 6x3 x2 8x 1 当x 3时的值 需要进行 次乘法和 次加法运算 答案 66 解析 f x 9x 3 x 4 x 6 x 1 x 8 x 1 乘法及加法运算都是6次 6 2015 河北成安县一中高一月考 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解析 f x 2x5 5x4 4x3 3x2 6x 7 2x 5 x 4 x 3 x 6 x 7 x 5时 有v0 a5 2 v1 v0 x a4 2 5 5 5 v2 v1x a3 5 5 4 21 v3 v2x a2 21 5 3 108 v4 v3x a1 108 5 6 534 v5 v4x a0 534 5 7 2677 当x 5时 多项式的值为2677 求80和36的最大公约数 解析 80 36 44 44 36 8 36 8 28 28 8 20 20 8 12 12 8 4 8 4 4 80和36的最大公约数是4 点评 当大数减小数的差等于小数时停止减法 较小的数就是两数的最大公约数 用更相减损术求两个正整数的最大 用更相减损术分别求下列两组数的最大公约数 1 78与36 2 1515与600 解析 1 78 36 42 36 6 36 6 30 6 24 6 18 6 12 6 6 故78与36的最大公约数为6 2 1515 600 915 915 600 315 600 315 285 315 285 30 285 30 255 255 30 225 225 30 195 195 30 165 165 30 135 135 30 105 105 30 75 75 30 45 45 30 15 30 15 15 故1515与600的最大公约数是15 用辗转相除法求546与429的最大公约数 解析 546 1 429 117 429 3 117 78 117 1 78 39 78 2 39 故546与429的最大公约数为39 点评 用辗转相除法求最大公约数步骤较少 而更相减损术虽然步骤较长 但运算简单 用辗转相除法求两个正整数的最大公约数 用辗转相除法求288和123的最大公约数 解析 288 2 123 42 123 2 42 39 42 1 39 3 39 13 3 故3就是288和123的最大公约数 用秦九韶算法求多项式f x x5 0 11x3 0 15x 0 04当x 0 3时的值 解析 将f x 写为 f x x5 0 x4 0 11x3 0 x2 0 15x 0 04 由秦九韶算法的递推公式 得v0 1 v1 v0 0 3 0 0 3 v2 v1 0 3 0 11 0 2 用秦九韶算法求多项式的值 v3 v2 0 3 0 0 06 v4 v3 0 3 0 15 0 132 v5 v4 0 3 0 04 0 0796 所以当x 0 3时 多项式的值为 0 0796 点评 1 用秦九韶算法求多项式的值 首先要将多项式改写 然后由内向外逐次计算 由于下一次计算要用到上一次的结果 故应认真 细心 确保每个中间结果的准确性 2 当多项式中有几项不存在时 可将这几项的系数看成是0 即0 xn 已知函数f x x3 2x2 5x 6 用秦九韶算法求f 10 的值 解析 由秦九韶法 得f x x3 2x2 5x 6 x2 2x 5 x 6 x 2 x 5 x 6 当x 10时 f 10 10 2 10 5 10 6 8 10 5 10 6 75 10 6 756 求三个数319 377 116的最大公约数 分析 三个数的最大公约数分别是每个数的约数 因此也是任意两个数的最大公约数的约数 也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数 求三个正整数的最大公约数 解析 解法一 辗转相除法 先求319与377的最大公约数 377 319 1 58 319 58 5 29 58 29 2 319与377的最大公约数是29 再求29与116的最大公约数 116 29 4 29与116的最大公约数为29 319 377 116的最大公约数是29 解法二 更相减损术 先求319与377的最大公约数 377 319 58 319 58 261 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 319与377的最大公约数是29 再求29与116的最大公约数 116 29 87 87 29 58 58 29 29 29与116的最大公约数是29 319 337 116的最大公约数是29 求出三个数1734 816 1343的最大公约数 解析 解法一 辗转相除法 先求1734和816的最大公约数 1734 816 2 102 816 102 8 所以1734与816的最大公约数为102 再求102与1343的最大公约数 1343 102 13 17 102 17 6 所以1343与102的最大公约数为17 即1734 816 1343的最大公约数为17 解法二 更相减损术 1734 816 918 918 816 102 816 102 714 714 102 612 612 102 510 510 102 408 408 102 306 306 102 204 204 102 102 所以1734和816的最大公约数为102 再求102和1343的最大公约数 1343 102 1241 1241 102 1139 1139 102 1037 1037 102 935 935 102 833 833 102 731 731 102 629 629 102 527 527 102 425 425 102 323 323 102 221 221 102 119 119 102 17 102 17 85 85 17 68 68 17 51 51 17 34 34 17 17 所以1343与102的最大公约数为17 即1734 816 1343的最大公约数为17 求375 85的最小公倍数 解析 先求最大公约数 375 85 4 35 85 35 2 15 35 15 2 5 15 5 3 0 375与85的最大公约数是5 375与85的最小公倍数是 375 85 5 6375 点评 求两个正整数的最小公倍数 即利用它们的积除以它们的最大公约数 本题求法可推广到求多个数的情况 求两个正整数的最小公倍数 求80与36的最小公倍数 解析 先求最大公约数 80 36 2 8 36 8 4 4 4 2 0 80与36的最大公约数为4 80与36的最小公倍数是 80 36 4 720 正解 改写多项式f x x 5 x 10 x 10 x 5 x 1 所以v0 1 v1 v0 x a4 3 v2 v1x a3 4 v3 v2x a2 2 v4 v3x a1 1 v5 v4x a0 1 f 2 1 相应的程序为