9512.net
甜梦文库
当前位置:首页 >> >>

高中数学必修三1.3.1 辗转相除法与更相减损术、秦九韶算法(共32张PPT)课件_图文

欢迎来到数学课堂 1.3 算法案例 第一课时 辗转相除法 与更相减损术、秦九韶算法 知识能力目标引航 1.理解辗转相除法与更相减损术的含义,了解其执行过程,并会求最 大公约数. 2.掌握秦九韶算法的计算过程,了解它提高计算效率的实质,并会求 多项式的值. 3.进一步体会算法的基本思想. 1.辗转相除法与更相减损术 (1)辗转相除法. ①算法步骤: 第一步,给定两个正整数 m,n. 第二步,计算 m 除以 n 所得的余数 r. 第三步,m=n,n=r. 第四步,若 r=0,则 m,n 的最大公约数等于 m;否则返回第二步. ②程序框图如图所示. ③程序: INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END (2)更相减损术. 算法分析: 第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用 2 约简;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的差与较小的数 比较,并以大数减小数.继续这个操作,直到所得的差与减数相等为止, 则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约 数. 【做一做 1】用更相减损术求 294 和 84 的最大公约数时,第一 步是 . 解析:由于 294 和 84 都是偶数,先用 2 约简. 答案:用 2 约简 2.秦九韶算法 (1)概念:求多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 的值时,常用秦 九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法, 其实质是转化为求 n 个一次多项式的值,共进行 n 次乘法运算和 n 次加法运算.其过程是: 改写多项式为: f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a1)x+a0 =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=… =(…((anx+an-1)x+an-2)x+…+a1)x+a0. 设 v1=anx+an-1, v2=v1x+an-2, v3=v2x+an-3, …… vn=vn-1x+a0. (2)算法步骤: 第一步,输入多项式的次数 n、最高次项的系数 an 和 x 的值. 第二步,将 v 的值初始化为 an,将 i 的值初始化为 n-1. 第三步,输入 i 次项的系数 ai. 第四步,v=vx+ai,i=i-1. 第五步,判断 i 是否大于或等于 0.若是,则返回第三步;否则,输出 多项式的值 v. (3)程序框图如图所示. (4)程序: INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v=a i=n-1 WHILE i>=0 PRINT “i=”;i INPUT “ai=”;a v=vx+a i=i-1 WEND PRINT v END 【做一做 2】设计程序框图,用秦九韶算法求多项式的值,所选用 的结构是( ) A.顺序结构 B.条件结构 C.循环结构 D.以上都有 答案:D 1.更相减损术与辗转相除法的区别与联系 剖析:如表所示. 辗转相除法 更相减损术 ①以减法为主. ①以除法为主. ②两个整数的差值较大时,运 区 ②两个整数差值较大时运算 算次数较多. 别 次数较少. ③相减,差与减数相等得结果. ③相除余数为零时得结果 ④相减前要做是否都是偶数 的判断 联 系 ①都是求最大公约数的方法. ②二者的实质都是递归的过程. ③二者都要用循环结构来实现 2.秦九韶算法是比较先进的算法 剖析:同一个问题有多种算法,如果某个算法比其他算法的步骤 少,运算的次数少,那么这个算法就是比较先进的算法.判断算法是否 先进的一个重要标志就是运算的次数越少越好. 求多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 的值时,通常是先计算 anxn,进行 n 次乘法运算;再计算 an-1xn-1,进行 n-1 次乘法运算;这样继 续下去共进行 n+n-1+…+2+1=(2+1)(其计算方法以后学习)次乘法 运算,还需要进行 n 次加法运算,总共进行(2+1)+n 次运算. 但是用秦九韶算法时,改写多项式为 f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a1)x+a0 =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 …… =(…((anx+an-1)x+an-2)x+…+a1)x+a0. 先计算 v1=anx+an-1,需 1 次乘法运算,1 次加法运算; v2=v1x+an-2,需 1 次乘法运算,1 次加法运算; …… vn=vn-1x+a0,需 1 次乘法运算,1 次加法运算. 所以需进行 n 次乘法运算,n 次加法运算,共进行 2n 次运算. 由于 (+1) 2 + n -2n=(2-1)≥0,则(2+1)+n≥2n. 因此说秦九韶算法与其他算法相比运算次数少,秦九韶算法是 比较先进的算法. 题型一 求最大公约数 【例题 1】(1)用辗转相除法求 840 与 1785 的最大公约数; (2)用更相减损术求 612 与 468 的最大公约数. 分析:本题是关于辗转相除法和更相减损术的直接应用.辗转相 除法的操作是较大的数除以较小的数;更相减损术的操作是以大数 减小数. 解:(1)用辗转相除法求 840 和 1785 的最大公约数. 1785=840×2+105, 840=105×8. 所以 840 和 1785 的最大公约数是 105. (2)首先 612 和 468 都是偶数,所以用 2 约简,得到 306 和 234,还 是偶数,需要再用 2 约简,得到 153 和 117,最后用更相减损术计算得 153-117=36, 117-36=81, 81-36=45, 45-36=9, 36-9=27, 27-


学霸百科 | 新词新语

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图