《2017-2018学年人教b版必修三 1.3 中国古代数学中的算法案列 第1课时 课件（45张）》由会员分享，可在线阅读，更多相关《2017-2018学年人教b版必修三 1.3 中国古代数学中的算法案列 第1课时 课件（45张）（45页珍藏版）》请在金锄头文库上搜索。
1、第一章,算法初步,1.3 算法案例,第1课时 辗转相除法与更相减损术、秦九韶算法,自主预习学案,1辗转相除法 (1)辗转相除法是用于求_的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫_ (2)所谓辗转相除法，就是对于给定的两个数，用_除以_若余数不为零，则将_构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时_就是原来两个数的最大公约数,两个正整数的最大公约数,欧几里得算法,较大的数,较小的数,余数和较小的数,较小的数,(3)算法步骤： 第一步，给定两个正整数m，n 第二步，计算m除以n所得的余数r 第三步，mn，nr 第四步，若r_，则m，n的最大公约数等于
2、m；否则，返回第_步,0,二,(4)程序框图,2更相减损术 (1)更相减损术是我国古代数学专著_ 中介绍的一种求两数最大公约数的方法 (2)更相减损术的基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用_约简；若不是，执行第二步第二步，以较大的数_较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数_为止，则这个数或这个数与约简的数的_就是所求的最大公约数,九章算术,2,减去,相等,乘积,3秦九韶算法 (1)概念：求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化
3、为求n个_多项式的值，共进行_次乘法运算和_次加法运算其过程是： 改写多项式为： f(x)anxnan1xn1a1xa0 (anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0,一次,n,n,设v1_， v2v1xan2， v3v2xan3， ， vn_,anxan1,vn1xa0,(2)算法步骤： 第一步，输入多项式的次数n、最高次项的系数an和x的值 第二步，将v的值初始化为an，将i的值初始化为n1 第三步，输入i次项的系数ai 第四步，vvxai，i_ 第五步，判断i是否大于或等于_. 若是，则返回第三步；否则，输出
4、多项式的值_,i1,0,v,(3)程序框图如图所示,解析 辗转相除法可以求两个正整数的最大公约数,A,解析 按更相减损术求最大公约数，到最后(4,4)相等，故最大公约数为4,A,解析 求36与134的最大公约数，第一步是13436326，第二步是3626110，故选D,D,解析 9863135,6535128,352817,28470，最大公约数为7,7,解析 先求245与75的最大公约数(245,75)(170,75)(95,75)(20,75) (55,20)(35,20)(15,20)(5,15)(10,5)(5,5) 故245与75的最大公约数为5， 245与75的最小公倍数为2457
5、553 675,3 675,解析 辗转相除法：357105342， 10542221， 42212 故105与357的最大公约数为21,更相减损术：357105252， 252105147， 14710542， 1054263， 634221， 422121 故105与357的最大公约数为21. 最小公倍数为105357211 785,互动探究学案,命题方向1 辗转相除法和更相减损术的应用,分析 1. 辗转相除法与更相减损术的主要区别是什么？ 2将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可,典例 1,解析 用辗转相除法： 803628， 36844， 8420 故80和3
6、6的最大公约数是4,用更相减损术检验： 803644， 44368， 36828， 28820， 20812， 1284， 844 故80和36的最大公约数是4,规律总结 1. 利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数 2利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用2约简也可以不除以2，直接求最大公约数，这样不影响最后结果 3当两个整数的差较大时，利用辗转相除法计算的次数较少,解析 (1
7、)288123242,12342239， 423913,39313， 288和123的最大公约数是3 (2)(93,57)(36,57)(36,21)(15,21)(15,6)(9,6)(3,6)(3,3)， 93与57的最大公约数是3,命题方向2 秦九韶算法的应用,分析 利用秦九韶算法一步一步地代入运算，注意本题中有某几次项不存在；在计算时，应将这些项加上，比如缺少x3这一项，可看作0x3加上,典例 2,解析 f(x)(8x5)x0)x3)x0)x0)x2)x1， 依次用公式计算当x2时的值： v08， v182521， v2212042， v3422387， v48720174， v517
8、420348， v634822698， v7698211 397， 故当x2时，多项式的值为1 397,规律总结 (1)算法一方面具有具体化、程序化、机械化的特点，同时又有高度抽象性、概括性和精确性对于一个具体算法而言，从算法分析到算法语言的实现，任何一个疏漏或错误都将导致算法的失败算法是思维的条理化、逻辑化 (2)算法既重视“算则”，更重视“算理”对于算法而言，一步一步的程序化步骤，即“算则”固然重要，但这些步骤的依据，即“算理”有着更基本的作用，“算理”是“算则”的基础，“算则”是“算理”的表现 (3)用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算当多项式函数中间出现空项
9、时，要以系数为零的齐次项补充,解析 f(x)x55x410x310x25x1 (x5)x10)x10)x5)x1， 而x2，所以有 v01，v1v0xa41(2)53， v2v1xa33(2)104， v3v2xa24(2)102， v4v3xa12(2)51， v5v4xa01(2)11 故f(2)1,命题方向3 求三个正整数的最大公约数,分析 求三个数的最大公约数，可先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数 解析 解法一(辗转相除法)：因为325130265,130652，所以325和130的最大公约数为65 因为27065410,651065,1052， 所以65
10、和270的最大公约数为5， 故325,130,270三个数的最大公约数为5,典例 3,解法二(更相减损术)：325130195,19513065,1306565 所以325和130的最大公约数是65 27065205,20565140,1406575,756510,651055,551045,451035,351025,251015,15105,1055 所以270与65的最大公约数为5 所以325,130,270的最大公约数为5,规律总结 理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的,解析 先求175与100的最大公约数： 175100175,10075125
11、， 75253， 175与100的最大公约数是25 再求25与75的最大公约数： 752550,502525， 75和25的最大公约数是25 175,100,75的最大公约数是25.,错解 因为f(x)(x1)x1)x1)x1， 所以当x3时， v01，v1314， v243113， v3133140， v440311201121， 所以当x3时， f(3)121,典例 4,辨析 当多项式中间出现空项时，用秦九韶算法求函数值要补上系数为0的相应项，忽略了这一点，导致结果出现错误 正解 原多项式可化为： f(x)(x0)x1)x1)x1)x1， 当x3时， v01，v11303，v233110，
12、 v3103131，v4313194， v59431283， 所以，当x3时， f(3)283,算法案例在实际生活中的应用,通过算法案例的学习，知道算法的核心是一般意义上的解决问题的策略的具体化对于一个实际问题，我们在分析、思考后可将之转化为数学问题，从而获得解决它的基本思路,分析 要焊接正方体，就是将两种规格的钢筋截成长度相等的钢筋条为了保证不浪费材料，应使得每种规格的钢筋截取后没有剩余，因此截取的长度应为2. 4与5. 6的公约数；为使得正方体的体积最大，因此截取的长度应为2. 4与5. 6的最大公约数.,典例 5,解析 用更相减损术来求2. 4与5. 6的最大公约数： 562. 43.
13、2， 322. 40. 8， 240. 81. 6， 160. 80. 8， 因此2. 4与5. 6的最大公约数为0. 8 所以使得正方体的棱长为0. 8m时，正方体的体积最大且不浪费材料,解析 更相减损术的理论依据是每次操作所得的两数和前两数具有相同的最大公约数,B,解析 (123,51)(72,51)(21,51)(21,30)(21,9)(12,9)(3,9) (3,6) (3，)所以共做了8次减法,D,解析 将函数式化成如下形式： f(x)(x0)x2)x3)x1)x1， 由内向外依次计算： v01， v11303， v233211， v3113336,D,解析 先求720与120的最大公约数120，再求168与120的最大公约数24，因此，720,120与168的最大公约数为24,24,解析 f(x)3x40x32x24x2(3x0)x2)x4)x2， v03， v13(2)06； v26(2)214； v314(2)424； v424(2)250 故f(2)50,课时作业学案,
