2020版高中数学第一章算法初步1.3中国古代数学中的算法案例学案（含解析）新人教B版必修3.docx

1.3中国古代数学中的算法案例学习目标1.理解更相减损之术中的数学原理，并能根据这些原理进行算法分析.2.理解割圆术中蕴含的数学原理.3.了解秦九韶算法及利用它提高计算效率的本质.4.对简单的案例能设计程序框图并写出算法知识点一更相减损之术更相减损之术的运算步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数知识点二割圆术1割圆术的算法S1假设圆的半径为1，面积为S，圆内接正n边形面积为Sn，边长为xn，边心距为hn，先从圆内接正六边形的面积开始算起，即n6，则正六边形的面积S66；S2利用公式S2nSnnxn(1hn)重复计算，就可得到正十二边形、正二十四边形的面积因为圆的半径为1，所以随着n的增大，S2n的值不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值2割圆术的算法思想刘徽从圆内接正六边形开始，让边数逐次加倍，逐个算出这些圆内接正多边形的面积，从而得到一系列逐渐递增的数值，来一步一步地逼近圆面积，最后求出圆周率的近似值用刘徽自己的话概括就是“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣”知识点三秦九韶算法思考衡量一个算法是否优秀的重要参数是速度把多项式f(x)x5x4x3x2x1变形为f(x)(x1)x1)x1)x1)x1，然后求当x5时的值，为什么比常规逐项计算省时？答案从里往外计算，充分利用已有成果，可减少重复计算梳理秦九韶算法的一般步骤：把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：(anxan1)xan2)xa1)xa0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值1辗转相除法的基本步骤是用较大的数除以较小的数()2求最大公约数的方法除辗转相除法之外，没有其他方法()3编写辗转相除法的程序时，要用到循环语句()题型一更相减损之术例1试用更相减损之术求612,396的最大公约数解方法一6122306,3962198,3062153,198299，1539954,995445,54459,45936,36927,27918,1899.所以612,396的最大公约数为92236.方法二612396216,396216180,21618036,18036144,14436108,1083672,723636.故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已知一个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.72826.2；v52826.250.814130.2.当x5时，多项式的值为14130.2.反思与感悟秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高跟踪训练2用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值解f(x)(7x6)x5)x4)x3)x2)x1)x，所以有v07，v173627，v2273586，v38634262，v426233789，v5789322369，v62369317108，v77108321324.故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21324.1用秦九韶算法计算多项式f(x)6x65x54x43x32x2x7在x0.4时的值时，需做加法和乘法的次数的和为()A10 B9 C12 D8答案C解析f(x)(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.3用更相减损之术求1734和816的最大公约数解因为1734和816都是偶数，所以分别除以2得867和408.867408459,45940851,40851357，35751306,30651255,25551204，20451153,15351102,1025151.所以867和408的最大公约数是51，故1734和816的最大公约数是512102.1更相减损之术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数2用秦九韶算法求多项式f(x)当xx0的值的思路为(1)改写；(2)计算(3)结论f(x0)vn.一、选择题11037和425的最大公约数是()A51 B17 C9 D3答案B2利用秦九韶算法求当x2时，f(x)12x3x24x35x46x5的值，下列说法正确的是()A先求122B先求625，第二步求2(625)4C用f(2)122322423524625直接运算求解D以上都不正确答案B345和150的最大公约数和最小公倍数分别是()A5,150 B15,450C450,15 D15,150答案B4用秦九韶算法计算f(x)6x54x4x32x29x，需要加法(或减法)与乘法运算的次数分别为()A5,4 B5,5 C4,4 D4,5答案D解析n次多项式，当最高次项的系数不为1时，需进行n次乘法；若各项均不为0，则需进行n次加法(或减法)，缺一项就减少一次加法(或减法)运算，而这个5次多项式的5次项系数不为1，缺常数项，因而乘法次数为5，加法(或减法)次数为514.故选D.5下面程序框图的算法思路源于我国古代数学名著九章算术中的“更相减损之术”执行该程序框图，若输入的a，b分别为14,18，则输出的a等于()A0 B2 C4 D14答案B解析开始：a14，b18，第一次循环：a14，b4；第二次循环：a10，b4；第三次循环：a6，b4；第四次循环：a2，b4；第五次循环：a2，b2.此时，ab，退出循环，输出a2.6用秦九韶算法求多项式f(x)12xx23x32x4当x1时的值时，v2的结果是()A4 B1 C5 D6答案D解析此题的n4，a42，a33，a21，a12，a01，由秦九韶算法的递推关系式得v1v0xa32(1)35，v2v1xa25(1)16，故选D.7三个数4557,1953,5115的最大公约数是()A31 B93 C217 D651答案B8已知f(x)x52x33x2x1，应用秦九韶算法计算当x3时的值时，v3的值为()A27 B11 C109 D36答案D解析将函数式化成如下形式，f(x)(x0)x2)x3)x1)x1.由内向外依次计算：v01，v11303，v233211，v3113336，v43631109，v510931328.二、填空题9自然数8251和6105的最大公约数为_答案37解析利用更相减损之术可得它们的最大公约数为37.10用秦九韶算法求多项式6x35x24x3的值时，应先将此多项式变形为_答案(6x5)x4)x3解析6x35x24x3(6x25x4)x3(6x5)x4)x3.11用更相减损之术求459和357的最大公约数，需进行减法的次数为_答案5解析利用更相减损之术，有459357102,357102255,255102153,15310251,1025151，共进行了5次减法12用秦九韶算法求多项式f(x)20.35x1.8x23.66x36x45.2x5x6在x1.3时的值时，令v0a6，v1v0xa5，v6v5xa0时，v3的值为_答案22.445三、解答题13求三个数72,120,168的最大公约数解(更相减损之术)：先求120,168的最大公约数16812048,1204872,724824,482424，所以120,168的最大公约数为24.再求72,24的最大公约数722448,482424，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.14用秦九韶算法求多项式f(x)4x53x45x3x2x当x2时的值解因为f(x)(4x3)x5)x1)x1)x，所以v04，v142311，v2112527，v3272155，v45521111，v51112222.所以当x2时，多项式f(x)4x53x45x3x2x的值为222.四、探究与拓展15秦九韶是我国南宋时期的数学家，普州(现四川省安岳县)人，他在所著的数书九章中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例，若输入n，x的值分别为3,2，则输出v的值为()A9 B18C20 D35答案B解析初始值n3，x2，程序运行过程如下：v1i2v1224i1v4219i0v92018i1跳