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

1、中國古代數(shù)學(xué)中的算法案例中國古代數(shù)學(xué)中的算法案例 中國古代數(shù)學(xué)中的算法案例最大公約數(shù)中國古代數(shù)學(xué)中的算法案例定定 義義l如果有一個自然數(shù)a能被自然數(shù)b整除，則稱a為b的倍數(shù)，b為a的約數(shù)。幾個自然數(shù)公有的約數(shù)，叫做這幾個自然數(shù)的公約數(shù)。公約數(shù)中最大的一個公約數(shù)，稱為這幾個自然數(shù)的最大公約數(shù)。中國古代數(shù)學(xué)中的算法案例 更相減損術(shù) （出自九章算術(shù)）求得最大公約數(shù)的方法 輾轉(zhuǎn)相除法 （歐幾里得算法）中國古代數(shù)學(xué)中的算法案例更相減損術(shù)中國古代數(shù)學(xué)中的算法案例簡介簡介l更相減損術(shù)是出自九章算術(shù)的一種求最大公約數(shù)的算法，它原本是為為約分而設(shè)計(jì)的約分而設(shè)計(jì)的。 但但它適用于任何任何需要求最大公約數(shù)的場合。中

2、國古代數(shù)學(xué)中的算法案例如何使用如何使用l求求98與與63的最大公約數(shù)。的最大公約數(shù)。 l解：解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減：l 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 98和63的最大公約數(shù)等于7。 中國古代數(shù)學(xué)中的算法案例 得 與 有相同的公約數(shù)理論依據(jù)rbarbarbarbaba,ba,rb,中國古代數(shù)學(xué)中的算法案例算法表示算法表示 lS1：輸入兩個正數(shù)a,b(ab) ；lS2：如果ab，則執(zhí)行S3，否則轉(zhuǎn)到S5；lS3：將a-b的值賦予r；lS4：若br，則把b賦予a，把r賦予b，否則把 r賦予a，重新

3、執(zhí)行S2；lS5：輸出最大公約數(shù)b.中國古代數(shù)學(xué)中的算法案例輸出輸出bYN輸入輸入a,ba b結(jié)束結(jié)束開始開始a bb=baa=abYN中國古代數(shù)學(xué)中的算法案例程序：程序：a=input(“a=”)；b=input(“b=”)；while ab if a=b a=ab; else b=ba； endendprint(%io(2), b, “兩數(shù)的最大公約數(shù)兩數(shù)的最大公約數(shù)為：為：” )中國古代數(shù)學(xué)中的算法案例輾轉(zhuǎn)相除法中國古代數(shù)學(xué)中的算法案例輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法l輾轉(zhuǎn)相除法最早出現(xiàn)在歐幾里得的幾何原本中（大約公元前300年），所以它是現(xiàn)在仍在使用的算法中最早出現(xiàn)的。歐幾里得中國古代數(shù)學(xué)中的算法

4、案例如何使用如何使用l以求288和123的最大公約數(shù)為例，操作如下： lS1：288123=242 lS2：12342=239 lS3：4239=13 lS4：393=13 3就是288和123的最大公約數(shù)。這是一個輾轉(zhuǎn)相處的過程中國古代數(shù)學(xué)中的算法案例理論依據(jù)nbarrnbaba,得 與 有相同的公約數(shù) rb,中國古代數(shù)學(xué)中的算法案例 第一步第一步：輸入兩個：輸入兩個正整數(shù)正整數(shù)a，b（ab）; 第二步第二步：求出：求出ab的余數(shù)的余數(shù)r； 第三步第三步：令：令a=b，b=r，若，若r0，重復(fù)第二，重復(fù)第二步；步； 第四步第四步：輸出最大：輸出最大公約數(shù)公約數(shù)a.中國古代數(shù)學(xué)中的算法案例l更

5、相減損術(shù)更相減損術(shù)和輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法的主要區(qū)別在于: 前者所使用的運(yùn)算是“減減”，后者是“除除”。從算法思想上看，兩者并沒有本質(zhì)上的區(qū)別，但是在計(jì)算過程中，如果遇到一個數(shù)很大，另一個數(shù)比較小的情況，可能要進(jìn)行很多次減法才能達(dá)到一次除法的效果，所以輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法更好一些。中國古代數(shù)學(xué)中的算法案例割圓術(shù)割圓術(shù)中國古代數(shù)學(xué)中的算法案例n早在我國先秦時期，墨經(jīng)上就已經(jīng)給出了圓的定義。我國古代數(shù)學(xué)經(jīng)典九章算術(shù)在第一章“方田”章中寫到“半周半徑相乘得積步”，也就是我們現(xiàn)在所熟悉的公式。n為了證明這個公式，我國魏晉時期數(shù)學(xué)家劉徽寫了一篇1800余字的注記，這篇注記就是數(shù)學(xué)史上著名的“割圓術(shù)”。中國

