1、3 59 15 問題問題1 1 ：在小學，我們已經(jīng)學過求最大公約數(shù)：在小學，我們已經(jīng)學過求最大公約數(shù)的知識，你能求出的知識，你能求出1818與與3030的最大公約數(shù)嗎？的最大公約數(shù)嗎？18 30231818和和3030的最大公約的最大公約數(shù)是數(shù)是2 23=6.3=6.先用兩個數(shù)公有的先用兩個數(shù)公有的質(zhì)因數(shù)質(zhì)因數(shù)連續(xù)去除連續(xù)去除,一直除到所得一直除到所得的商是互質(zhì)數(shù)為止的商是互質(zhì)數(shù)為止,然后然后把所有的除數(shù)連乘起來把所有的除數(shù)連乘起來. 問題問題2 2:我們都是利用找公約數(shù)的方法來求最大我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察公約數(shù)，如果公約數(shù)比較大而且根據(jù)我

2、們的觀察又不能得到一些公約數(shù)，我們又應該怎樣求它們又不能得到一些公約數(shù)，我們又應該怎樣求它們的最大公約數(shù)？比如求的最大公約數(shù)？比如求82518251與與61056105的最大公約數(shù)的最大公約數(shù)? ? 1、求兩個正整數(shù)的最大公約數(shù)的算法、求兩個正整數(shù)的最大公約數(shù)的算法我國早期也有解決求最大公約數(shù)問題的算法，我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術。就是更相減損術。更相減損術求最大公約數(shù)的步驟如下：更相減損術求最大公約數(shù)的步驟如下：可半者可半者半之，不可半者，副置分母半之，不可半者，副置分母子之數(shù)，以少減多，更相子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。減損，求其等也，以等數(shù)

3、約之。翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用們是否都是偶數(shù)。若是，用2 2約簡；若不是，執(zhí)行第二步。約簡；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。公約數(shù)。練習練習1 1 用更相減損術求用更相減損術求9898與與6363的最大公約數(shù)的最大公約數(shù). .解

4、：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，減小數(shù)，并輾轉(zhuǎn)相減， 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。練習練習2 2：用更相減損術求兩個正數(shù)：用更相減損術求兩個正數(shù)8484與與7272的最大的最大公約數(shù)。公約數(shù)。 (12)(12) 我國魏晉時期的數(shù)學家劉徽，他在注我國魏晉時期的數(shù)學家劉徽，他在注九章算術九章算術中采用正多邊形面積逐漸逼近中采用正多邊形面積逐漸逼近圓面積的算法計算圓周率圓面積的算法計算圓周率，用劉徽自己的

5、，用劉徽自己的原話就是原話就是：“割之彌細，所失彌少；割之又割之彌細，所失彌少；割之又割，以至于不可割，則與圓合體而無所失割，以至于不可割，則與圓合體而無所失矣矣” ，這段注文充分說明了劉徽對極限概念，這段注文充分說明了劉徽對極限概念. . 他的思想后來又得到祖沖之的推進和發(fā)展，他的思想后來又得到祖沖之的推進和發(fā)展，計算出圓周率的近似值在世界上很長時間里計算出圓周率的近似值在世界上很長時間里處于領先地位。處于領先地位。2.劉徽割圓術劉徽割圓術2.劉徽割圓術劉徽割圓術一、劉徽首先指出利用一、劉徽首先指出利用=3=3這一數(shù)值算得的這一數(shù)值算得的結(jié)果不是圓面積，而是圓內(nèi)接正十二邊形的結(jié)果不是圓面積，

6、而是圓內(nèi)接正十二邊形的面積，這個結(jié)果比面積，這個結(jié)果比的真值少的真值少. .二、他由圓內(nèi)接正六邊形算起，逐漸把邊數(shù)二、他由圓內(nèi)接正六邊形算起，逐漸把邊數(shù)加倍，逐個算出正加倍，逐個算出正1212邊形、正邊形、正2424邊形、正邊形、正4848邊形、正邊形、正9696邊形邊形的面積，這些面積會逐的面積，這些面積會逐漸地接近圓面積漸地接近圓面積. .最后求出圓面積的近似值。最后求出圓面積的近似值。三、已知正三、已知正6邊形一邊（恰與半徑等長邊形一邊（恰與半徑等長)即求得正即求得正12邊形邊形邊長，邊長，.由正由正12邊形求正邊形求正24邊形一邊之長時，劉徽反邊形一邊之長時，劉徽反復地應用到勾股定理（

