中國古代數學中的算法案例.ppt

中國古代數學中的算法案例,最大公約數,定 義,如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。,更相減損術 （出自九章算術）,求得最大公約數的方法,輾轉相除法 （歐幾里得算法）,更相減損術,簡介,更相減損術是出自九章算術的一種求最大公約數的算法，它原本是為約分而設計的。 但它適用于任何需要求最大公約數的場合。,如何使用,求98與63的最大公約數。 解：由于63不是偶數，把98和63以大數減小數，并輾轉相減： 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 98和63的最大公約數等于7。,得 與 有相同的公約數,理論依據,算法表示,S1：輸入兩個正數a,b(ab) ； S2：如果ab，則執(zhí)行S3，否則轉到S5； S3：將a-b的值賦予r； S4：若br，則把b賦予a，把r賦予b，否則把 r賦予a，重新執(zhí)行S2； S5：輸出最大公約數b.,輸出b,Y,N,輸入a,b,a b,結束,開始,a b,b=ba,a=ab,Y,N,程序：,a=input(“a=”)； b=input(“b=”)； while ab if a=b a=ab; else b=ba； end end print(%io(2), b, “兩數的最大公約數為：” ),輾轉相除法,輾轉相除法,輾轉相除法最早出現在歐幾里得的幾何原本中（大約公元前300年），所以它是現在仍在使用的算法中最早出現的。,歐幾里得,如何使用,以求288和123的最大公約數為例，操作如下： S1：288123=242 S2：12342=239 S3：4239=13 S4：393=13 3就是288和123的最大公約數。,這是一個輾轉相處的過程,理論依據,得 與 有相同的公約數,第一步：輸入兩個正整數a，b（ab）; 第二步：求出ab的余數r； 第三步：令a=b，b=r，若r0，重復第二步； 第四步：輸出最大公約數a.,更相減損術和輾轉相除法的主要區(qū)別在于: 前者所使用的運算是“減”，后者是“除”。從算法思想上看，兩者并沒有本質上的區(qū)別，但是在計算過程中，如果遇到一個數很大，另一個數比較小的情況，可能要進行很多次減法才能達到一次除法的效果，所以輾轉相除法更好一些。,割圓術,早在我國先秦時期，墨經上就已經給出了圓的定義。我國古代數學經典九章算術在第一章“方田”章中寫到“半周半徑相乘得積步”，也就是我們現在所熟悉的公式。 為了證明這個公式，我國魏晉時期數學家劉徽寫了一篇1800余字的注記，這篇注記就是數學史上著名的“割圓術”。,劉徽形容他的“割圓術”說：割之彌細，所失彌少，割之又割，以至于不可割，則與圓合體，而無所失矣。 簡單來說所謂“割圓術”，是用圓內接正多邊形的周長去無限逼近圓周并以此求取圓周率的方法。,計算方法,第一，從半徑為1的圓內接正六邊形開始，計算它的面積S6； 第二，逐步加倍圓內接正多邊形的邊數，分別計算圓內接正十二邊形，正二十四邊形，正四十八邊形，的面積，到一定的邊數（設為2m）為止，得到一列遞增的數， S6，S12，S24，S48，S2n. 第三，S2n近似等于圓面積。,下面的關鍵是找出正n邊形的面積與正2n邊形的面積之間的關系，以便遞推。,設圓的半徑為1，正n邊形的邊長AB為xn，弦心距OG為hn；面積為Sn，根據勾股定理，得：,容易知道x6=1,正2n邊形的面積等于正n邊形的面積加上n個等腰三角形的面積，即,于是由,求得S12=3；,S243.105828；,按照這樣的思路，劉徽把圓內接正多邊形的面積一直算到了正3072邊形，并由此而求得了圓周率 為3.14和 3.1416這兩個近似數值。這個結果是當時世界上圓周率計算的最精確的數據。,n=6; x=1; s=6*sqrt(3)/4; for i=1 : 1 : 5 h=sqrt(1(x/2)2);,s=s+n*x*(1h)/2; n=2*n; x=sqrt(x/2)2+(1h)2); end print(%io(2), n, s),程序編寫,秦九韶算法,秦九韶（1208年1261年）南宋官員、數學家，與李冶、楊輝、朱世杰并稱宋元數學四大家。字道古，漢族，自稱魯郡（今山東曲阜）人，生于普州安岳（今屬四川）。精研星象、音律、算術、詩詞、弓劍、營造之學，歷任瓊州知府、司農丞，后遭貶，卒于梅州任所，著作數書九章，其中的大衍求一術、三斜求積術和秦九韶算法是具有世界意義的重要貢獻。,人物介紹,數書九章在數學內容上頗多創(chuàng)新。中國算籌式記數法及其演算式在此得以完整保存；自然數、分數、小數、負數都有專條論述，還第一次用小數表示無理根的近似值；卷1大衍類中靈活運用最大公約數和最小公倍數，并首創(chuàng)連環(huán)求等，借以求幾個數的最小公倍數；在孫子算經中“物不知數”問題的基礎上總結成大衍求一術，使一次同余式組的解法規(guī)格化、程序化，比西方高斯創(chuàng)用的同類方法早500多年，被公認為“中國剩余定理此外，秦九韶還改進了一次方程組的解法，用互乘對減法消元，與現今的加減消元法完全一致。,成就,已知一個一元n次多項式函數: P(x)=anxn+an-1xn-1+a1x+ao,當知道x值時，我們可以按順序一項一項的計算，然后相加，求出P(x),秦九韶算法,設有n+1項的n次函數，即：,再將括號內的前n-1項提取公因數x,得:,將前n項提取公因數x ，得:,秦九韶算法,如此反復提取公因數x ，最后將函數化為:,則： fn即為所求,秦九韶算法,怎樣用程序框圖表示秦九韶算法 ？,觀察秦九韶算法的數學模型，計算vk時要用到fk1的值，若令f0=an，我們可以得到下面的遞推公式： f0=an fk=fk1x+ank (k=1, 2, , n),這是一個在秦九韶算法中反復執(zhí)行的步驟，可以用循環(huán)結構來實現。,開始,輸入 x,n;a0,a1,a2,an,k=k1,f=f*x +ak,輸出S,結束,k=n, f=an,開始,輸入x,n;a0,a1,a2,an,k0,是,否,Scilab語言：,x=input(“x=“); n=input(“n=“); result=input(“The first xishu“); for i=1 : 1 : n a=input(“xishu: “); result=result*x+a; end disp(result,“The result is:“);,n=input(“n=“); /輸入多項式次數 a=zeros(1,n+1); /定義帶下標的變量 for i=1:1:n+1 a(i)=input(“a(i)=“); /順次輸入系數a0,a1,.,an end x=input(“x=“); /輸入自變量的值 y=a(n+1); for i=1:1:n y=y*x+a(n+1i); end y,這種計算方法，稱之為秦九韶方法。直到今天，這種算法仍是世界