中国古代算法案例中国古代算案例法案例.ppt

1.求两个正整数最大公约数的算法 (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）→（44,36） → （36,8） → （28,8） → （20,8） → （12,8） → （4,8） → （4,4） ∴80和36的最大公约数是4. [点评]　当大数减小数的差等于小数时停止减法，相同的数就是两数的最大公约数． 用更相减损术分别求下列两组数的最大公约数： (1)78与36； [解析]　(1)(78,36)→(42,36)→(6,36)→(6,30)→(6,24)→ (6,18)→(6,12)→(6,6)，故78与36的最大公约数为6. 用辗转相除法求546与429的最大公约数. [解析]　546＝1×429＋117， 429＝3×117＋78， 117＝1×78＋39， 78＝2×39， 即(546,429)→(429,117)→(117,78)→(78,39) 故546与429的最大公约数为39. [点评]　用辗转相除法求最大公约数步骤较少，而更相减损术虽然步骤较长，但运算简单． 用辗转相除法求288和123的最大公约数． [解析]　288＝2×123＋42， 123＝2×42＋39， 42＝1×39＋3， 39＝13×3， 即(288,123)→(123,42)→(42,39)→(3,39) 故3就是288和123的最大公约数. 求三个数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. 求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＝6 375. 求80与36的最小公倍数． [解析]　先求最大公约数． 80＝36×2＋8， 36＝8×4＋4 8＝4×2＋0， ∴80与36的最大公约数为4. ∴80与36的最小公倍数是(80×36)÷4＝720. 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， 用秦九韶算法求多项式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.079 6， 所以当x＝0.3时，多项式的值为－0.079 6. [点评]　(1)用秦九韶算法求多项式的值，首先要将多项式改写，然后由内向外