2020届二轮复习算法案例教案(全国通用)

申明敬告: 本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

文档介绍

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)‎ 程序框图:‎ ‎【答案】‎
查看更多

相关文章

您可能关注的文档