1、算法案例（第二課時(shí)）1秦九韶,南宋，數(shù)學(xué)家。他在1247年（淳佑七年）著成數(shù)書(shū)九章十八卷全書(shū)共81道題，分為九大類：大衍類、天時(shí)類、田域類、測(cè)望類、賦役類、錢(qián)谷類、營(yíng)建類、軍旅類、市易類。這是一部劃時(shí)代的巨著，它總結(jié)了前人在開(kāi)方中所使用的列籌方法，將其整齊而有系統(tǒng)地應(yīng)用到高次方程的有理或無(wú)理根的求解上去，其中對(duì)大衍求一術(shù)一次同余組解法）和正負(fù)開(kāi)方術(shù)高次方程的數(shù)值解法）等有十分深入的研究。其中的”大衍求一術(shù)”一次同余組解法），在世界數(shù)學(xué)史上占有崇高的地位。在古代孫子算經(jīng)中載有”物不知數(shù)”這個(gè)問(wèn)題，舉例說(shuō)明：有一數(shù)，三三數(shù)之余二，五五數(shù)之余二，七七數(shù)之余二，問(wèn)此數(shù)為何？這一類問(wèn)題的解法可以推廣成解

2、一次同余式組的一般方法奏九韶給出了理論上的證明，并將它定名為”大衍求一術(shù)”。秦 九 韶2計(jì)算多項(xiàng)式（） =當(dāng)x = 5的值算法1：因?yàn)椋ǎ?=所以（5）=55555=3125625125255= 3906算法2：（5）=55555=5（5555） =5（5（555 ） ） =5（5（ 5 （55 ） ） ） =5（5（ 5 （5 （5 ） ） ） ） 分析：兩種算法中各用了幾次乘法運(yùn)算？和幾次加法運(yùn)算？3計(jì)算任意一個(gè)四次多項(xiàng)式當(dāng) x = 5 時(shí)的值：4計(jì)算任意一個(gè)四次多項(xiàng)式當(dāng) x = 5 時(shí)的值：然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即你從中看到了怎樣的規(guī)律？怎么用程序框圖來(lái)描述呢？5數(shù)書(shū)九章

3、秦九韶算法設(shè)是一個(gè)n次的多項(xiàng)式對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫(xiě)：思考：當(dāng)知道了x的值后該如何求多項(xiàng)式的值？這是怎樣的一種改寫(xiě)方式？最后的結(jié)果是什么？6要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即最后的一項(xiàng)是什么？這種將求一個(gè)n次多項(xiàng)式f（x）的值轉(zhuǎn)化成求n個(gè)一次多項(xiàng)式的值的方法，稱為秦九韶算法。思考：在求多項(xiàng)式的值上，這是怎樣的一個(gè)轉(zhuǎn)化？7例2 已知一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。解：將多項(xiàng)式變形：按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：所以，當(dāng)x = 5時(shí)，多項(xiàng)式的值等于17255.2你從中看到了怎樣的規(guī)律

4、？怎么用程序框圖來(lái)描述呢？8開(kāi)始輸入f (x)的系數(shù)：a0、a1、a2、a3、a4、a5輸入x0n=0v=a5v= vx0+a5-nn=n+1n 5?輸出v結(jié)束否是注意：要想使用檢驗(yàn)功能，請(qǐng)使用前，先要減低宏的安全限制9排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6方法1：S1：比較第2個(gè)數(shù)與第1個(gè)數(shù)的大小，并排序得3，8S2：將第3個(gè)數(shù)與S1中的數(shù)比較，插入適當(dāng)?shù)奈恢?，得?，3，8S3：將第4個(gè)數(shù)與S2中的數(shù)比較，并插入適當(dāng)?shù)奈恢?，如此繼續(xù)下去，直到把最后一個(gè)數(shù)插入到上一步已排好的數(shù)列的合適位置為止，得到：2 ，3， 5， 82 ，3， 5， 8 ，92 ，3， 5， 6

