算法案例秦九韶算法

1、1.3算法案例-秦九韶算法高二數(shù)學(xué)組 梅 杰一.教學(xué)目標(biāo)1.了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)提高計算效率的實質(zhì)；2.能利用秦九韶算法進(jìn)行一些多項式的計算，能用循環(huán)結(jié)構(gòu)表示算法步驟。二教學(xué)重難點1.理解秦九韶算法體現(xiàn)的思想；2.用循環(huán)結(jié)構(gòu)表示算法步驟。三.教學(xué)過程（一）創(chuàng)設(shè)情景，揭示課題問題1 ：請同學(xué)們設(shè)計一個算法，計算當(dāng)時的值。學(xué)生可能會提出兩種做法：做法一：把5代入多項式的每一項，計算每一項的值，然后相加；做法二：先計算x的冪，可以利用前面的計算結(jié)果，以減少計算量，即先計算x2,然后依次計算x2.x,( x2.x).x,( ( x2.x).x).x的值，再各項

2、相加。結(jié)合學(xué)生的做法，進(jìn)行比較點評：有哪些優(yōu)點？哪些不足？計算次數(shù)各是多少？有哪些計算種類？做法一有15次乘法運算，5次加法運算；做法二有9次乘法運算，5次加法運算對于計算機(jī)來說，做一次乘法運算所用時間要比做一次加法要長的多，所以算法好壞的一個重要標(biāo)志仍然是運算的次數(shù)問題2 ：上述問題1還有沒有更有效的算法呢？老師引導(dǎo)學(xué)生從因式分解的角度，將多項式變形為：思考：從內(nèi)到外，如果把每一個括號都看成一個常數(shù)，那么變形后的式子中有哪些“一次式”？x的系數(shù)依次是什么？師生一起列表表示出計算過程：原多項式x的系數(shù)423.5-2.61.7-0.8運算20110567.52824.514131+變形后x的系數(shù)

3、422113.5564.92826.214130.2*5思考：讓學(xué)生回顧整個計算過程，用此種方法一共進(jìn)行了多少次乘法、加法運算？點評：一共進(jìn)行了5次乘法，5次加法運算，相比較前兩種做法，此做法更快、更方便，而且在計算過程中，只與多項式的系數(shù)有關(guān)。這種算法就是“秦九韶算法”，在此可以介紹下秦九韶生平?！疽姼巾摗浚ǘ┭刑叫轮獑栴}1：怎樣用秦九韶算法求一般的多項式當(dāng)x=x0時的值？類似上述方法，將多項式變形為：由內(nèi)向外逐層計算一次多項式的值，把n次多項式的求值問題轉(zhuǎn)化為求n個一次多項式值的問題，即求：,.思考：秦九韶算法使用一般的多項式中運算的次數(shù)？運算種類？點評: 秦九韶算法使用一般的多項式的求

4、值問題.直接法乘法運算的次數(shù)最多可到達(dá),加法最多次.秦九韶算法通過轉(zhuǎn)化把乘法運算的次數(shù)減少到最多次,加法最多次.問題2：怎樣用程序語言來表示秦九韶算法呢？通過觀察上述秦九韶算法中的n個一次式，可見計算要用到的值，若令，我們可以得到下面的遞推公式：,（k=1,2,n）這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)構(gòu)來實現(xiàn)。師生一起分三步進(jìn)行： 自然語言寫算法：第一步,輸入多項式次數(shù),最高次項的系數(shù)和的值.第二步,；第三步,輸入次項的系數(shù)；第四步,；第五步,判斷是否大于等于,若是,則返回第三步;否則,輸出多項式的值.畫程序框圖（略）翻譯成程序語言INPUT “n=”;n INPUT “an=”

5、;a INPUT “x=”;x v=a i=n-1 WHILE i=0 PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1 WEND PRINT v END（三）例題講解例1.利用秦九韶算法計算當(dāng)時的值，并統(tǒng)計需要多少次乘法計算和多少次加法計算？例2利用秦九韶算法計算多項式當(dāng)時的值點評: 如果多項式函數(shù)中有缺項的畫,要以系數(shù)為的項補(bǔ)齊后再計算.例3 .某城市2001年末汽車保有量為萬輛,預(yù)計此后每年報廢上一年末汽車保有量的,并且每年新增汽車萬輛.設(shè)計算法,計算經(jīng)過多少年可使汽車保有量達(dá)到萬輛.將此算法用程序語言給出.解：設(shè),經(jīng)過幾年的汽車保有量為,則 上述各式充分

6、說明了秦九韶算法的優(yōu)點:可以通過遞推關(guān)系進(jìn)行迭代處理.程序為: C=0.94A=30n=0WHILE A40 A=A*C+3 n=n+1WENDPRINT nEND（四）課堂小結(jié)（五）布置作業(yè)秦九韶生平簡介 南宋大數(shù)學(xué)家秦九韶 秦九韶（公元12021261），字道古，安岳人。秦九韶與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。其父秦季棲，進(jìn)士出身，官至上部郎中、秘書少監(jiān)。秦九韶聰敏勤學(xué)。宋紹定四年（1231），秦九韶考中進(jìn)士，先后擔(dān)任縣尉、通判、參議官、州守、同農(nóng)、寺丞等職。先后在湖北、安徽、江蘇、浙江等地做官，1261年左右被貶至梅州（今廣東梅縣），不久死于任所。他在政務(wù)之余，對數(shù)學(xué)進(jìn)行虔心鉆研，

