2017-2018学年高中数学第一章算法初步1.3中国古代数学中的算法案例课件新人教B版必修.ppt

-*- 1.3　中国古代数学中的算法案例 1.理解中国古代三个问题(求两个正整数的最大公约数、割圆术、求多项式函数值)的算法. 2.注意体会“更相减损之术”与“辗转相除法”的差异,以及秦九韶算法在求多项式函数值上的优越性. 1.求两个正整数最大公约数的算法 (1)“等值算法”在我国古代也称为更相减损之术,它是用来求两个正整数的最大公约数的方法,其基本过程是:对于给定的两个数,用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的两数相等为止,则所得数就是所求的最大公约数. (2)辗转相除法(即欧几里得算法):是用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是所求的最大公约数. 归纳总结1.用“等值算法”求两数的最大公约数时,是当大数减去小数的差恰好等于小数时停止减法,这时的小数就是要求的两数的最大公约数. 2.求三个以上(含三个数)的数的最大公约数时,可依次通过求两个数的最大公约数与第三个数的最大公约数来求得. 【做一做1】 用辗转相除法求168与72的最大公约数,要做n次除法运算,那么n为(　　) 　　　　　 　　　　　 　　　 A.2 B.3 C.4 D.5 答案:A 2.割圆术 割圆术是我国魏晋时期的数学家刘徽在注《九章算术》中采用正多边形面积逐渐逼近圆面积的算法计算圆周率π的一种方法.他的思想后来又得到祖冲之的推进和发展,计算出的圆周率的近似值在世界上很长时间里处于领先地位. 【做一做2】 用圆内接正多边形逼近圆,得到的圆周率的值总是(　　) A.大于等于π的实际值 B.大于π的实际值 C.等于π的实际值 D.小于π的实际值 解析:用割圆术求出的是π的不足近似值. 答案:D 知识拓展1.秦九韶算法很多文献称之为霍纳算法. 2.用秦九韶算法计算多项式的值,关键是正确地将多项式改写,然后由内向外依次计算求得. 1.辗转相除法与更相减损之术的异同 剖析:相同点:①都是求最大公约数的方法.②更相减损之术的理论依据为:由m-n=r,得m=n+r,可以看出,m,n与n,r有相同的公约数;辗转相除法的理论依据是:由m=nq+r可以看出,m,n和n,r有相同的公约数,即二者的“算理”相似. 不同点:①更相减损之术进行的是减法运算,辗转相除法进行的是除法运算,计算次数上辗转相除法计算次数相对较少.②结果上,辗转相除法体现结果是以相除余数为0得到,而更相减损之术则以减数与差相等而得到. 3.教材中的“探索与研究” 古希腊求两个正整数的最大公约数的方法是辗转相除法(即欧几里得算法):用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.以求288和123的最大公约数为例,操作如下: (288,123)→(42,123)→(42,39)→(3,39). 想一想这种算法的道理.试着编写程序在计算机上实现. 剖析:辗转相除法求正整数a,b(ab)的最大公约数的步骤是:计算出a÷b的余数r,若r=0,则b为a,b的最大公约数;若r≠0,则把前面的除数b作为新的被除数,把余数r作为新的除数,继续运算,直到余数为零,此时的除数即为a,b的最大公约数. 从其算法思想我们可以看出,辗转相除法的基本步骤是用较大的数(用a表示)除以较小的数(用b表示),得到除式:a=nb+r(0≤rb). 由于这是一个反复执行的步骤,且执行的次数由余数r是否等于0决定,所以我们可以把它看做一个循环体,用循环结构就可以来实现其算法. 程序略. 题型一 题型二 题型三 题型一 题型二 题型三 反思用更相减损之术求解时,如果所给的两个正整数都是偶数时,那么一般先把这两个正整数除以2,最终把这两个正整数化成不都是偶数的情况,然后再用两数中较大的数减去较小的数,得到化简后两数的最大公约数,这时所求的最大公约数一定要注意:前面除了几个2,这时求出的最大公约数就要乘以几个2. 题型一 题型二 题型三 题型一 题型二 题型三 题型一 题型二 题型三 反思先求最大公约数,因为两数的最小公倍数就是两数之积与两数最大公约数的商,所以这种方法也可以推广到n(n≥3)个数的情况. 题型一 题型二 题型三 【变式训练2】 求396与270的最小公倍数. 解:用辗转相除法求396与270的最大公约数:(396,270)→(126,270)→(126,18),126=18×7,因此396与270的最大公约数为18,因此这两个数的最小公倍数为396×270÷18=5 940. 题型一 题型二 题型三 题型一 题型二 题型三 反思有的同学习惯于常规解法,可能会直接代入求解,但这种算法计算机在执行时要进行21次乘法和6次加法运算,而利用