中國古代數(shù)學(xué)中的算法案例.ppt

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