数学人教B版必修3示范教案：1.3　中国古代数学中的算法案例 WORD版含解析.doc

1、示范教案教学分析在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力三维目标1理解算法案例的算法步骤和程序框图，进一步体会算法的思想2引导学生得出自己设计的算法程序，提高分析问题和解决问题的能力重点难点教学重点：引导学生得出自己设计案例的算法步骤、程序框图和算法程序教学难点：编写算法案例的程序课时安排2课时第1课时求两个正整数最大公约数的算法导入新课思路1(情境导入)大家喜欢打乒乓球吧，由于东、西方文化及身

2、体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时(如8 251与6 105)，使用上述方法求最大公约数就比较困难教师点出课题思路2(直接导入)前面我们学习了算法步骤、程序框图和算法语句今天我们将通过“更相减损之术”来进一步体会算法的思想推进新课讨论结果：(1)如果整数a能被整数b整除，则b称为a的一个约数(2)两个整数m与n的公约数中的最大值称为m与n的最大公约数(3)求两

3、个整数a与b的最大公约数，“更相减损之术”的算法步骤：对于给定的两个数，以两数中较大数减去较小的数，然后将差和较小数构成一对新数，再用较大数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两数便为原两数的最大公约数程序如下：思路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的最大公约数解

4、：(119,85)(34,85)(34,51)(34,17)(17,17)，119与85的最大公约数为17.思路2求294与84的最大公约数分析：由于这两个数都是偶数，同除以2后再用“更相减损之术”解：2942147,84242，取147与42的最大公约数后再乘2.(147,42)(105,42)(63,42)(21,42)(21,21)294与84的最大公约数为21242.点评：当m与n均为偶数时，可以同除以2后再求解.变式训练求80与36的最大公约数解：80240,36218，40220,1829，取20与9的最大公约数后再乘以4.(20,9)(11,9)(2,9)(2,7)(2,5)(2

5、,3)(2,1)(1,1)80与36的最大公约数是144.求1 734与816的最大公约数解：1 7342867,8162408，(867,408)(459,408)(51,408)(51,357)(51,306)(51,255)(51,204)(51,153)(51,102)(51,51)1 734与816的最大公约数是512102.求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的

6、最大公约数是29.(116,29)(87,29)(58,29)(29,29)，116与29的最大公约数为29.319,377,116的最大公约数为29.本节学习了用“更相减损之术”求最大公约数习题13A1.数学不仅是一门科学，也是一种文化，本节从知识方面学习求两个正整数的最大公约数，从思想方法方面，主要学习递归思想本节设置精彩例题，不仅让学生学到知识，而且让学生进一步体会算法的思想，培养学生的爱国主义情操求最大公约数的方法：辗转相除法就是对于给定两数，用较大数除以较小数，若余数不为空，则将余数和较小数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时较小数是原来两个数的最大公约数算法步骤

7、(以求两个正整数a、b的最大公约数为例)：S1输入两个正整数a，b(ab)；S2把ab的余数赋值给r；S3如果r0，那么把b赋给a，把r赋给b，转到S2；否则转到S4；S4输出最大公约数b.第2课时割圆术与秦九韶算术导入新课思路1(情境导入)大家都喜欢吃苹果吧，我们吃苹果都是从外到里一口一口地吃，而虫子却是先钻到苹果里面从里到外一口一口地吃，由此看来处理同一个问题的方法多种多样. 怎样求多项式f(x)x5x4x3x2x1当x5时的值呢？方法也是多种多样的，今天我们开始学习割圆术和秦九韶算法思路2(直接导入)前面我们学习了更相减损之术， 今天我们开始学习割圆术和秦九韶算法推进新课讨论结果：我们先

8、对单位圆内接正六边形、正十二边形、正二十四边形的面积之间的关系进行分析，找出它们之间的递增规律如下图所示，假设圆的半径为1，面积为S，圆内接正n边形面积为Sn，边长为xn，边心距为hn.根据勾股定理，hn.正2n边形的面积为正n边形的面积Sn再加上n个等腰三角形(ADB)的面积和，即S2nSnnxn(1hn)正2n边形的边长为x2n.刘徽割圆术还注意到，如果在内接n边形的每一边上，作一高为CD的矩形，就可得到S2nSS2n(S2nSn)这样，我们就不仅可计算出圆周率的不足近似值，还可计算出圆周率的过剩近似值从正六边形的面积开始计算，即n6，则正六边形的面积S66.用上面的公式重复计算，就可得到

9、正十二边形、正二十四边形的面积因为圆的半径为1，所以随着n的增大，S2n的值不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值下面我们根据刘徽割圆术的算法思想，用Scilab语言写出求的不足近似值的程序：n6；x1；s6 * sqrt(3)/4；for i1：1：5hsqrt(1(x/2)2)；ssn *x * (1h)/2；n2 *n；xsqrt(x/2)2(1h)2)；endprint(%io(2)，n，s)；注：此处i的终值为5.当i的终值为1,2，时，程序分别算出正十二边形、正二十四边形的面积运行程序，当边数为192时，就可以得到刘徽求得的圆周率的近似值3.14，当

