中國古代算法案例1

1、1.3 中國古代數(shù)學中的算法案例,我國人民在長期的生活，生產(chǎn)和勞動過程中，創(chuàng)造了整數(shù)、分數(shù)、小數(shù)、正負數(shù)的概念及其運算，在代數(shù)學、幾何學等方面，我國在宋，元之前也都處于世界的前列。我們在小學、中學學到的算術，代數(shù)，從記數(shù)到多元一次聯(lián)立方程的求根方法，都是我國古代數(shù)學家最先創(chuàng)造的。更為重要的是我國古代數(shù)學的發(fā)展有著自己鮮明的特色，也就是“寓理于算”，即把解決的問題“算法化”。,3 5,9 15,問題1：在小學，我們已經(jīng)學過求最大公約數(shù)的知識，你能求出18與30的最大公約數(shù)嗎？,18 30,2,3,18和30的最大公約數(shù)是23=6.,先用兩個數(shù)公有的質因數(shù)連續(xù)去除,一直除到所得的商是互質數(shù)為止,然

2、后把所有的除數(shù)連乘起來.,問題2:我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)?,1、求兩個正整數(shù)的最大公約數(shù)的算法,我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術。,更相減損術求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個

3、操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。,更相減損術,例1 用更相減損術求91與49的最大公約數(shù).,解：由于49不是偶數(shù)，把91和49以大數(shù)減小數(shù)，并輾轉相減， 即：914942 49427 42735 35728 28721 21714 1477 所以，91與49的最大公約數(shù)是7。,更相減損術,練習1 用更相減損術求98與63的最大公約數(shù).,解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減，,即：986335; 633528; 35287; 28721; 21714; 1477.,所以，98與63的最大公約數(shù)是7。,練習2：用更相減損術求兩個正數(shù)84與72

4、的最大公約數(shù)。,(12),我國魏晉時期的數(shù)學家劉徽，他在注九章算術中采用正多邊形面積逐漸逼近圓面積的算法計算圓周率，用劉徽自己的原話就是：“割之彌細，所失彌少；割之又割，以至于不可割，則與圓合體而無所失矣” ，這段注文充分說明了劉徽對極限概念. 他的思想后來又得到祖沖之的推進和發(fā)展，計算出圓周率的近似值在世界上很長時間里處于領先地位。,2.劉徽割圓術,2.劉徽割圓術,一、劉徽首先指出利用=3這一數(shù)值算得的結果不是圓面積，而是圓內接正十二邊形的面積，這個結果比的真值少.,二、他由圓內接正六邊形算起，逐漸把邊數(shù)加倍，逐個算出正12邊形、正24邊形、正48邊形、正96邊形的面積，這些面積會逐漸地接近

5、圓面積.最后求出圓面積的近似值。,三、已知正6邊形一邊（恰與半徑等長)即求得正12邊形邊長，.由正12邊形求正24邊形一邊之長時，劉徽反復地應用到勾股定理（或稱商高、勾股定理），如圖：,割圓術。不斷地利用勾股定理，來計算正N邊形的邊長。,劉徽先將直徑為2的圓分割為6等分，再分割成12等分，24等分，.，這樣繼續(xù)下去，并利用勾股定理計算其面積，從而求出圓周率的近似值，他一直計算到圓內接正192邊形的面積。因為圓的半徑為1，所以隨著邊數(shù)的增大，面積不斷趨近于圓周率，這樣不斷計算下去，就可以得到越來越精密的圓周率近似值。,祖沖之,祖沖之: （公元429-500年）是我國南北朝時期，河北省淶源縣人他從

6、小就閱讀了許多天文、數(shù)學方面的書籍，勤奮好學，刻苦實踐，終于使他成為我國古代杰出的數(shù)學家、天文學家,圓周率是指平面上圓的周長與直徑之比。早在一千四百多年以前，我國古代著名的數(shù)學家祖沖之，就精密地計算出圓的周長是它直徑的3.1415926-3.1415927倍之間。這是當時世界上算得最精確的數(shù)值-圓周率。,“圓周率”是說一個圓的周長同它的直徑有一個固定的比例。我們的祖先很早就有“徑一周三”的說法，就是說，假如一個圓的直徑是1尺，那它的周長就是3尺。后來，人們發(fā)現(xiàn)這個說法并不準確。東漢的大科學家張衡認為應該是3.162。三國到西晉時期的數(shù)學家劉徽經(jīng)過計算，求出了3. 14159的圓周率，這在當時是

