高中数学算法初步1.3中国古代数学中的算法案例课件.pptx

一、求两个正整数的最大公约数的算法 【问题思考】 1.试计算4与12,8与72,6与96的最大公约数;再计算一下4与12-4,8与72-8,6与96-6的最大公约数.通过比较,你能发现什么规律? 提示:这两组的最大公约数均分别是4,8,6.由此可归纳出对于两个正整数a,b(ab),a与b的最大公约数和b与a-b的最大公约数相同.,2.填空: (1)“等值算法”在我国古代也称为更相减损之术,它是用来求两个正整数的最大公约数的方法,其基本过程是:对于给定的两个数,用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的两数相等为止,则所得数就是所求的最大公约数. (2)辗转相除法(即欧几里得算法)是用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.,3.辗转相除法与更相减损之术有何异同? 提示:相同点:都是求最大公约数的方法.更相减损之术的理论依据为:由m-n=r,得m=n+r,可以看出,m,n与n,r有相同的公约数;辗转相除法的理论依据是:由m=nq+r可以看出,m,n和n,r有相同的公约数,即二者的“算理”相似. 不同点:更相减损之术进行的是减法运算,辗转相除法进行的是除法运算,计算次数上辗转相除法计算次数相对较少.结果上,辗转相除法体现结果是以相除余数为0得到,而更相减损之术则以减数与差相等而得到. 4.做一做:840和1 764的最大公约数是( ) A.84 B.12 C.168 D.252 答案:A,二、割圆术 【问题思考】 1.填空: 割圆术是我国魏晋时期的数学家刘徽在注九章算术中采用正多边形面积逐渐逼近圆面积的算法计算圆周率的一种方法.他的思想后来又得到祖冲之的推进和发展,计算出的圆周率的近似值在世界上很长时间里处于领先地位. 2.做一做:用圆内接正多边形逼近圆,因而得到的圆周率总是 的实际值. 答案:小于,三、秦九韶算法 【问题思考】 1.填空: (1)秦九韶算法是我国宋代数学家秦九韶在他的代表作数学九章中提出的一种用于计算多项式的值的方法.直到今天,这种算法仍是世界上多项式求值的最先进的算法. (2)秦九韶算法适用于一般的多项式f(x)=anxn+an-1xn-1+a1x+a0的求值问题.用秦九韶算法可把n次多项式的求值问题转化成求n个一次多项式的值的问题,即求 v0=an, v1=v0x+an-1, v2=v1x+an-2, v3=v2x+an-3, vn=vn-1x+a0.,提示:根据秦九韶算法知,v2=v1x+an-2,v1=anx+an-1, 故v2=(anx+an-1)x+an-2.,3.为什么说秦九韶算法是多项式求值最先进的算法?,4.做一做:已知f(x)=x5+2x3+3x2+x+1,应用秦九韶算法计算x=3时的值时,v3的值为 . 答案:36,思考辨析 判断下列说法是否正确,正确的在后面的括号内画“”,错误的画“”. (1)用更相减损之术求294与84的最大公约数时,需要做5次减法. ( ) (2)秦九韶算法是按照从内到外的顺序依次计算求值的. ( ) (3)秦九韶算法适用所有函数的求函数值运算. ( ) 答案:(1) (2) (3),探究一,探究二,探究三,易错辨析,【例1】 分别用辗转相除法和更相减损之术求下列两数的最大公约数. (1)261,319;(2)1 734,816. 解:(1)辗转相除法: 319261=1(余58) 26158=4(余29) 5829=2(余0) 319与261的最大公约数是29. 更相减损之术:(261,319)(261,58)(203,58)(145,58)(87,58) (29,58)(29,29). 319与261的最大公约数是29.,探究一,探究二,探究三,易错辨析,(2)辗转相除法: 1 734816=2(余102),816102=8(余0), 1 734与816的最大公约数是102. 更相减损之术:因为两数皆为偶数,首先除以2得到867,408,再求867与408的最大公约数.(867,408)(459,408)(51,408)(51,357) (51,306)(51,255)(51,204)(51,153)(51,102)(51,51). 1 734与816的最大公约数是512=102. 反思感悟用等值算法(更相减损之术)求两个数的最大公约数时,当大数减小数的差恰好等于小数时停止算法,这时的小数或差即所求最大公约数.用辗转相除法求两个数的最大公约数时,当大数除以小数的余数能整除这个小数时停止算法,这个余数即所求两数的最大公约数.,探究一,探究二,探究三,易错辨析,变式训练1(1)用更相减损之术求36与135的最大公约数,需做减法的次数是 . 解析:(135,36)(99,36)(63,36)(27,36)(27,9)(18,9) (9,9),故共进行了6次减法运算. 答案:6 (2)求140与76的最大公约数. 解:方法一)利用更相减损之术. (140,76)(64,76)(64,12)(52,12)(40,12)(28,12)(16,12)(4,12)(4,8)(4,4). 140与76的最大公约数为4. (方法二)利用辗转相除法. (140,76)(64,76)(64,12)(4,12). 140与76的最大公约数为4.,探究一,探究二,探究三,易错辨析,【例2】 求1 356和2 400的最小公倍数. 思路分析:两数的最小公倍数就是两数之积与此两数最大公约数的商. 即 解:2 400=1 3561+1 044, 1 356=1 0441+312, 1 044=3123+108, 312=1082+96, 108=961+12, 96=128. 1 356与2 400的最大公约数为12,探究一,探究二,探究三,易错辨析,反思感悟求两个正整数的最小公倍数要先求其最大公约数,两数的最小公倍数就是两数之积与两数最大公约数的商,并且这种方法也可以推广到n(n3,且nN+)个数的情况.,探究一,探究二,探究三,易错辨析,变式训练2求375与85的最小公倍数. 解:375=854+35,85=352+15,35=152+5,15=53+0, 375与85的最大公约数是5, 375与85的最小公倍数是375855=6 375.,探究一,探究二,探究三,易错辨析,【例3】 用秦九韶算法求多项式f(x)=x5+0.11x3-0.15x-0.04当x=0.3时的值. 思路分析:本题中有些项不存在,如x4,x2,要补上,写为0x4,0x2.将f(x)写为f(x)=(x+0)x+0.11)x+0)x-0.15)x-0.04.按从内到外的顺序依次计算多项式的值. 解:v0=1, v1=v00.3+0=0.3, v2=v10.3+0.11=0.2, v3=v20.3+0=0.06, v4=v30.3-0.15=-0.132, v5=v40.3-0.04=-0.079 6. 所以当x=0.3时,多项式的值为-0.079 6.,探究一,探究二,探究三,易错辨析,反思感悟1.应用秦九韶算法的关键是将一个n次多项式转化为n个一次多项式,转化要正确. 2.计算时要由内向外逐次计算,由于下一次计算需要用到上一次的计算结果,故应认真、细心,确保中间结果的准确性. 3.多项式中当有几项不存在(这些项的系数为0)时,应将这些项的系数看作0进行转化和计算.,探究一,探究二,探究三,易错辨析,1.若本例中条件不变,求当x=2时,多项式的值. 解:f(x)=(x+0)x+0.11)x+0)x-0.15)x-0.04,按从内到外的顺序,依次计算多项式的值, v0=1, v1=v02+0=2, v2=v12+0.11=4.11, v3=v22+0=8.22, v4=v32-0.15=16.29, v5=v42-0.04=32.54. 所以当x=2时多项式的值为32.54.,探究一,探究二,探究三,易错辨析,2.若本例中条件不变,改为求所用乘法和加法的次数是多少? 解:根据秦九韶算法,把多项式写成如下形式. f(x)=(x+0)x+0.11)x+0)x-0.15)x-0.04, 按从内到外的顺序,若x=0.3,则有 v0=1, v1=v00.3+0=0.3, v2=v10.3+0.11=0.2, v3=v20.3+0=0.06, v4=v30.3-0.15=-0.132, v5=v40.3-0.04=-0.079 6. 故f(0.3)是通过5个一次多项式的值得到的,所以进行了5次乘法和5次加法.,探究一,探究二,探究三,易错辨析,因对多项式改写不正确而致误 【典例】 已知多项式f(x)=3x5-2x2-5x4+3x3+x,则f(2)= . 错解原式改写为f(x)=(3x-2)x-5)x+3)x+1)x, 于是v0=3, v1=32-2=4, v2=42-5=3, v3=32+3=9, v4=92+1=19, v5=192=38. 故填38.,探究一,探究二,探究三,易错辨析,正解f(x)=3x5-2x2-5x4+3x3+x=3x5-5x4+3x3-2x2+x=(3x-5)x+3)x-2)x+1)x. 于是v0=3, v1=32-5=1, v2=12+3=5, v3=52-2=8, v4=82+1=17, v5=172=34. 所以当x=2时,多项式的值为34. 答案34,探究一,探究二,探究三,易错辨析,防范措施解决此类问题的关键是要严格按照秦九韶算法的递推公式结构,并且事先将多项式f(x)改写成所要求的形式,这样才能避免求值出错.对于本典例就是由于没有将f(x)按x的降幂排列而导致计算出错.,探究一,探究二,探究三,易错辨析,变式训练已知多项式f(x)=3x5-2x2-5x4+x,则f(-2)等于 . 解析:f(x)=3x5-5x4+0x3-2x2+x=(3x-5)x+0)x-2)x+1)x,于是v0=3, v1=3(-2)-5=-11, v2=(-11)(-2)+0=22, v3=22(-2)-2=-46, v4=(-46)(-2)+1=93, v5=93(-2)=-186. 所以当x=2时,多项式的值为-186. 答案:-186,1,2,3,4,5,1.用“等值算法”可求得204与85的最大公约数是( ) A.15 B.17 C.51 D.85 解析:204-85=119,119-85=34,85-34=51,51-34=17,34-17=17,204和85的最大公约数是17,故选B. 答案:B,1,2,3,4,5,2.我国数学家刘徽采用正多边形面积逐渐逼近圆面积的计算方法来求圆周率,其算法的特点为( ) A.运算速度快 B.能计算出的精确值 C.“内外夹逼” D.无限次地分割 答案:C,1,2,3,4,5,3.用秦九韶算法求多项式f(x)=x5+2x4+3x3+4x2+5x+6当x=7时的值时,需要做加法、乘法的次数分别是( ) A.6,6 B.5,5 C.5,4 D.4,5 答案:B,1,2,3,4,5,4.用秦九韶算法求多项式f(x)=0.5x5+4x4-3x2+x-1当x=3时的值,先算的是( ) A.33=9 B.0.535=121.5 C.0.53+4=5.5 D.(0.53+4)3=16.5 解析:把多项式表示成如下形式: f(x)=(0.5x+4)x+0)x-3)x+1)x-1,按递推方法,由内往外,先算0.5x+4的值,故选C. 答案:C,1,2,3,4,5,5.用秦九韶算法计算多项式f(x)=x6