算法案例---秦九韶算法

1、【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流算法案例-秦九韶算法.精品文檔.§1.3算法案例-秦九韶算法高二數(shù)學(xué)組 梅 杰一.教學(xué)目標(biāo)1.了解秦九韶算法的計(jì)算過(guò)程，并理解利用秦九韶算法可以減少計(jì)算次數(shù)提高計(jì)算效率的實(shí)質(zhì)；2.能利用秦九韶算法進(jìn)行一些多項(xiàng)式的計(jì)算，能用循環(huán)結(jié)構(gòu)表示算法步驟。二教學(xué)重難點(diǎn)1.理解秦九韶算法體現(xiàn)的思想；2.用循環(huán)結(jié)構(gòu)表示算法步驟。三.教學(xué)過(guò)程（一）創(chuàng)設(shè)情景，揭示課題問(wèn)題1 ：請(qǐng)同學(xué)們?cè)O(shè)計(jì)一個(gè)算法，計(jì)算當(dāng)時(shí)的值。學(xué)生可能會(huì)提出兩種做法：做法一：把5代入多項(xiàng)式的每一項(xiàng)，計(jì)算每一項(xiàng)的值，然后相加；做法二：先計(jì)算x的冪，可以利用前面的計(jì)算結(jié)果，以減少計(jì)算量，

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

3、數(shù)423.5-2.61.7-0.8運(yùn)算20110567.52824.514131+變形后x的系數(shù)422113.5564.92826.214130.2*5思考：讓學(xué)生回顧整個(gè)計(jì)算過(guò)程，用此種方法一共進(jìn)行了多少次乘法、加法運(yùn)算？點(diǎn)評(píng)：一共進(jìn)行了5次乘法，5次加法運(yùn)算，相比較前兩種做法，此做法更快、更方便，而且在計(jì)算過(guò)程中，只與多項(xiàng)式的系數(shù)有關(guān)。這種算法就是“秦九韶算法”，在此可以介紹下秦九韶生平。【見(jiàn)附頁(yè)】（二）研探新知問(wèn)題1：怎樣用秦九韶算法求一般的多項(xiàng)式當(dāng)x=x0時(shí)的值？類(lèi)似上述方法，將多項(xiàng)式變形為：由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，把n次多項(xiàng)式的求值問(wèn)題轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式值的問(wèn)題，即求：,

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

5、出多項(xiàng)式的值.畫(huà)程序框圖（略）翻譯成程序語(yǔ)言INPUT “n=”;n INPUT “an=”;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.利用秦九韶算法計(jì)算當(dāng)時(shí)的值，并統(tǒng)計(jì)需要多少次乘法計(jì)算和多少次加法計(jì)算？例2利用秦九韶算法計(jì)算多項(xiàng)式當(dāng)時(shí)的值點(diǎn)評(píng): 如果多項(xiàng)式函數(shù)中有缺項(xiàng)的畫(huà),要以系數(shù)為的項(xiàng)補(bǔ)齊后再計(jì)算.例3 .某城市2001年末汽車(chē)保有量為萬(wàn)輛,預(yù)計(jì)此后每年報(bào)廢上一年末汽車(chē)保有量的,并且每年新增汽車(chē)萬(wàn)輛.設(shè)計(jì)算法,計(jì)算經(jīng)過(guò)多

6、少年可使汽車(chē)保有量達(dá)到萬(wàn)輛.將此算法用程序語(yǔ)言給出.解：設(shè),經(jīng)過(guò)幾年的汽車(chē)保有量為,則上述各式充分說(shuō)明了秦九韶算法的優(yōu)點(diǎn):可以通過(guò)遞推關(guān)系進(jìn)行迭代處理.程序?yàn)? C=0.94A=30n=0WHILE A<40 A=A*C+3 n=n+1WENDPRINT nEND（四）課堂小結(jié)（五）布置作業(yè)秦九韶生平簡(jiǎn)介     南宋大數(shù)學(xué)家秦九韶 秦九韶（公元12021261），字道古，安岳人。秦九韶與李冶、楊輝、朱世杰并稱(chēng)宋元數(shù)學(xué)四大家。其父秦季棲，進(jìn)士出身，官至上部郎中、秘書(shū)少監(jiān)。    秦九韶聰敏勤學(xué)。宋紹定四年（1