5、， 8 ， 9S4：S5：10排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6方法1：過(guò)程演示832596開(kāi)始排第1次排第2次排第3次排第4次832596382596238596235896235896排第5次235689直接排序法11排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6方法2：S1：用第1個(gè)數(shù)與第2個(gè)數(shù)比較，若前者小則兩數(shù)不變，否則，交換這兩個(gè)數(shù)的位置。S2：按這樣的原則，比較第2個(gè)數(shù)和第3個(gè)數(shù)，前者小則兩數(shù)不變，否則，交換這兩個(gè)數(shù)的位置直到比完最后兩個(gè)數(shù)。（稱為“一趟”）S3：如果前一趟的比較中交換的次數(shù)為0，說(shuō)明排序已完成，否則回到S2。根據(jù)題意，

6、一趟后的結(jié)果是什么？為什么說(shuō)前一趟的比較中交換為0次時(shí)，排序完成？3，2，5， 8， 6 ， 912排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái)第1趟832596382596328596325896325896325869該趟中交換的次數(shù)為_(kāi)次413排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái)第2趟325869235869235869235869235689235689該趟中交換的次數(shù)為_(kāi)次214排序的算法將下面數(shù)字按由小到大的順序排列8，3，2，5，9，6請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái)第3趟235689235689235

7、689235689235689235689該趟中交換的次數(shù)為_(kāi)次，0所以排序的結(jié)果為：2，3，5，6，8，915 秦九韶的數(shù)學(xué)成就 宋理宗淳祐四年（1244年），十一月，秦九韶解官建康通判，回湖州丁母憂，一邊為母親守靈，一邊把自己幾十年勤奮學(xué)習(xí)、苦心鉆研、實(shí)踐、總結(jié)的數(shù)學(xué)成就結(jié)晶，精選出來(lái)的較有代表性的81個(gè)問(wèn)題，分為9類，每類9題，編輯成18卷，淳祐七年，世界最高水平的數(shù)學(xué)名著數(shù)書(shū)九章成書(shū)。 秦九韶在數(shù)學(xué)上的主要成就是系統(tǒng)地總結(jié)和發(fā)展了高次方程數(shù)值解法和一次同余組解法，提出了相當(dāng)完備的“正負(fù)開(kāi)方術(shù)”和“大衍求一術(shù)”，達(dá)到了當(dāng)時(shí)世界數(shù)學(xué)的最高水平 秦九韶在前人工作的基礎(chǔ)上，提出一套完整的利用隨

8、乘隨加逐步求出高次方程正根的程序，亦稱“正負(fù)開(kāi)方術(shù)”，現(xiàn)稱秦九韶法 這也是“增乘開(kāi)方法”的主要特點(diǎn)。有人說(shuō)，計(jì)算機(jī)發(fā)明以后，解方程變得有趣了確實(shí)是這樣，秦九韶的高次方程數(shù)值解法，可以毫無(wú)困難地轉(zhuǎn)化為計(jì)算機(jī)程序。在數(shù)書(shū)九章中，秦九韶列舉了20多個(gè)解方程問(wèn)題，次數(shù)最高達(dá)10次除一般方法外，還討論了“投胎”、“換骨”、“玲瓏”、“同體連枝”等特 殊情形，并將其廣泛應(yīng)用于面積、體積、測(cè)量等方面的實(shí)際問(wèn)題在西方，關(guān)于高次方程數(shù)值解法的探討，經(jīng)歷了漫長(zhǎng)的歷史過(guò)程，直到1840年，意大利數(shù)學(xué)家P魯菲尼(Ruffini，1765-1822)才創(chuàng)立了一種逐次近似法解決數(shù)字高次方程無(wú)理數(shù)根的近似值問(wèn)題，而1819