6、古代數(shù)學(xué)中的算法案例 劉徽形容他的“割圓術(shù)”說：割之彌細(xì)，所失彌少，割之又割，以至于不可割，則與圓合體，而無所失矣。 簡單來說所謂“割圓術(shù)”，是用圓內(nèi)接正多邊形的周長去無限逼近圓周并以此求取圓周率的方法。 中國古代數(shù)學(xué)中的算法案例計(jì)算方法計(jì)算方法n第一，從半徑為第一，從半徑為1 1的圓內(nèi)接正六邊形開的圓內(nèi)接正六邊形開始，計(jì)算它的面積始，計(jì)算它的面積S6S6；n第二，逐步加倍圓內(nèi)接正多邊形的邊數(shù)，第二，逐步加倍圓內(nèi)接正多邊形的邊數(shù)，分別計(jì)算圓內(nèi)接正十二邊形，正二十四分別計(jì)算圓內(nèi)接正十二邊形，正二十四邊形，正四十八邊形，邊形，正四十八邊形，的面積，到一的面積，到一定的邊數(shù)（設(shè)為定的邊數(shù)（設(shè)為2 2

7、m m）為止，得到一列遞）為止，得到一列遞增的數(shù)，增的數(shù)， S6S6，S12S12，S24S24，S48S48，S2S2n n. .n第三，第三，S2nS2n近似等于圓面積。近似等于圓面積。中國古代數(shù)學(xué)中的算法案例下面的關(guān)鍵是找出正下面的關(guān)鍵是找出正n n邊形的面積與正邊形的面積與正2 2n n邊形的面積之間的關(guān)系，以便遞推。邊形的面積之間的關(guān)系，以便遞推。設(shè)圓的半徑為設(shè)圓的半徑為1 1，正，正n n邊形邊形的邊長的邊長ABAB為為x xn n，弦心距，弦心距OGOG為為h hn n；面積為；面積為S Sn n，根據(jù)勾股，根據(jù)勾股定理，得：定理，得：22221,21(6)2nnnnnxhxxh

8、n中國古代數(shù)學(xué)中的算法案例容易知道容易知道x x6 6=1,=1, 正正2 2n n邊形的面積等于正邊形的面積等于正n n邊形的面積加上邊形的面積加上n n個等腰三個等腰三角形的面積，即角形的面積，即21(1)(6)2nnnnSSnxhn于是由于是由6364S 求得求得S12=3；S243.105828；中國古代數(shù)學(xué)中的算法案例 按照這樣的思路，劉徽把圓內(nèi)接正多邊形的面積一直算到了正3072邊形，并由此而求得了圓周率 為3.14和 3.1416這兩個近似數(shù)值。這個結(jié)果是當(dāng)時世界上圓周率計(jì)算的最精確的數(shù)據(jù)。 中國古代數(shù)學(xué)中的算法案例n=6;x=1;s=6*sqrt(3)/4;for i=1 :

9、1 : 5h=sqrt(1(x/2)2);s=s+n*x*(1h)/2;n=2*n;x=sqrt(x/2)2+(1h)2);endprint(%io(2), n, s) 程序編寫中國古代數(shù)學(xué)中的算法案例中國古代數(shù)學(xué)中的算法案例 秦九韶（秦九韶（1208年年1261年）年）南宋官員、數(shù)學(xué)家，與李冶、楊輝、南宋官員、數(shù)學(xué)家，與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。字道朱世杰并稱宋元數(shù)學(xué)四大家。字道古，漢族，自稱魯郡（今山東曲阜）古，漢族，自稱魯郡（今山東曲阜）人，生于普州安岳（今屬四川）。人，生于普州安岳（今屬四川）。精研星象、音律、算術(shù)、詩詞、弓精研星象、音律、算術(shù)、詩詞、弓劍、營造之學(xué)，歷任瓊

10、州知府、司劍、營造之學(xué)，歷任瓊州知府、司農(nóng)丞，后遭貶，卒于梅州任所，著農(nóng)丞，后遭貶，卒于梅州任所，著作作數(shù)書九章數(shù)書九章，其中的大衍求一，其中的大衍求一術(shù)、三斜求積術(shù)和秦九韶算法是具術(shù)、三斜求積術(shù)和秦九韶算法是具有世界意義的重要貢獻(xiàn)。有世界意義的重要貢獻(xiàn)。 中國古代數(shù)學(xué)中的算法案例 數(shù)書九章數(shù)書九章在數(shù)學(xué)內(nèi)容上頗多創(chuàng)新。中國算籌式記數(shù)在數(shù)學(xué)內(nèi)容上頗多創(chuàng)新。中國算籌式記數(shù)法及其演算式在此得以完整保存；自然數(shù)、分?jǐn)?shù)、小數(shù)、負(fù)法及其演算式在此得以完整保存；自然數(shù)、分?jǐn)?shù)、小數(shù)、負(fù)數(shù)都有專條論述，還第一次用小數(shù)表示無理根的近似值；卷數(shù)都有專條論述，還第一次用小數(shù)表示無理根的近似值；卷1大衍類中靈活運(yùn)用最

