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