數(shù)學示范教案：中國古代數(shù)學中的算法案例

學必求其心得，業(yè)必貴于專精學必求其心得，業(yè)必貴于專精學必求其心得，業(yè)必貴于專精示范教案eq\o(\s\up7(）,\s\do5（整體設計））教學分析在學生學習了算法的初步知識,理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結合典型算法案例，讓學生經歷設計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力．三維目標1．理解算法案例的算法步驟和程序框圖,進一步體會算法的思想．2．引導學生得出自己設計的算法程序，提高分析問題和解決問題的能力．重點難點教學重點:引導學生得出自己設計案例的算法步驟、程序框圖和算法程序．教學難點：編寫算法案例的程序．課時安排2課時eq\o（\s\up7（),\s\do5（教學過程））第1課時求兩個正整數(shù)最大公約數(shù)的算法導入新課思路1(情境導入)．大家喜歡打乒乓球吧,由于東、西方文化及身體條件的不同,西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題,東、西方人處理問題方式是有所不同的．在小學，我們學過求兩個正整數(shù)的最大公約數(shù)的方法：先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止,然后把所有的除數(shù)連乘起來。當兩個數(shù)公有的質因數(shù)較大時(如8251與6105)，使用上述方法求最大公約數(shù)就比較困難．教師點出課題．思路2（直接導入）．前面我們學習了算法步驟、程序框圖和算法語句．今天我們將通過“更相減損之術”來進一步體會算法的思想．推進新課eq\b\lc\\rc\(\a\vs4\al\co1(新知探究）)eq\b\lc\\rc\(\a\vs4\al\co1(提出問題））eq\a\vs4\al(1什么叫約數(shù)？，2什么叫最大公約數(shù)？，3閱讀教材寫出更相減損之術的算法步驟和程序。）討論結果：(1)如果整數(shù)a能被整數(shù)b整除，則b稱為a的一個約數(shù)．(2)兩個整數(shù)m與n的公約數(shù)中的最大值稱為m與n的最大公約數(shù)．(3)求兩個整數(shù)a與b的最大公約數(shù)，“更相減損之術”的算法步驟：對于給定的兩個數(shù)，以兩數(shù)中較大數(shù)減去較小的數(shù)，然后將差和較小數(shù)構成一對新數(shù)，再用較大數(shù)減去較小的數(shù)，反復執(zhí)行此步驟,直到差數(shù)和較小的數(shù)相等,此時相等的兩數(shù)便為原兩數(shù)的最大公約數(shù)．程序如下：eq\x（\a\al（a＝input"pleasegivethefirstnumber”;,b＝input"pleasegivethesecondnumber”；，whilea〈〉b,ifa〉b,a＝a－b；，else,b＝b－a;，end，end,print%io2，a，b；))eq\b\lc\\rc\（\a\vs4\al\co1（應用示例)）思路1例求78和36的最大公約數(shù)．分析：用(a,b）形寫出求解過程．解:（78,36)→(42，36）→(6,36）→(6,30）→(6,24）→（6，18）→(6，12）→（6,6）．即78和36的最大公約數(shù)是6.點評：這種算法，只做簡單的減法,操作方便、易懂，也完全符合算法的要求，它完全是機械的運算，據此很容易編出程序，在計算機上運算.變式訓練求119與85的最大公約數(shù)．解:（119，85)→（34，85)→（34，51)→（34，17)→(17,17）,∴119與85的最大公約數(shù)為17。思路2求294與84的最大公約數(shù)．分析:由于這兩個數(shù)都是偶數(shù)，同除以2后再用“更相減損之術"．解：∵294÷2＝147,84÷2＝42，∴取147與42的最大公約數(shù)后再乘2.(147,42）→（105，42)→（63,42）→(21，42）→（21，21)．∴294與84的最大公約數(shù)為21×2＝42.點評：當m與n均為偶數(shù)時，可以同除以2后再求解。變式訓練求80與36的最大公約數(shù)．解：∵80÷2＝40,36÷2＝18，40÷2＝20，18÷2＝9，∴取20與9的最大公約數(shù)后再乘以4.(20,9)→（11，9）→(2，9）→（2，7)→（2，5）→(2，3）→（2，1)→（1,1）．∴80與36的最大公約數(shù)是1×4＝4.eq\b\lc\\rc\(\a\vs4\al\co1（知能訓練))求1734與816的最大公約數(shù)．解：1734÷2＝867，816÷2＝408，（867,408）→（459,408）→(51,408)→（51,357）→(51,306）→(51，255）→(51,204)→（51,153）→（51，102)→（51,51)．∴1734與816的最大公約數(shù)是51×2＝102。eq\b\lc\\rc\（\a\vs4\al\co1（拓展提升)）求319,377,116的最大公約數(shù)．分析：先求319與377的最大公約數(shù)m，再求m與116的最大公約數(shù)n，則n為所求．解:(319,377)→(319,58)→(261，58）→（203，58）→(145，58)→（87,58)→(29，58)→(29，29)，∴319與377的最大公約數(shù)是29.(116,29)→（87,29)→(58,29)→（29，29）,∴116與29的最大公約數(shù)為29.∴319,377，116的最大公約數(shù)為29.eq\b\lc\\rc\（\a\vs4\al\co1（課堂小結)）本節(jié)學習了用“更相減損之術”求最大公約數(shù)．eq\b\lc\\rc\(\a\vs4\al\co1（作業(yè)））習題1—3A1。eq\o(\s\up7（），\s\do5(設計感想））數(shù)學不僅是一門科學,也是一種文化,本節(jié)從知識方面學習求兩個正整數(shù)的最大公約數(shù)，從思想方法方面，主要學習遞歸思想．本節(jié)設置精彩例題，不僅讓學生學到知識,而且讓學生進一步體會算法的思想,培養(yǎng)學生的愛國主義情操．eq\o（\s\up7（)，\s\do5(備課資料)）求最大公約數(shù)的方法：輾轉相除法．就是對于給定兩數(shù)，用較大數(shù)除以較小數(shù)，若余數(shù)不為空，則將余數(shù)和較小數(shù)構成一對新數(shù),繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小數(shù)是原來兩個數(shù)的最大公約數(shù)．算法步驟（以求兩個正整數(shù)a、b的最大公約數(shù)為例）：S1輸入兩個正整數(shù)a，b（a〉b)；S2把a÷b的余數(shù)賦值給r；S3如果r≠0，那么把b賦給a，把r賦給b，轉到S2；否則轉到S4；S4輸出最大公約數(shù)b。第2課時割圓術與秦九韶算術導入新課思路1(情境導入)．大家都喜歡吃蘋果吧，我們吃蘋果都是從外到里一口一口地吃，而蟲子卻是先鉆到蘋果里面從里到外一口一口地吃，由此看來處理同一個問題的方法多種多樣。怎樣求多項式f(x）＝x5＋x4＋x3＋x2＋x＋1當x＝5時的值呢？方法也是多種多樣的，今天我們開始學習割圓術和秦九韶算法．思路2（直接導入)．前面我們學習了更相減損之術，今天我們開始學習割圓術和秦九韶算法．推進新課eq\b\lc\\rc\（\a\vs4\al\co1（新知探究)）eq\b\lc\\rc\（\a\vs4\al\co1（提出問題）)eq\a\vs4\al(閱讀教材,說說割圓術的過程。)討論結果:我們先對單位圓內接正六邊形、正十二邊形、正二十四邊形……的面積之間的關系進行分析，找出它們之間的遞增規(guī)律．如下圖所示,假設圓的半徑為1，面積為S，圓內接正n邊形面積為Sn，邊長為xn，邊心距為hn.根據勾股定理，hn＝eq\r（1－\f(xn，2）2).正2n邊形的面積為正n邊形的面積Sn再加上n個等腰三角形（ADB）的面積和，即S2n＝Sn＋n·eq\f(1,2)·xn（1－h(huán)n)．①正2n邊形的邊長為x2n＝eq\r（\f（xn，2）2＋1－h(huán)n2）.劉徽割圓術還注意到,如果在內接n邊形的每一邊上,作一高為CD的矩形，就可得到S2n<S<S2n＋（S2n－Sn）．②這樣,我們就不僅可計算出圓周率的不足近似值,還可計算出圓周率的過剩近似值．從正六邊形的面積開始計算，即n＝6，則正六邊形的面積S6＝6×eq\f（\r(3）,4）.用上面的公式①重復計算,就可得到正十二邊形、正二十四邊形……的面積．因為圓的半徑為1，所以隨著n的增大，S2n的值不斷趨近于圓周率,這樣不斷計算下去,就可以得到越來越精密的圓周率近似值．下面我們根據劉徽割圓術的算法思想，用Scilab語言寫出求π的不足近似值的程序:n＝6；x＝1；s＝6＊sqrt（3）/4;fori＝1:1:5①h＝sqrt（1－（x/2）^2)；s＝s＋n＊x＊(1－h(huán))/2；n＝2＊n;x＝sqrt(x/2）^2＋（1－h(huán))^2);endprint(%io(2)，n，s)；注：①此處i的終值為5.當i的終值為1,2，…時，程序分別算出正十二邊形、正二十四邊形……的面積．運行程序，當邊數(shù)為192時,就可以得到劉徽求得的圓周率的近似值3.14，當邊數(shù)為24576時，就得到了祖沖之計算的結果3。1415926。由于是用圓內接正多邊形逼近圓，因而得到的圓周率總是小于π的實際值．作為練習，請同學編出程序求S2n＋（S2n－Sn)(n＝6,12，…)作為π的過剩近似值．eq\b\lc\\rc\(\a\vs4\al\co1（提出問題）)eq\a\vs4\al(1求多項式fx＝x5＋x4＋x3＋x2＋x＋1當x＝5時的值有哪些方法？比較它們的特點.，2什么是秦九韶算法？，3怎樣評價一個算法的好壞？)討論結果：（1)怎樣求多項式f（x）＝x5＋x4＋x3＋x2＋x＋1當x＝5時的值呢？一個自然的做法就是把5代入多項式f(x），計算各項的值，然后把它們加起來，這時，我們一共做了1＋2＋3＋4＝10次乘法運算，5次加法運算．另一種做法是先計算x2的值，然后依次計算x2·x，(x2·x)·x，((x2·x）·x)·x的值，這樣每次都可以利用上一次計算的結果，這時，我們一共做了4次乘法運算，5次加法運算．第二種做法與第一種做法相比，乘法的運算次數(shù)減少了，因而能夠提高運算效率，對于計算機來說，做一次乘法運算所用的時間比做一次加法運算要長得多,所以采用第二種做法，計算機能更快地得到結果．（2）上面問題有沒有更有效的算法呢?我國南宋時期的數(shù)學家秦九韶(約1202~1261）在他的著作《數(shù)書九章》中提出了下面的算法:把一個n次多項式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫成如下形式：f（x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝（(anxn－2＋an－1xn－3＋…＋a2）x＋a1）x＋a0＝(…（（anx＋an－1)x＋an－2）x＋…＋a1)x＋a0。求多項式的值時，首先計算最內層括號內一次多項式的值，即v1＝anx＋an－1，然后由內向外逐層計算一次多項式的值，即v2＝v1x＋an－2，v3＝v2x＋an－3，…vn＝vn－1x＋a0，這樣，求n次多項式f(x)的值就轉化為求n個一次多項式的值．上述方法稱為秦九韶算法．直到今天,這種算法仍是多項式求值比較先進的算法．(3）計算機的一個很重要的特點就是運算速度快,但即便如此，算法好壞的一個重要標志仍然是運算的次數(shù)．如果一個算法從理論上需要超出計算機允許范圍內的運算次數(shù)，那么這樣的算法就只能是一個理論的算法．eq\b\lc\\rc\(\a\vs4\al\co1(應用示例))思路1例用秦九韶方法求多項式f（x)＝1＋x＋0.5x2＋0。16667x3＋0.04167x4＋0.00833x5在x＝－0.2時的值．解:x＝－0.2，a5＝0。00833v0＝a5＝0。00833a4＝0.04167v1＝v0x＋a4＝0。04a3＝0。16667v2＝v1x＋a3＝0.15867a2＝0.5v3＝v2x＋a2＝0.46827a1＝1v4＝v3x＋a1＝0.90635a0＝1v5＝v4x＋a0＝0.81873所以f(－0.2）＝0。81873.點評：秦九韶用上述多項式求值的算法,并通過減根變換，給出了求高次代數(shù)方程根的完整算法．這一成就要比西方同樣的算法早五六百年．這樣的算法很容易在計算器或計算機上實現(xiàn)．思路2已知一個5次多項式為f(x）＝5x5＋2x4＋3.5x3－2。6x2＋1.7x－0.8，用秦九韶算法求這個多項式當x＝5時的值．解:根據秦九韶算法，把多項式改寫成如下形式：f(x)＝（（(（5x＋2）x＋3。5)x－2.6）x＋1.7)x－0.8，按照從內到外的順序，依次計算一次多項式當x＝5時的值:v0＝5；v1＝5×5＋2＝27；v2＝27×5＋3.5＝138。5；v3＝138.5×5－2.6＝689.9；v4＝689.9×5＋1。7＝3451.2;v5＝3415.2×5－0。8＝17255。2;所以，當x＝5時，多項式的值等于17255.2.點評:觀察上述秦九韶算法中的n個一次式,可見vk的計算要用到vk－1的值,若令v0＝an,我們可以得到下面的公式：eq\b\lc\｛\rc\（\a\vs4\al\co1(v0＝an，，vk＝vk－1x＋an－kk＝1,2,…，n.）)這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn)．算法步驟如下：S1輸入多項式次數(shù)n、最高次的系數(shù)an和x的值；S2將v的值初始化為an，將i的值初始化為n－1；S3輸入i次項的系數(shù)ai；S4v＝vx＋ai，i＝i－1；S5判斷i是否大于或等于0.若是，則返回S3;否則，輸出多項式的值v。變式訓練已知n次多項式Pn(x)＝a0xn＋a1xn－1＋…＋an－1x＋an，如果在一種算法中，計算xeq\o\al(k，0)（k＝2，3，4,…，n）的值需要k－1次乘法，計算P3(x0）的值共需要9次運算（6次乘法,3次加法），那么計算P10(x0)的值共需要______次運算．下面給出一種減少運算次數(shù)的算法：P0(x）＝a0,Pk＋1(x）＝xPk(x）＋ak＋1(k＝0,1,2，…，n－1)．利用該算法，計算P3（x0)的值共需要6次運算,計算P10(x0）的值共需要________次運算．解析：秦九韶算法適用一般的多項式f(x）＝anxn＋an－1xn－1＋…＋a1x＋a0的求值問題．直接法乘法運算的次數(shù)最多可到達eq\f(nn＋1，2），加法最多n次．秦九韶算法通過轉化把乘法運算的次數(shù)減少到最多n次，加法最多n次．答案:6520eq\b\lc\\rc\（\a\vs4\al\co1（知能訓練）)當x＝2時，用秦九韶算法求多項式f(x)＝3x5＋8x4－3x3＋5x2＋12x－6的值．解法一：根據秦九韶算法,把多項式改寫成如下形式：f（x）＝（((（3x＋8)x－3)x＋5）x＋12）x－6.按照從內到外的順序,依次計算一次多項式當x＝2時的值．v0＝3；v1＝v0×2＋8＝3×2＋8＝14；v2＝v1×2－3＝14×2－3＝25；v3＝v2×2＋5＝25×2＋5＝55;v4＝v3×2＋12＝55×2＋12＝122；v5＝v4×2－6＝122×2－6＝238?！喈攛＝2時，多項式的值為238。解法二：f(x）＝(（（(3x＋8)x－3)x＋5）x＋12）x－6，則f（2)＝（((（3×2＋8）×2－3)×2＋5)×2＋12)×2－6＝238.eq\b\lc\\rc\(\a\vs4\al\co1（拓展提升)）用秦九韶算法求多項式f（x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x當x＝3時的