1、1.3 中国古代数学中的算法案例,第一章 算法初步,学习目标 1.理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析. 2.理解割圆术中蕴含的数学原理. 3.了解秦九韶算法及利用它提高计算效率的本质. 4.对简单的案例能设计程序框图并写出算法程序.,题型探究,问题导学,内容索引,当堂训练,问题导学,知识点一 更相减损术,更相减损术的运算步骤 第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的
2、最大公约数.,偶数,2,第二步,较大,较小,较小,相等,知识点二 割圆术,1.割圆术的算法 S1 假设圆的半径为1，面积为S，圆内接正n边形面积为Sn，边长为xn，边心距为hn，先从圆内接正六边形的面积开始算起，即n6，则正六边形的面积S66S2 利用公式S2nSnn xn(1hn)重复计算，就可得到正十二边形、正二十四边形的面积.因为圆的半径为1，所以随着n的增大，S2n的值不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值.,2.割圆术的算法思想 刘徽从圆内接正六边形开始，让边数逐次加倍，逐个算出这些圆内接正多边形的面积，从而得到一系列逐渐递增的数值，来一步一步地逼近圆
3、面积，最后求出圆周率的近似值.用刘徽自己的话概括就是“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣.”,思考,知识点三 秦九韶算法,衡量一个算法是否优秀的重要参数是速度.把多项式f(x)x5x4x3x2x1变形为f(x)(x1)x1)x1)x1)x1，然后求当x5时的值，为什么比常规逐项计算省时？,从里往外计算，充分利用已有成果，可减少重复计算.,答案,秦九韶算法的一般步骤： 把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式： (anxan1)xan2)xa1)xa0，求多项式的值时，首先计算一次多项式的值，即v1 ，然后由内向外逐层计算一次多项式的值，
4、即 v2 ， v3 ， vn ， 这样，求n次多项式f(x)的值就转化为求 的值.,最内层括号内,梳理,anxan1,v1xan2,v2xan3,vn1xa0,n个一次多项式,题型探究,例1 试用更相减损术求612、396的最大公约数.,解答,类型一 更相减损术,方法一 6122306,3962198,3062153,198299，1539954,995445,54459,45936,36927,27918,1899.所以612、396的最大公约数为92236. 方法二 612396216,396216180,21618036,18036144,14436108,1083672,723636.
5、故36为612、396的最大公约数.,用更相减损术的算法步骤： 第一步，给定两个正整数m，n，不妨设mn. 第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n. 第三步，dmn. 第四步，判断“dn”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd(k是约简整数2的个数)为所求的最大公约数.,反思与感悟,跟踪训练1 用更相减损术求261和319的最大公约数.,解答,31926158， 26158203， 20358145， 1455887， 875829， 582929， 319与261的最大公约数为29.,例2 已知一个
6、5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值.,类型二 秦九韶算法的基本思想,解答,将f(x)改写为 f(x)(4x2)x3.5)x2.6)x1.7)x0.8， 由内向外依次计算一次多项式当x5时的值： v04；v145222； v22253.5113.5； v3113.552.6564.9； v4564.951.72 826.2； v52 826.250.814 130.2. 当x5时，多项式的值等于14 130.2.,秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高.,反思与感悟,跟踪训练2
7、用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值.,f(x)(7x6)x5)x4)x3)x2)x1)x，所以有v07， v173627， v2273586， v38634262， v426233789， v5789322 369， v62 369317 108， v77 108321 324. 故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21 324.,解答,当堂训练,1.用秦九韶算法计算多项式f(x)6x65x54x43x32x2x7在x0.4时的值时，需做加法和乘法的次数的和为 A.10 B.9 C.12 D.8,2,3,1,f(x)
8、(6x5)x4)x3)x2)x1)x7， 做加法6次，乘法6次， 6612(次)，故选C.,答案,解析,2.已知f(x)2x3x3，用秦九韶算法求当x3时v2的值.,f(x)2x3x32x30x2x3 (2x0)x1)x3， v02，v12306， v263119.,解答,2,3,1,3.用更相减损术求1 734和816的最大公约数.,因为1 734和816都是偶数，所以分别除以2得867和408. 867408459,45940851,40851357， 35751306,30651255,25551204， 20451153,15351102,1025151. 所以867和408的最大公约数是51，故1 734和816的最大公约数是512102.,解答,2,3,1,规律与方法,1.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数. 2.用秦九韶算法求多项式f(x)当xx0的值的思路为(1)改写；(2)计算(3)结论f(x0)vn.,本课结束,