10、边数为 24 576 时，就得到了祖冲之计算的结果3.141 592 6.由于是用圆内接正多边形逼近圆，因而得到的圆周率总是小于的实际值作为练习，请同学编出程序求S2n(S2nSn)(n6,12，)作为的过剩近似值讨论结果：(1)怎样求多项式f(x)x5x4x3x2x1当x5时的值呢？一个自然的做法就是把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了123410次乘法运算，5次加法运算另一种做法是先计算x2的值，然后依次计算x2x，(x2x)x，(x2x)x)x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算第二种做法与第一种做法

11、相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果(2)上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶(约12021261)在他的著作数书九章中提出了下面的算法：把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计

12、算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值上述方法称为秦九韶算法直到今天，这种算法仍是多项式求值比较先进的算法(3)计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法思路1例 用秦九韶方法求多项式f(x)1x0.5x20.166 67x30.041 67x40.008 33x5在x0.2时的值解：x0.2， a50.008 33v0a5 0.008 33a40.041 67

13、v1v0xa4 0.04a30.166 67 v2v1xa3 0.158 67a20.5 v3v2xa2 0.468 27a11 v4v3xa1 0.906 35a01 v5v4xa0 0.818 73所以 f(0.2)0.818 73.点评：秦九韶用上述多项式求值的算法，并通过减根变换，给出了求高次代数方程根的完整算法这一成就要比西方同样的算法早五六百年这样的算法很容易在计算器或计算机上实现思路2已知一个5次多项式为f(x)5x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值解：根据秦九韶算法，把多项式改写成如下形式：f(x)(5x2)x3.5)x2.6)x1

14、.7)x0.8，按照从内到外的顺序，依次计算一次多项式当x5时的值：v05；v155227；v22753.5138.5；v3138.552.6689.9；v4689.951.73 451.2；v53 415.250.817 255.2；所以，当x5时，多项式的值等于17 255.2.点评：观察上述秦九韶算法中的n个一次式，可见vk的计算要用到vk1的值，若令v0an，我们可以得到下面的公式：这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现算法步骤如下：S1输入多项式次数n、最高次的系数an和x的值；S2将v的值初始化为an，将i的值初始化为n1；S3输入i次项的系数ai；S4vvx

15、ai，ii1；S5判断i是否大于或等于0.若是，则返回S3；否则，输出多项式的值v.变式训练已知n次多项式Pn(x)a0xna1xn1an1xan，如果在一种算法中，计算x(k2,3,4，n)的值需要k1次乘法，计算P3(x0)的值共需要9次运算(6次乘法，3次加法)，那么计算P10(x0)的值共需要_次运算下面给出一种减少运算次数的算法：P0(x)a0，Pk1(x)xPk(x)ak1(k0,1,2，n1)利用该算法，计算P3(x0)的值共需要 6次运算，计算P10(x0)的值共需要_次运算解析：秦九韶算法适用一般的多项式f(x)anxnan1xn1a1xa0的求值问题直接法乘法运算的次数最多

16、可到达，加法最多n次秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次答案：6520当x2时，用秦九韶算法求多项式f(x)3x58x43x35x212x6的值解法一：根据秦九韶算法，把多项式改写成如下形式：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式当x2时的值v03；v1v02832814；v2v123142325；v3v225252555；v4v321255212122；v5v42612226238.当x2时，多项式的值为238.解法二：f(x)(3x8)x3)x5)x12)x6，则f(2)(328)23)25)212)26238.用秦九韶

17、算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值解：f(x)(7x6)5)x4)x3)x2)x1)xv07；v173627；v2273586；v38634262；v426233789；v5789322 369；v62 369317 108；v77 1083021 324.f(3)21 324.本节学习了割圆术和秦九韶算法习题13A4.古老的算法散发浓郁的现代气息，这是一节充满智慧的课本节主要介绍了秦九韶算法通过对秦九韶算法的学习，对算法本身有哪些进一步的认识？教师引导学生思考、讨论、概括，小结时要关注如下几点：(1)算法具有通用的特点，可以解决一类问题；(2)解决同一类问题，可以有不同的算法，但计算的效率是不同的，应该选择高效的算法；(3)算法的种类虽多，但三种逻辑结构可以有效地表达各种算法等等 进位制进位制是人们为了计数和运算方便而约定的计数系统约定满二进一，就是二进制，约定满十进一，就是十进制即满几进一就是几进制一般来说，以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan1a1a0(k)(0ank)，0aik(i0,1，n1)将k进制数用十进制表示，应等于：anan1a1a0(k)anknan1kn1a1k1a0k0.将十进制数用k进制表示，可以采用除k取余法