7、最先進的，但是劉徽只算到這里就沒有繼續(xù)算。祖沖之打算采用劉徽“割圓術”（在圓內做正6邊形，6邊形的周長剛好是直徑的3倍，然后再做12邊形、24邊形邊數(shù)越多，它的周長就和圓的周長越接近）的方法算下去。 在當時的情況下，不但沒有計算機，也沒有筆算，只能用長4寸，方3寸的小竹棍來計算。工作是艱巨的，這時祖沖之的兒子也能幫助他了。 父子倆算了一天又一天，眼睛熬紅了，人也漸漸瘦了下來，可大圓里的邊形卻越畫越多，3072邊、6144邊邊數(shù)越多，邊長越短。父子倆蹲在地上，一個認真地畫，一個細心地算，誰也不敢走神。最后，他們在那個大圓里畫出了24576邊形，并計算出它的周長是3.1415926。 倆人看看擺在

8、地上密密麻麻的小木棍，再看看畫在地上的大圓里的圖形，高興地笑了。 后來，祖沖之推算出，49152邊形的周長不會超過3.1415927。所以，他得出結論，圓周率是在3.1415926和3.1415927這兩個數(shù)之間。 祖沖之是世界上第一個計算圓周率精確到小數(shù)點后7位的人，比歐洲人早了1000多年，這是我國古代一項非常了不起的貢獻！,祖沖之計算得出的密率分數(shù)近似值355/113 ，外國數(shù)學家獲得同樣結果，已是一千多年以后的事了為了紀念祖沖之的杰出貢獻，有些外國數(shù)學史家建議把叫做祖率,祖沖之在天文歷法方面的成就，大都包含在他所編制的大明歷及為大明歷所寫的駁議中。,秦九韶 （公元1202-1261年）

9、南宋，數(shù)學家。他在1247年（淳佑七年）著成數(shù)書九章十八卷全書共81道題，分為九大類：大衍類、天時類、田域類、測望類、賦役類、錢谷類、營建類、軍旅類、市易類。這是一部劃時代的巨著，它總結了前人在開方中所使用的列籌方法，將其整齊而有系統(tǒng)地應用到高次方程的有理或無理根的求解上去，其中對大衍求一術一次同余組解法）和正負開方術高次方程的數(shù)值解法）等有十分深入的研究。其中的“大衍求一術”一次同余組解法），在世界數(shù)學史上占有崇高的地位。,3. 秦九韶算法,秦九韶算法,設計求多項式f(x)=2x55x44x3+3x26x+7當x=5時的值的算法，并寫出程序。,一般的解決方案,x=5; f=2 * x5 5

10、* x4 4 * x3 + 3 * x2 6 * x + 7; f,上述算法一共做了解15次乘法運算，5次加法運算. 優(yōu)點是簡單，易懂; 缺點是不通用，不能解決任意多項式的求值問題，而且計算效率不高。,有沒有更高效的算法？,用提取公因式的方法多項式變形為,f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x+7 =(2x5)x4)x+3)x6)x+7,這樣共作了5次加法，5次乘法.,第二種做法與第一種做法相比,乘法的運算次數(shù)減少了,因而能提高運算效率.而且對于計算機來說,做一次乘法所需的運算時間比做一次加法要長得多,因此第二種

11、做法能更快地得到結果.,求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.,解法一:首先將原多項式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677,所以,當x=5時,多項式的值是2677.,然后由內向外逐層計算一次多項式的值,即,這種求多項式值的方法就叫秦九韶算法.,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.,我們可以改寫成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多項式的值時,首先計算最內層括號內一次多項式的值,即,v1=v0 x+an-1,然后由內向外逐層計算一次多項式的值,即,一般地,對于一個n次多項式,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,這樣,求n次多項式f(x)的值就轉化為求n個一次多項式的值.這種算法稱為秦九韶算法.,v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,觀察上述秦九韶算法中的n個一次式,可見vk的計算要用到vk-1的值.,若令v0=an,得,這