7、或稱商高、勾股定理），如圖：復地應用到勾股定理（或稱商高、勾股定理），如圖：割圓術。不斷地利用勾股定理，來計算割圓術。不斷地利用勾股定理，來計算正正N邊形的邊長。邊形的邊長。 劉徽先將直徑為劉徽先將直徑為2 2的圓分割為的圓分割為6 6等分，等分，再分割成再分割成1212等分，等分，2424等分，等分，.，這樣，這樣繼續(xù)下去，并利用勾股定理計算其面積，繼續(xù)下去，并利用勾股定理計算其面積，從而求出圓周率的近似值，他一直計算從而求出圓周率的近似值，他一直計算到圓內(nèi)接正到圓內(nèi)接正192192邊形的面積。因為圓的邊形的面積。因為圓的半徑為半徑為1 1，所以隨著邊數(shù)的增大，面積，所以隨著邊數(shù)的增大，面積

8、不斷趨近于圓周率，這樣不斷計算下去，不斷趨近于圓周率，這樣不斷計算下去，就可以得到越來越精密的圓周率近似值。就可以得到越來越精密的圓周率近似值。祖沖之 祖沖之祖沖之:（公元（公元429-500年）是我國南北朝時年）是我國南北朝時期，河北省淶源縣人他從小就閱讀期，河北省淶源縣人他從小就閱讀了許多天文、數(shù)學方面的書籍，勤奮了許多天文、數(shù)學方面的書籍，勤奮好學，刻苦實踐，終于使他成為我國好學，刻苦實踐，終于使他成為我國古代杰出的數(shù)學家、天文學家古代杰出的數(shù)學家、天文學家 圓周率是指圓周率是指平面平面上圓的上圓的周長周長與直徑之比。早在一千四百多年與直徑之比。早在一千四百多年以前，我國古代著名的數(shù)學家

9、祖以前，我國古代著名的數(shù)學家祖沖之，就精密地計算出圓的周長沖之，就精密地計算出圓的周長是它直徑的是它直徑的3.1415926-3.1415926-3.14159273.1415927倍之間。這是當時世界倍之間。這是當時世界上算得最精確的數(shù)值上算得最精確的數(shù)值-圓周率。圓周率。 “圓周率圓周率”是說一個圓的周長同它的直徑有一個固定的比例。我們是說一個圓的周長同它的直徑有一個固定的比例。我們的祖先很早就有的祖先很早就有“徑一周三徑一周三”的說法，就是說，假如一個圓的直徑是的說法，就是說，假如一個圓的直徑是1尺，那它的周長就是尺，那它的周長就是3尺。后來，人們發(fā)現(xiàn)這個說法并不準確。東漢的尺。后來，人

10、們發(fā)現(xiàn)這個說法并不準確。東漢的大科學家張衡認為應該是大科學家張衡認為應該是3.162。三國到西晉時期的數(shù)學家劉徽經(jīng)過計算，。三國到西晉時期的數(shù)學家劉徽經(jīng)過計算，求出了求出了3. 14159的圓周率，這在當時是最先進的，但是劉徽只算到這里的圓周率，這在當時是最先進的，但是劉徽只算到這里就沒有繼續(xù)算。祖沖之打算采用劉徽就沒有繼續(xù)算。祖沖之打算采用劉徽“割圓術割圓術”（在圓內(nèi)做正（在圓內(nèi)做正6邊形，邊形，6邊形的周長剛好是直徑的邊形的周長剛好是直徑的3倍，然后再做倍，然后再做12邊形、邊形、24邊形邊形邊數(shù)越多，邊數(shù)越多，它的周長就和圓的周長越接近）的方法算下去。它的周長就和圓的周長越接近）的方法算

11、下去。 在當時的情況下，不但沒有計算機，也沒有筆算，只能用長在當時的情況下，不但沒有計算機，也沒有筆算，只能用長4寸，寸，方方3寸的小竹棍來計算。工作是艱巨的，這時祖沖之的兒子也能幫助他寸的小竹棍來計算。工作是艱巨的，這時祖沖之的兒子也能幫助他了。了。 父子倆算了一天又一天，眼睛熬紅了，人也漸漸瘦了下來，可大圓父子倆算了一天又一天，眼睛熬紅了，人也漸漸瘦了下來，可大圓里的邊形卻越畫越多，里的邊形卻越畫越多，3072邊、邊、6144邊邊邊數(shù)越多，邊長越短。父子邊數(shù)越多，邊長越短。父子倆蹲在地上，一個認真地畫，一個細心地算，誰也不敢走神。最后，他倆蹲在地上，一個認真地畫，一個細心地算，誰也不敢走神

