5/51.3中國古代數學中的算法案例學習目標1.了解中國古代數學中求兩個正整數最大公約數的算法以及割圓術的算法；2.通過對“更相減損之術”及“割圓術”的學習，更好的理解將要解決的問題“算法化”的思維方法，并注意理解推導“割圓術”的操作步驟。學習重點1.改變解決問題的思路，要將抽象的數學思維轉變?yōu)榫唧w的步驟化的思維方法，提高邏輯思維能力；2.學會借助實例分析，探究數學問題。學習過程一、學習引入同學們是否知道，我們在小學、初中學到的算術、代數，從記數到多元一次聯(lián)立方程組以及方程的求根方法，都是我國古代數學家最先創(chuàng)造的，有的比其他國家早幾百年甚至上千年，我們人民在長期的生活、生產和勞動過程中，創(chuàng)造了整數、分數、小數、正負數及其計算，以及無限逼近任意實數的方法，在代數學、幾何學方面，我國在宋、元之前也都處于世界前列，更為重要的是我國古代數學的發(fā)展有著自己鮮明的特色，走著與西方完全不同的道路，在今天看來這條道路仍然有很大的優(yōu)越性。這條道路的一個重要特色就是“寓理于算”，也就是本節(jié)中所講的要把解決問題“算法化”。下面我們舉一些我國古代數學中算法的例子，讓同學們更進一步體會“算法”的概念，看一看中國古代數學家的偉大成就和顯著特色。下面就中國古代的數學成就，結合算法的知識，主要了解一下下面三個方面的內容：求兩個正整數最大公約數的算法、割圓術和秦九韶算法。二、新知講授（一）求兩個正整數最大公約數的算法：更相減損之術我們知道，如果整數a能被整數b整除，則b稱為a的一個約數，一個整數可能有好幾個約數。例如，12能被1,2,3,4,6,12整除，這6個數都是12的約數。16的有1,2,4,8,16這5個約數。我們看到2和4，既是12的約數，又是16的約數，2和4叫做12和16的公約數，公約數2和4中，4最大，4稱作12和16的最大公約數。如何找到一種算法，對任意兩個正整數都能求出它們的最大公約數呢？下面給出我國古代數學家的一個算法，這個算法被稱做“更相減損之術”。我們以求16,12這兩個數的最大公約數為例加以說明。用兩個數中較大的數減去較小的數，即16-12=4，用差數4和最小的數12構成新的一對數，對這一對數再用大數減小數，以同樣的操作一直做下去，知道產生一對相等的數，這個數就是最大公約數。整個操作如下：4是12和16的最大公約數。這種算法的道理何在？不難看出，對任意兩個數，每次操作后所得的兩個數與前兩數具有相同的最大公約數，而兩數的值逐漸減少，經過有限步地操作后，總能得到相等的兩個數，即求得兩數的最大公約數。例1求78和36的最大公約數。解：這種算法，只做簡單的減法，操作方便、易懂，也完全符合算法的要求，它完全是機械的運算，據此很容易編出程序，在計算機上運算，把這個算法與我們下面探索與研究中介紹的歐幾里德算法比較，看看這個算法的優(yōu)越性。下面是我們用Scilab編出的程序，供大家參考。實際上，你可用你在信息技術課上學到的任一種程序設計語言編出程序，從中體會一下這個算法的優(yōu)越性。為了方便敘述，我們稱這種算法為“等值算法”用等值算法求最大公約數的程序：a=input("pleasegivethefirstnumber");a=input("pleasegivethefirstnumber");b=input("pleasegivethesecondnumber");whilea<>bifa>ba=a-belseb=b-aendendprint(%io2(2),a,b)（二）割圓術我國魏晉時期的數學家劉徽，他在注《九章算術》中采用正多邊形面積逐漸逼近圓面積的算法計算圓周率，用劉徽自己的原話就是“割之彌細，所失彌少，割之又割，以至于不可割，則與圓合體而無所失矣?！彼乃枷牒髞碛值玫阶鏇_之的推進和發(fā)展，計算出圓周率的近似值在世界上很長時間里處于領先地位。劉徽從圓內接正六邊形開始，讓邊數逐次加倍，逐個算出這些圓內接正多邊形的面積，從而得到一系列逐漸遞增的數值，來一步一步地逼近圓面積，最后求出圓周率的近似值?？梢韵胂笤诋敃r需要付出多么艱辛的勞動，現(xiàn)在讓我們用劉徽的思想，使用計算機求圓周率的近似值，計算機最大的特點是運算速度快，只要我們將運算規(guī)律告訴計算機，計算機會迅速得到所求的答案。我們先對單位圓內接正六邊形、正十二邊形、正二十四邊形……的面積之間的關系進行分析，找出它們之間的遞增規(guī)律。例2假設圓的半徑為1，面積為S，圓內接正n邊形面積為，邊長為，邊心距為，根據勾股定理，。正2n邊形的面積為正n邊形的面積再加上n個等腰三角形的面積和，即①正2n邊形的邊長為。劉徽割圓術還注意到，如果在內接n邊形的每一邊上，做一高為CD的矩形，就可得到這樣我們就不僅可計算出圓周率的不足近似值，還可計算出圓周率的過剩近似值。正六邊形的面積開始計算，即n=6，則正六邊形的面積。用上面的公式①重復計算，就可得到正十二邊形、正二十四邊形……的面積。因為圓的半徑為1，所以隨著n的增大，的值不斷趨近于圓周率，這樣不斷計算下去，就可以得到越來越精密的圓周率近似值。下面我們根據劉徽割圓術的算法思想，用Scilsb語言寫出求的不足近似值程序：（三）秦九韶算法例3已知一個一元n次多項式函數，當，我們可按順序一項一項地計算，然后相加，求得。下面看看我們宋代（約13世紀）大數學家秦九韶是如何計算多項式函數值的。讓我們以5次多項式函數為例加以說明。設首先，我們把這個多項式一步一步的進行改寫：上面的分層計算，只用了小括號，計算時，首先計算最內層的括號，然后由內向外逐層計算，知道最外層的一個括號，然后加上常數項。這種算法與直接算法比較，有什么有什么優(yōu)越性呢？首先，這種算法一共做了5次乘法，5次加法，與直接計算相比較大大節(jié)省了乘法的次數，是計算量減少，并且邏輯結構簡單。對任意一元n次多項式，類似的敘述如下：上面的方法，現(xiàn)在大家稱它為秦九韶方法。直到今天，這種算法仍是世界上多項式求值的最先進的算法。這種方法的計算量僅為：乘法n次，加法n次。我們看看其他算法的計算量。用直接求和法，直接計算多項式各項的值，然后把他們相加?？芍朔ǖ拇螖禐?，加法次數為n。逐項求和在直接求和法的基礎上做了改進，先把多項式寫成的形式，這樣多項式的每一含x的冪的項都是與的乘積（k=1,2,3，……，n），在計算項時把的值保存在變量c中，求項時只須計算，同時把的值存入c中，繼續(xù)下一項的運算，然后把這n+1項的值相加。容易看出逐項求和法所用乘法的次數為2n-