中国古代数学中的算法案例课件（人教b版必修3）

1．3中国古代数学中的算法案例

1．求两个正整数最大公约数的算法(1)更相减损之术(等值算法)用两数中较大的数减去较小的数，再用

和

构成新的一对数，再用大数减小数，以同样的操作一直做下去，直到产生

，这个数就是最大公约数．差数较小的数一对相等的数(2)用“等值算法〞求最大公约数的程序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，令vk＝(…(anx＋an－1)x＋…＋an－(k－1))x＋an－k，那么递推公式为

，其中k＝1,2，…，n.(2)计算P(x0)的方法先计算

，然后

逐层计算，直到

，然后加上

．最内层的括号由内向外最外层括号常数项本节重点：秦九韶算法的原理、算法设计和无限逼近的思想．本节难点：理解算法案例的内容及具体算法设计的关键步骤1．求两个正整数最大公约数的算法(1)辗转相除法①辗转相除法的理论根底m，n，r为正整数，假设m＝nq＋r(0≤r<n)(即r＝mmodn)，那么(m，n)＝(n，r)．其中(m，n)表示m和n的最大公约数．事实上，由m＝nq＋r知n和r的公约数都是m和n的公约数；由r＝m－nq知m和n的公约数都是n和r的公约数．故m和n的公约数与n和r的公约数都相同，其最大公约数也相同．②辗转相除法的步骤用辗转相除法求两个正整数的最大公约数，其算法可以用自然语言描述如下：第一步，给定两个正整数m，n；第二步，计算m除以n所得的余数r；第三步，m＝n，n＝r；第四步，假设r＝0，那么m，n的最大公约数等于m；否那么，返回第二步．从其算法思想我们可以看出，辗转相除法的根本步骤是用较大的数(用a表示)除以较小的数(用b表示)，得到除式：a＝nb＋r(0≤r<b)．由于这是一个反复执行的步骤，且执行的次数由余数r是否等于0决定，所以我们可以把它看作一个循环体，用循环结构就可以来实现其算法．(2)更相减损术(“等值算法〞)步骤：我们以求119和85这两个数的最大公约数为例加以说明：以两数中较大的数减去较小的数，即119－85＝34，以差数34和较小的数85构成新的一对数，对这一对数再用大数减去小数，即85－34＝51，再以差数51和34构成新的一对数，大数减去小数，这样的操作一直做下去，直到产生一对相等的数，这个数就是最大公约数．整个操作如下：(119,85)→(34,85)→(34,51)→(34,17)→(17,17)，∴119与85的最大公约数为17.从其算法思想我们可以看出，更相减损术的根本步骤是用较大的数(用a表示)减去较小的数(用b表示)，得到等式：r＝a－b(r为差数)．由于这是一个反复执行的步骤，且执行的次数由差数与较小的数是否相等决定，所以我们可以把它看作一个循环体，用循环结构就可以实现其算法．2．把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(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求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值．2．秦九韶算法的依据是加法对乘法的分配律，把多项式的运算分解为一次因式的乘法和加法运算．3．刘徽的割圆术是利用圆内接正多边形，随着边数的增多，正多边形的面积无限逼近圆的面积的无限逼近思想，来求圆周率π的近似值．[例1]求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.[点评]当大数减小数的差等于小数时停止减法，较小的数就是两数的最大公约数．用更相减损术求57与93的最大公约数．[解析]

(93,57)―→(36,57)―→(36,21)―→(15,21)―→(15,6)―→(9,6)―→(3,6)―→(3,3)，∴93与57的最大公约数是3.[例2]求98和280的最大公约数．[解析]

280＝98×2＋84,98＝84×1＋14,84＝14×6＋0.∴最大公约数为14.[点评]用辗转相除法求最大公约数步骤较少，而更相减损术虽然步骤较长，但运算简单．用辗转相除法求72和168的最大公约数．[解析]

168＝72×2＋24,72＝24×3＋0.∴最大公约数为24.[例3]用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．[解析]

x＝3a7＝7v0＝a7＝7；a6＝6v1＝v0x＋a6＝7×3＋6＝27；a5＝5v2＝v1x＋a5＝27×3＋5＝86；a4＝4v3＝v2x＋a4＝86×3＋4＝262；a3＝3v4＝v3x＋a3＝262×3＋3＝789；a2＝2v5＝v4x＋a2＝789×3＋2＝2369；a1＝1v6＝v5x＋a1＝2369×3＋1＝7108；a0＝0v7＝v6x＋a0＝7108×3＋0＝21324.所以f(3)＝21324.[点评]利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算需用到前项的结果，故应认真、细心，确保中间结果的准确性．用秦九韶算法时，关键是理解在其中用到的递推公式 ，其中k＝1,2，…，n.一个5次多项式函数f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值．[解析]

根据秦九韶算法原理，先将所给的多项式进行改写，然后由内向外逐层计算即可．f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8＝((((5x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，v0＝5，v1＝5×5＋2＝27，v2＝27×5＋3.5＝138.5，v3＝138.5×5－2.6＝689.9，v4＝689.9×5＋1.7＝3451.2，v5＝3451.2×5－0.8＝17255.2.所以，当x＝5时，多项式的值等于17255.2.[例4]求三个数324,243,270的最大公约数．[解析]324＝243×1＋81,243＝81×3＋0，那么324与243的最大公约数为a＝81.又270＝81×3＋27,81＝27×3＋0，那么324,243,270的最大公约数为27.[点评]求三个数的最大公约数，可先求两数的最大公约数a，然后求a与第三个数的最大公约数b，那么b为所求的三数的最大公约数．该题解法可推广到求多个数的最大公约数．求324,243和135的最大公约数．[解析](324,243)―→(81,243)―→(81,162)―→(81,81)那么324与243最大公约数为81.又(81,135)―→(81,54)―→(27,54)―→(27,27)，那么81与135的最大公约数为27，∴324、243、135的最大公约数为27.[例5]求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＋836＝8×4＋4＝8＝4×2＋0∴80与36的最大公约数为4.∴80与36的最小公倍数是(80×36)÷4＝720.[例6]f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求这个多项式当x＝2时的值时，做了几次乘法？几次加法？[误解]根据秦九韶算法，把多项式改写成如下形式f(x)＝((((x＋2)x＋3)x＋4)x＋5)x＋6.按照从内到外的顺序，依次计算一次多项式当x＝2时的值：v1＝2＋2＝4，v2＝2v1＋3＝11，v3＝2v2＋4＝26，v4＝2v3＋5＝57，v5＝2v4＋6＝120.显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．[辨析]在v1中虽然“v1＝2＋2＝4〞，而计算机还是做了1次乘法“v1＝2×1＋2＝4〞．因为用秦九韶算法计算多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值时，首先将多项式改写成f(x)＝(…(anx＋an－1)x＋…＋a1)x＋a0，然后再计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0无论an是不是1，这次的乘法都是要进行的．[正解]由以上分析可知，做了5次乘法，5次加法．一、选择题1．用更相减损之术求88与24的最大公约数为()A．2 B．7C．8 D．12[答案]C[解析]

(88,24)→(64,24)→(40,24)→(24,16)→(16,8)→(8,8)，故88与24的最大公约数为8.2．用秦九韶算法求多项式f(x)＝x3－3x2＋2x－11的值时，应把f(x)变形为()A．x3－(3x＋2)x－11B．(x－3)x2＋(2x－11)C．(x－1)(x－2)x－11D．((x－3)x＋2)x－11[答案]

D3．用程序框图表示“割圆术〞，将用到()A．顺序结构B．条件分支结构C．顺序结构和循环结构D．三种根本逻辑结构[答案]D二、填空题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时的值，需要进行________次乘法和_____