12、。最后，他們在那個大圓里畫出了們在那個大圓里畫出了24576邊形，并計算出它的周長是邊形，并計算出它的周長是3.1415926。 倆人看看擺在地上密密麻麻的小木棍，再看看畫在地上的大圓里的倆人看看擺在地上密密麻麻的小木棍，再看看畫在地上的大圓里的圖形，高興地笑了。圖形，高興地笑了。 后來，祖沖之推算出，后來，祖沖之推算出，49152邊形的周長不會超過邊形的周長不會超過3.1415927。所。所以，他得出結(jié)論，圓周率是在以，他得出結(jié)論，圓周率是在3.1415926和和3.1415927這兩個數(shù)之間。這兩個數(shù)之間。 祖沖之是世界上第一個計算圓周率精確到小數(shù)點后祖沖之是世界上第一個計算圓周率精確到小

13、數(shù)點后7位的人，比歐位的人，比歐洲人早了洲人早了1000多年，這是我國古代一項非常了不起的貢獻！多年，這是我國古代一項非常了不起的貢獻！ 祖沖之計算得出的密率分數(shù)近似值355/113 ，外國數(shù)學家獲得同樣結(jié)果，已是一千多年以后的事了為了紀念祖沖之的杰出貢獻，有些外國數(shù)學史家建議把叫做祖率 祖沖之在天文歷法方面的成就，祖沖之在天文歷法方面的成就，大都包含在他所編制的大都包含在他所編制的大明歷大明歷及為及為大明歷大明歷所寫的所寫的駁議駁議中。中。 秦九韶算法秦九韶算法 設計求多項式設計求多項式f(x)=2x55x44x3+3x26x+7當當x=5時的值的算法，并寫出程序。時的值的算法，并寫出程序。

14、 一般的解決方案一般的解決方案 x=5;f=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7;f 上述算法一共做了解上述算法一共做了解15次乘法運算次乘法運算，5次加法運算次加法運算. 優(yōu)點是簡單，易懂優(yōu)點是簡單，易懂; 缺點是不通用，不能解決任意多項式缺點是不通用，不能解決任意多項式的求值問題，而且計算效率不高。的求值問題，而且計算效率不高。有沒有更高效的算法？有沒有更高效的算法？ 用提取公因式的方法多項式變形為用提取公因式的方法多項式變形為 f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x

15、+7 =(2x5)x4)x+3)x6)x+7這樣共作了這樣共作了5次加法，次加法，5次乘法次乘法.第二種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運乘法的運算次數(shù)減少了算次數(shù)減少了,因而能提高運算效率因而能提高運算效率.而且對于而且對于計算機來說計算機來說,做一次乘法所需的運算時間比做一做一次乘法所需的運算時間比做一次加法要長得多次加法要長得多,因此第二種做法能更快地得到因此第二種做法能更快地得到結(jié)果結(jié)果.求多項式求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當當x=5時的值時的值.解法一解法一:首先將原多項式改寫成如下形式首先將原多項式改寫成如下形式 : f(x)=

16、(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,當當x=5時時,多多項式的值是項式的值是2677.然后由內(nèi)向外逐層計算一次多項式的值然后由內(nèi)向外逐層計算一次多項式的值,即即這種求多項式值的方法就叫這種求多項式值的方法就叫秦九韶算法秦九韶算法.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式我們可以改寫成如下形式:f(x)=(anx+an-1)x+an-2)x+a

17、1)x+a0.求多項式的值時求多項式的值時,首先計算最內(nèi)層括號內(nèi)一首先計算最內(nèi)層括號內(nèi)一次多項式的值次多項式的值,即即 v1=v0 x+an-1,然后由內(nèi)向外逐層計算一次多項式的值然后由內(nèi)向外逐層計算一次多項式的值,即即一般地一般地,對于一個對于一個n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個個一次多項式的值一次多項式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的觀察上述秦九韶算法中的n個一次式個一次式,可見可見vk的計算要用到的計算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)這是一個在秦九韶算法中反復執(zhí)行的步這是一個在秦九韶算法中反復執(zhí)行的步驟驟,因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)因此可用循環(huán)結(jié)構(gòu)來實現(xiàn).點評點