7、并廣泛搜集歷學(xué)、數(shù)學(xué)、星象、音律、營造等資料，進(jìn)行分析、研究。 宋淳祜四至七年（1244至1247），他在為母親守孝時，把長期積累的數(shù)學(xué)知識和研究所得加以編輯，寫成了聞名的巨著數(shù)學(xué)九章，并創(chuàng)造了“大衍求一術(shù)”。這 不僅在當(dāng)時處于世界領(lǐng)先地位，在近代數(shù)學(xué)和現(xiàn)代電子計算設(shè)計中，也起到了重要作用，被稱為“中國剩余定理”。他所論的“正負(fù)開方術(shù)”，被稱為“秦九韶程序”?，F(xiàn)在，世界各國從小學(xué)、中學(xué)到大學(xué)的數(shù)學(xué)課程，幾乎都接觸到他的定理、定律和解題原則。秦九韶在數(shù)學(xué)方面的研究成果，比英國數(shù)學(xué)家取得的成果要早800多年。安岳修建的秦九韶紀(jì)念館，恢宏壯觀，雄偉氣派。秦九韶的數(shù)學(xué)成就及對世界數(shù)學(xué)的貢獻(xiàn)主要表現(xiàn)在以

8、下方面：1、秦九韶的數(shù)書九章是一部劃時代的巨著 秦九韶潛心研究數(shù)學(xué)多年，在湖州守孝三年，所寫成的世界數(shù)學(xué)名著數(shù)學(xué)九章，癸辛雜識續(xù)集稱作數(shù)學(xué)大略，永樂大典稱作數(shù)學(xué)九章。全書九章十八卷，九章九類：“大衍類”、“天時類”、“田域類”、“測望類”、“賦役類”、“錢谷類”、“營建類”、“軍旅類”、“市物類”，每類9題（9問）共計81題（81問），該書內(nèi)容豐富至極，上至天文、星象、歷律、測候，下至河道、水利、建筑、運輸，各種幾何圖形和體積，錢谷、賦役、市場、牙厘的計算和互易。許多計算方法和經(jīng)驗常數(shù)直到現(xiàn)在仍有很高的參考價值和實踐意義，被譽(yù)為“算中寶典”。該書著述方式，大多由“問曰”、“答曰”、“術(shù)曰”、“

9、草曰”四部分組成：“問曰”，是從實際生活中提出問題；“答曰”，給出答案；“術(shù)曰”，闡述解題原理與步驟；“草曰”，給出詳細(xì)的解題過程。此書已為國內(nèi)外科學(xué)史界公認(rèn)的一部世界數(shù)學(xué)名著。此書不僅代表著當(dāng)時中國數(shù)學(xué)的先進(jìn)水平，也標(biāo)志著中世紀(jì)世界數(shù)學(xué)的最高水平。我國數(shù)學(xué)史家梁宗巨評價道：“秦九韶的數(shù)書九章（1247年）是一部劃時代的巨著，內(nèi)容豐富，精湛絕倫。特別是大衍求一術(shù)（不定方程的中國獨特解法）及高次代數(shù)方程的數(shù)值解法，在世界數(shù)學(xué)史上占有崇高的地位。那時歐洲漫長的黑夜猶未結(jié)束，中國人的創(chuàng)造卻像旭日一般在東方發(fā)出萬丈光芒?！?、秦九韶的“大衍求一術(shù)”，領(lǐng)先高斯554年，被康托爾稱為“最幸運的天才” 秦九

10、韶所發(fā)明的“大衍求一術(shù)”，即現(xiàn)代數(shù)論中一次同余式組解法，是中世紀(jì)世界數(shù)學(xué)的最高成就，比西方1801年著名數(shù)學(xué)家高斯（Gauss，17771855年）建立的同余理論早554年，被西方稱為“中國剩余定理”。秦九韶不僅為中國贏得無尚榮譽(yù)，也為世界數(shù)學(xué)作出了杰出貢獻(xiàn)。3、秦九韶的任意次方程的數(shù)值解領(lǐng)先霍納572年 秦九韶在數(shù)書九章中除“大衍求一術(shù)”外，還創(chuàng)擬了正負(fù)開方術(shù)，即任意高次方程的數(shù)值解法，也是中世紀(jì)世界數(shù)學(xué)的最高成就，秦九韶所發(fā)明的此項成果比1819年英國人霍納（WGHorner，17861837年）的同樣解法早572年。秦九韶的正負(fù)方術(shù)，列算式時，提出“商常為正，實常為負(fù)，從常為正，益常為負(fù)”的原則，純用代數(shù)加法，給出統(tǒng)一的運算規(guī)律，并且擴(kuò)充到任何高次方程中去。此外，秦九韶還改進(jìn)了一次方程組的解法，用互乘對減法消元，與現(xiàn)今的加減消元法完全一致；同時秦九韶又給出了籌算的草式，可使它擴(kuò)充到一般線性方程中的解法。在歐洲最早是1559年布丟（Buteo，約14901570年，法國）給出的，他開始用不很完整的加減消元法解一次方程組，比秦九韶晚了312年，且理論上的不完整也遜于秦九