数学示范教案：中国古代数学中的算法案例

学必求其心得，业必贵于专精学必求其心得，业必贵于专精学必求其心得，业必贵于专精示范教案eq\o(\s\up7(）,\s\do5（整体设计））教学分析在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力．三维目标1．理解算法案例的算法步骤和程序框图,进一步体会算法的思想．2．引导学生得出自己设计的算法程序，提高分析问题和解决问题的能力．重点难点教学重点:引导学生得出自己设计案例的算法步骤、程序框图和算法程序．教学难点：编写算法案例的程序．课时安排2课时eq\o（\s\up7（),\s\do5（教学过程））第1课时求两个正整数最大公约数的算法导入新课思路1(情境导入)．大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题,东、西方人处理问题方式是有所不同的．在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止,然后把所有的除数连乘起来。当两个数公有的质因数较大时(如8251与6105)，使用上述方法求最大公约数就比较困难．教师点出课题．思路2（直接导入）．前面我们学习了算法步骤、程序框图和算法语句．今天我们将通过“更相减损之术”来进一步体会算法的思想．推进新课eq\b\lc\\rc\(\a\vs4\al\co1(新知探究）)eq\b\lc\\rc\(\a\vs4\al\co1(提出问题））eq\a\vs4\al(1什么叫约数？，2什么叫最大公约数？，3阅读教材写出更相减损之术的算法步骤和程序。）讨论结果：(1)如果整数a能被整数b整除，则b称为a的一个约数．(2)两个整数m与n的公约数中的最大值称为m与n的最大公约数．(3)求两个整数a与b的最大公约数，“更相减损之术”的算法步骤：对于给定的两个数，以两数中较大数减去较小的数，然后将差和较小数构成一对新数，再用较大数减去较小的数，反复执行此步骤,直到差数和较小的数相等,此时相等的两数便为原两数的最大公约数．程序如下：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的最大公约数．分析：用(a,b）形写出求解过程．解:（78,36)→(42，36）→(6,36）→(6,30）→(6,24）→（6，18）→(6，12）→（6,6）．即78和36的最大公约数是6.点评：这种算法，只做简单的减法,操作方便、易懂，也完全符合算法的要求，它完全是机械的运算，据此很容易编出程序，在计算机上运算.变式训练求119与85的最大公约数．解:（119，85)→（34，85)→（34，51)→（34，17)→(17,17）,∴119与85的最大公约数为17。思路2求294与84的最大公约数．分析:由于这两个数都是偶数，同除以2后再用“更相减损之术"．解：∵294÷2＝147,84÷2＝42，∴取147与42的最大公约数后再乘2.(147,42）→（105，42)→（63,42）→(21，42）→（21，21)．∴294与84的最大公约数为21×2＝42.点评：当m与n均为偶数时，可以同除以2后再求解。变式训练求80与36的最大公约数．解：∵80÷2＝40,36÷2＝18，40÷2＝20，18÷2＝9，∴取20与9的最大公约数后再乘以4.(20,9)→（11，9）→(2，9）→（2，7)→（2，5）→(2，3）→（2，1)→（1,1）．∴80与36的最大公约数是1×4＝4.eq\b\lc\\rc\(\a\vs4\al\co1（知能训练))求1734与816的最大公约数．解：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的最大公约数是51×2＝102。eq\b\lc\\rc\（\a\vs4\al\co1（拓展提升)）求319,377,116的最大公约数．分析：先求319与377的最大公约数m，再求m与116的最大公约数n，则n为所求．解:(319,377)→(319,58)→(261，58）→（203，58）→(145，58)→（87,58)→(29，58)→(29，29)，∴319与377的最大公约数是29.(116,29)→（87,29)→(58,29)→（29，29）,∴116与29的最大公约数为29.∴319,377，116的最大公约数为29.eq\b\lc\\rc\（\a\vs4\al\co1（课堂小结)）本节学习了用“更相减损之术”求最大公约数．eq\b\lc\\rc\(\a\vs4\al\co1（作业））习题1—3A1。eq\o(\s\up7（），\s\do5(设计感想））数学不仅是一门科学,也是一种文化,本节从知识方面学习求两个正整数的最大公约数，从思想方法方面，主要学习递归思想．本节设置精彩例题，不仅让学生学到知识,而且让学生进一步体会算法的思想,培养学生的爱国主义情操．eq\o（\s\up7（)，\s\do5(备课资料)）求最大公约数的方法：辗转相除法．就是对于给定两数，用较大数除以较小数，若余数不为空，则将余数和较小数构成一对新数,继续上面的除法，直到大数被小数除尽，则这时较小数是原来两个数的最大公约数．算法步骤（以求两个正整数a、b的最大公约数为例）：S1输入两个正整数a，b（a〉b)；S2把a÷b的余数赋值给r；S3如果r≠0，那么把b赋给a，把r赋给b，转到S2；否则转到S4；S4输出最大公约数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(阅读教材,说说割圆术的过程。)讨论结果:我们先对单位圆内接正六边形、正十二边形、正二十四边形……的面积之间的关系进行分析，找出它们之间的递增规律．如下图所示,假设圆的半径为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－hn)．①正2n边形的边长为x2n＝eq\r（\f（xn，2）2＋1－hn2）.刘徽割圆术还注意到,如果在内接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)/2；n＝2＊n;x＝sqrt(x/2）^2＋（1－h)^2);endprint(%io(2)，n，s)；注：①此处i的终值为5.当i的终值为1,2，…时，程序分别算出正十二边形、正二十四边形……的面积．运行程序，当边数为192时,就可以得到刘徽求得的圆周率的近似值3.14，当边数为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次加法运算．第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法，计算机能更快地得到结果．（2）上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约1202~1261）在他的著作《数书九章》中提出了下面的算法:把一个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）计算机的一个很重要的特点就是运算速度快,但即便如此，算法好坏的一个重要标志仍然是运算的次数．如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法．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.点评：秦九韶用上述多项式求值的算法,并通过减根变换，给出了求高次代数方程根的完整算法．这一成就要比西方同样的算法早五六百年．这样的算法很容易在计算器或计算机上实现．思路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.）)这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现．算法步骤如下：S1输入多项式次数n、最高次的系数an和x的值；S2将v的值初始化为an，将i的值初始化为n－1；S3输入i次项的系数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)的值共需要______次运算．下面给出一种减少运算次数的算法：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的求值问题．直接法乘法运算的次数最多可到达eq\f(nn＋1，2），加法最多n次．秦九韶算法通过转化把乘法运算的次数减少到最多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。∴当x＝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时的