- 2021-07-01 发布 |
- 37.5 KB |
- 8页
申明敬告: 本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
文档介绍
2020届二轮复习算法案例教案(全国通用)
板块三.算法案例 知识内容 1.更相减损术——求两个整数的最大公约数的算法 如何找到一种算法,对任意两个正整数都能快速地求出它们的最大公约数呢? 更相减损术的步骤: 以两个数中较大的数减去较小的数,以差数和较小的数构成一对新的数,对这一对数再用大数减小数,以同样的操作一直做下去,直到产生一对相等的数,此数就是这两个数的最大公约数. 等值算法:用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”,用等值算法可以求任意两个正整数的最大公约数. <教师备案> 《九章算法》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数.以具体的例子来说明更相减损术求最大公约数的原理: 以求和的最大公约数为例: , 每次操作后得到的两个数与前两个数的最大公约数相同,而且逐渐减少,故总能得到相等的两个数,即为所求的最大公约数. 2.辗转相除法 又称欧几里得算法,是由欧几里得在公元前300年左右首先提出来的求两个数的最大公约数的算法。 辗转相除法的步骤: 对于给定的两个数,以其中较大的数除以较小的数得到一个余数,将较小的数与余数看成一对新的数,重复上面的步骤,直到余数为零为止,此时上一步中较小的数即为所求的最大公约数。 以求和的最大公约数为例: ,故即为所求。 3.秦九韶算法——求多项式的值的算法 对于任意一个元的多项式,如何更快地计算它在某点所取到的值? 秦九韶算法: 已知一个多项式函数,计算多项式在某点处的函数值的一种算法,是我国古代数学家秦九韶提出的, 具体如下. 对任意一个元多项式, 改写成如下形式: , 求多项式的值时,先计算最内层括号内的一次多项式的值,即, 然后由内向外逐层计算一次多项式的值,即,,,. 这样,求一个次多项式的值,就转化为求个一次多项式的值. 令,则递推公式为,其中. 到目前为止,此算法仍然是世界上多项式求值的最先进的算法. 秦九韶算法与其它算法在计算量上面的比较:, ⑴直接求和法:先计算各个单项式的值,再把它们相加, 乘法次数为,加法次数; ⑵逐项求和法:先计算的各项幂的值,再分别相乘,计算幂值需要乘法次,将幂值与多项式系数相乘需要乘法次,故共需要乘法次,加法次. 此方法对直接求和法有所改进,但仍然比秦九韶算法计算量大很多. ⑶秦九韶算法:计算量仅为乘法次,加法次. 典例分析 题型一:辗转相除法与更相减损术 【例1】 我国古代数学发展一直处于世界领先水平,特别是宋、元时期的“算法”,其中可以同欧几里德辗转相除法相媲美的是 . 【考点】辗转相除法与更相减损术 【难度】1星 【题型】填空 【关键词】无 【解析】 【答案】更相减损术. 【例2】 用更相减损术求与的最大公约数. 【考点】辗转相除法与更相减损术 【难度】1星 【题型】解答 【关键词】无 【解析】 ,故与的最大公约数为. 【答案】 【例3】 用辗转相除法计算和的最大公约数时,需要做的除法次数是 ( ) A.1 B.2 C.3 D.4 【考点】辗转相除法与更相减损术 【难度】1星 【题型】选择 【关键词】无 【解析】 ,,故只需要两步计算. 【答案】B 【例4】 分别用自然语言、程序框图描述等值算法,并写出等值算法的程序. 【考点】辗转相除法与更相减损术 【难度】2星 【题型】解答 【关键词】无 【解析】 自然语言: S1:输入两个正整数; S2:如果不等于,则执行第三步(S3);否则转到第五步(S5); S3:把的差赋予; S4:如果,则把赋予,把赋予;否则把赋予,执行第二步(S2); S5:输出最大公约数. 程序(A版Basic语言): INPUT (“a,b=”);a,b WHILE a<>b IF a>b THEN a=a-b ELSE b=b-a END IF WEND PRINT b END 程序(B版Scilab程序语言): a=input(“a=”); b=input(“b=”); while a<>b if a>b a=a-b; else b=b-a; end end print(%io(2),b) 程序框图如下: 【答案】 【例1】 求两个数的最大公约数还有一种方法叫辗转相除法,即对于任意两个正整数,用两个数中的较大的数除以较小的数,再将所得的商与较小的数组成一组新的数,用同样的方法处理,一直到所得到的两个数呈倍数关系,这时所得的较小的数即为所求的最大公约数. 如:求与的最大公约数: ,余数为,考虑和,此时有,考虑和,它们有倍数关系,故最大公约数为. 请写出利用辗转相除法求任意两个正整数的最大公约数的算法步骤,对应的程序框图以及程序. 【考点】辗转相除法与更相减损术 【难度】2星 【题型】解答 【关键词】无 【解析】 S1:输入两个正整数; S2:计算除以所得的余数; S3:如果,则执行S4,否则转到S6; S4:把赋予,把赋予; S5:执行S2; S6:输出. 辗转相除法(B版)程序: a=input(“a=”); b=input(“b=”); r=1; while r<>0 r=mod(a,b); a=b; b=r; end print(%io(2),b) //r=mod(a,b)的含义是r为a除以b的余数. 辗转相除法(A版)程序: INPUT (“a,b=”);a,b DO r=a MOD b a=b b=r LOOP UNTIL r=0 PRINT b END // r=a MOD b的含义是r为a除以b的余数 【答案】 【例1】 分别用辗转相除法与更相减损术求与的最大公约数,并且由此比较这两种算法. 【考点】辗转相除法与更相减损术 【难度】2星 【题型】解答 【关键词】无 【解析】 更相减损术: 故它们的最大公约数为. 辗转相除法: ;;故它们的最大公约数为. 联系:都是求最大公约数的方法; 区别:①计算上辗转相除法以除法为主,更相减损术以减法为主; ②计算次数上,辗转相除法计算次数相对较少,特别是当两个数差别较大时区别明显; ③从结果输出的时候看,辗转相除法当“余数为”时输出“除数”,更相减损术当“差和减数相等”时输出“差”. 【答案】 【例1】 分别用更相减损术与辗转相除法求和的最大公约数,并写出用等值算法计算的程序与程序框图. 【考点】辗转相除法与更相减损术 【难度】2星 【题型】解答 【关键词】无 【解析】 更相减损术: , 故它们的最大公约数为; 辗转相除法: ;;; 故它们的最大公约数为; 等值算法的程序(B版): a=153;b=119; while a<>b if a>b a=a-b; else b=b-a; end end print(%io(2),b) 等值算法的程序(A版): a=153 b=119 while a<>b if a>b then a=a-b else end if wend print b 程序框图 【答案】 题型二:秦九韶算法 【例1】 用秦九韶算法求次多项式,当时,求需要算乘方、乘法、加法的次数分别为( ) A. B. C. D. 【考点】秦九韶算法 【难度】2星 【题型】选择 【关键词】无 【解析】 【答案】D 【例2】 用秦九韶算法计算多项式在时的值. 【考点】秦九韶算法 【难度】2星 【题型】解答 【关键词】无 【解析】 ; ,; ,; ,; ,; ,; ,. ∴. 【答案】 【例3】 已知次多项式.如果在一次算法中,计算的值需要次乘法,计算的值共需次运算(次乘法,次加法),那么计算 的值共需要______次运算. 【考点】秦九韶算法 【难度】2星 【题型】填空 【关键词】2018,北京,高考 【解析】 次运算. 【答案】 【例1】 设计利用秦九韶算法计算次多项式当时的值的程序框图. 【考点】秦九韶算法 【难度】2星 【题型】解答 【关键词】无 【解析】 程序框图如下: 【答案】 【例2】 写出用秦九韶算法计算任一个元多项式在某点的值的程序,以及对应的程序框图. 【考点】秦九韶算法 【难度】2星 【题型】解答 【关键词】无 【解析】 程序(B版): x=input(“x=”); n=input(“n=”); a(0)=input(“a(0)=”); a(1)=input(“a(1)=”); … a(n)=input(“a(n)=”); i=1; v=a(n); while i<=n v=v*x+a(n-i); i=i+1; end print(%io(2),v) 程序框图: 【答案】查看更多