7、231），秦九韶考中進(jìn)士，先后擔(dān)任縣尉、通判、參議官、州守、同農(nóng)、寺丞等職。先后在湖北、安徽、江蘇、浙江等地做官，1261年左右被貶至梅州（今廣東梅縣），不久死于任所。他在政務(wù)之余，對(duì)數(shù)學(xué)進(jìn)行虔心鉆研，并廣泛搜集歷學(xué)、數(shù)學(xué)、星象、音律、營(yíng)造等資料，進(jìn)行分析、研究。 宋淳祜四至七年（1244至1247），他在為母親守孝時(shí)，把長(zhǎng)期積累的數(shù)學(xué)知識(shí)和研究所得加以編輯，寫(xiě)成了聞名的巨著數(shù)學(xué)九章，并創(chuàng)造了“大衍求一術(shù)”。這 不僅在當(dāng)時(shí)處于世界領(lǐng)先地位，在近代數(shù)學(xué)和現(xiàn)代電子計(jì)算設(shè)計(jì)中，也起到了重要作用，被稱(chēng)為“中國(guó)剩余定理”。他所論的“正負(fù)開(kāi)方術(shù)”，被稱(chēng)為“秦九韶程序”?，F(xiàn)在，世界各國(guó)從小學(xué)、中學(xué)到大學(xué)的數(shù)

8、學(xué)課程，幾乎都接觸到他的定理、定律和解題原則。秦九韶在數(shù)學(xué)方面的研究成果，比英國(guó)數(shù)學(xué)家取得的成果要早800多年。安岳修建的秦九韶紀(jì)念館，恢宏壯觀，雄偉氣派。秦九韶的數(shù)學(xué)成就及對(duì)世界數(shù)學(xué)的貢獻(xiàn)主要表現(xiàn)在以下方面：1、秦九韶的數(shù)書(shū)九章是一部劃時(shí)代的巨著 秦九韶潛心研究數(shù)學(xué)多年，在湖州守孝三年，所寫(xiě)成的世界數(shù)學(xué)名著數(shù)學(xué)九章，癸辛雜識(shí)續(xù)集稱(chēng)作數(shù)學(xué)大略，永樂(lè)大典稱(chēng)作數(shù)學(xué)九章。全書(shū)九章十八卷，九章九類(lèi)：“大衍類(lèi)”、“天時(shí)類(lèi)”、“田域類(lèi)”、“測(cè)望類(lèi)”、“賦役類(lèi)”、“錢(qián)谷類(lèi)”、“營(yíng)建類(lèi)”、“軍旅類(lèi)”、“市物類(lèi)”，每類(lèi)9題（9問(wèn)）共計(jì)81題（81問(wèn)），該書(shū)內(nèi)容豐富至極，上至天文、星象、歷律、測(cè)候，下至河道、水利

9、、建筑、運(yùn)輸，各種幾何圖形和體積，錢(qián)谷、賦役、市場(chǎng)、牙厘的計(jì)算和互易。許多計(jì)算方法和經(jīng)驗(yàn)常數(shù)直到現(xiàn)在仍有很高的參考價(jià)值和實(shí)踐意義，被譽(yù)為“算中寶典”。該書(shū)著述方式，大多由“問(wèn)曰”、“答曰”、“術(shù)曰”、“草曰”四部分組成：“問(wèn)曰”，是從實(shí)際生活中提出問(wèn)題；“答曰”，給出答案；“術(shù)曰”，闡述解題原理與步驟；“草曰”，給出詳細(xì)的解題過(guò)程。此書(shū)已為國(guó)內(nèi)外科學(xué)史界公認(rèn)的一部世界數(shù)學(xué)名著。此書(shū)不僅代表著當(dāng)時(shí)中國(guó)數(shù)學(xué)的先進(jìn)水平，也標(biāo)志著中世紀(jì)世界數(shù)學(xué)的最高水平。我國(guó)數(shù)學(xué)史家梁宗巨評(píng)價(jià)道：“秦九韶的數(shù)書(shū)九章（1247年）是一部劃時(shí)代的巨著，內(nèi)容豐富，精湛絕倫。特別是大衍求一術(shù)（不定方程的中國(guó)獨(dú)特解法）及高次代

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