11、大公約數(shù)和最小公倍數(shù)，并首創(chuàng)連環(huán)大衍類中靈活運(yùn)用最大公約數(shù)和最小公倍數(shù)，并首創(chuàng)連環(huán)求等，借以求幾個數(shù)的最小公倍數(shù)；在求等，借以求幾個數(shù)的最小公倍數(shù)；在孫子算經(jīng)孫子算經(jīng)中中“物物不知數(shù)不知數(shù)”問題的基礎(chǔ)上總結(jié)成大衍求一術(shù)，使一次同余式組問題的基礎(chǔ)上總結(jié)成大衍求一術(shù)，使一次同余式組的解法規(guī)格化、程序化，比西方高斯創(chuàng)用的同類方法早的解法規(guī)格化、程序化，比西方高斯創(chuàng)用的同類方法早500多年，被公認(rèn)為多年，被公認(rèn)為“中國剩余定理此外，秦九韶還改進(jìn)了一次中國剩余定理此外，秦九韶還改進(jìn)了一次方程組的解法，用互乘對減法消元，與現(xiàn)今的加減消元法完方程組的解法，用互乘對減法消元，與現(xiàn)今的加減消元法完全一致。全一致

12、。中國古代數(shù)學(xué)中的算法案例已知一個一元已知一個一元n次多項(xiàng)式函數(shù)次多項(xiàng)式函數(shù): P(x)=anxn+an-1xn-1+a1x+ao當(dāng)知道當(dāng)知道x值時，我們可以按順序一項(xiàng)一項(xiàng)的計(jì)算，值時，我們可以按順序一項(xiàng)一項(xiàng)的計(jì)算，然后相加，求出然后相加，求出P(x)中國古代數(shù)學(xué)中的算法案例設(shè)有設(shè)有n+1項(xiàng)的項(xiàng)的n次函數(shù)，即：次函數(shù)，即：再將括號內(nèi)的前再將括號內(nèi)的前n-1項(xiàng)提取公因數(shù)項(xiàng)提取公因數(shù)x,得得:將前將前n項(xiàng)提取公因數(shù)項(xiàng)提取公因數(shù)x ，得，得:中國古代數(shù)學(xué)中的算法案例如此如此反復(fù)提取公因數(shù)反復(fù)提取公因數(shù)x ，最后將函數(shù)化為，最后將函數(shù)化為:令令.則：則： fn即為所求即為所求中國古代數(shù)學(xué)中的算法案例怎

13、樣用怎樣用程序框圖程序框圖表示秦九韶算法表示秦九韶算法 ？ 觀察秦九韶算法的數(shù)學(xué)模型，計(jì)算觀察秦九韶算法的數(shù)學(xué)模型，計(jì)算vk時時要用到要用到fk1的值，若令的值，若令f0=an，我們可以得，我們可以得到下面的遞推公式：到下面的遞推公式：f0=anfk=fk1x+ank (k=1, 2, , n) 這是一個在秦九韶算法中反復(fù)執(zhí)行的這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用步驟，可以用循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。來實(shí)現(xiàn)。中國古代數(shù)學(xué)中的算法案例k=k1f=f*x +ak輸出輸出S結(jié)束結(jié)束k=n, f=an開始開始輸入輸入x,n;a0,a1,a2,ank0是是否否中國古代數(shù)學(xué)中的算法案例Scilab語

14、言：語言： 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:); 中國古代數(shù)學(xué)中的算法案例n=input(n=); /輸入多項(xiàng)式次數(shù)輸入多項(xiàng)式次數(shù)a=zeros(1,n+1); /定義帶下標(biāo)的變量定義帶下標(biāo)的變量for i=1:1:n+1a(i)=input(a(i)=); /順次輸入系數(shù)順次輸入系數(shù)a0,a1,.,anendx=input(x=); /輸入自變量的值輸入自變量的值y=a(n+1);for i=1:1:n y=y*x+a(n+1i);endy中國古代數(shù)學(xué)中的算法案例 這種計(jì)算方法，稱之為秦九韶方法。直到今這種計(jì)算方法，稱之為秦九韶方法。直到今天，這種算法仍是世界上多項(xiàng)式求值的最先進(jìn)的天，這種算法仍是世界上多項(xiàng)式求值的最先進(jìn)的算法。其最大的意義在于將算法。其最大的意義在于將