9、年英國(guó)數(shù)學(xué)家WG霍納(Horner，17861837)在英國(guó)皇家學(xué)會(huì)發(fā)表的論文“用連續(xù)逼近法解任何次數(shù)字方程的新方法”中，才提出與增乘開(kāi)方法演算步驟相同的算法，后被稱為“霍納法”秦九韶的成就要比魯菲尼和霍納早五六百年。 秦九韶對(duì)于一次同余組解法的理論概括，是他在數(shù)學(xué)史上的另一杰出貢獻(xiàn)中算家對(duì)于一次同余式問(wèn)題解法的研究是適應(yīng)天文學(xué)家推算上元積年的需要而產(chǎn)生的最早見(jiàn)于記載的一次同余問(wèn)題是孫子算經(jīng)中的“物不知數(shù)問(wèn)題”(亦稱“孫子問(wèn)題”)：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾有何？”這相當(dāng)于求解一次同余組。 秦九韶的大衍求一術(shù)與他的高次方程數(shù)值解法一樣，簡(jiǎn)潔、明確、帶有很

10、強(qiáng)的機(jī)械性，其程序亦可毫無(wú)因難地轉(zhuǎn)化為算法語(yǔ)言，用計(jì)算機(jī)來(lái)實(shí)現(xiàn)在數(shù)書(shū)九章中，秦九韶通過(guò)大量例題，如“古歷會(huì)積”、“治歷演紀(jì)”“積尺尋源”、“推計(jì)土功”、“程行計(jì)地”等等，展示了大衍求一術(shù)在解決歷法、工程、賦役和軍旅等實(shí)際問(wèn)題中的廣泛應(yīng)用由于在許多問(wèn)題中，模數(shù)Ai并非兩兩互素，而中國(guó)傳統(tǒng)數(shù)學(xué)沒(méi)有素?cái)?shù)概念，所以將模數(shù)化為兩兩互素是相當(dāng)困難的問(wèn)題秦九韶所設(shè)計(jì)的將模數(shù)比為兩兩互素的算法，盡管還不完善，但仍比較成功地解決了這一難題，有人稱之為“沒(méi)有素?cái)?shù)的素?cái)?shù)論”。綜觀他在求解一次同余組問(wèn)題的各項(xiàng)成就，正如中科院研究員李文林、袁向東所說(shuō)：“所有這些系統(tǒng)的理論，周密的考慮，即使以今天的眼光看來(lái)也很不簡(jiǎn)單，充

11、分顯示了秦九韶高超的數(shù)學(xué)水平和計(jì)算技巧。”在西方，最早接觸一次同余式的是意大利數(shù)學(xué)家L斐波那契(Fibonacci，約1170-1250)他在算盤(pán)書(shū)中給出了兩個(gè)一次同余問(wèn)題，但沒(méi)有一般算法直到1819世紀(jì)，L歐拉(Euler，1743)、GF高斯(Gauss，1801)才對(duì)一次同余組進(jìn)行深入研究，重新獲得與中國(guó)剩余定理相同的定理，并對(duì)模數(shù)兩兩互素的情形給出了嚴(yán)格證明。1852年，英國(guó)傳教士、漢學(xué)家偉烈亞力(AWylie，1815-1887)發(fā)表中國(guó)數(shù)學(xué)科學(xué)札記(Jottings on the science of Chinese arithmetic)，其中談到了大衍求一術(shù)從1856年到187

12、6年，德國(guó)人L馬蒂生(Matthiessen，1830-1906)等西方學(xué)者又多次指出大衍求一術(shù)原理與高斯方法的一致性，從而更加引起了歐洲學(xué)者的矚目德國(guó)著名數(shù)學(xué)史家M康托爾(Cantor，1829-1920)高度評(píng)價(jià)了大衍求一術(shù)，他稱贊發(fā)現(xiàn)這一算法的中國(guó)數(shù)學(xué)家是“最幸運(yùn)的天才”。從此，中國(guó)古代數(shù)學(xué)的這一創(chuàng)造逐漸受到世界學(xué)者的矚目，并在西方數(shù)學(xué)史著作中正式被稱為“中國(guó)剩余定理”。數(shù)書(shū)九章中，除了前面提到的大衍求一術(shù)和正負(fù)開(kāi)方術(shù)兩項(xiàng)重要成就外，還記載了不少其他方面的成就例如，他改進(jìn)了線性方程組的解法，普遍應(yīng)用互乘相消法代替?zhèn)鹘y(tǒng)的直除法，已同今天所用的方法完全一致；在開(kāi)方中，他發(fā)展了劉徽開(kāi)方不盡求微數(shù)的