1.3算法案例(一)【明目标、知重点】1理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析2了解秦九韶算法及利用它计算提高计算效率的本质3对简单的案例能设计程序框图并写出算法程序【填要点、记疑点】1辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法(2)辗转相除法的算法步骤第一步，给定两个正整数m，n(mn)第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步2更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数3秦九韶算法把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：(anxan1)xan2)xa1)xa0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0这样，求n次多项式f(x)的值就转化为求n个一次多项式的值【探要点、究所然】情境导学在小学，我们已经学过求最大公约数的知识，利用找公约数的方法来求最大公约数如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它 们的最大公约数？比如求8 251与6 105的最大公约数？这就是我们这一堂课所要探讨的内容探究点一辗转相除法思考118与30的最大公约数是多少？你是怎样得到的？答先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数由于，所以，18与30的最大公约数是236.问题如何求两个正数8 251和6 105的最大公约数？思考2对于8 251与6 105这两个数，由于其公有的质因数较大，利用小学的方法求最大公约数就比较困难注意到8 2516 10512 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？答显然8 251的最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数思考3又6 1052 14621 813，同理，6 105与2 146的公约数和2 146与1 813的公约数相等重复上述操作，你能得到8 251与6 105这两个数的最大公约数吗？答8 2516 10512 146，6 1052 14621 813，2 1461 8131333，1 8133335148，333148237，1483740.最后的除数37是148和37的最大公约数，也是8 251与6 105的最大公约数反思与感悟上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法思考4(1)用辗转相除法可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来设计算法？其算法步骤如何设计？(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？(3)如果用当型循环结构设计算法，正整数m，n的最大公约数的程序框图和程序分别如何表示？答(1)用循环结构设计算法，算法如下：第一步，给定两个正整数m，n(mn)第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步(2)程序框图：程序：INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND探究点二更相减损术思考1设两个正整数mn，若mnk，则m与n的最大公约数和n与k的最大公约数相等反复利用这个原理，可求得98与63的最大公约数为多少？答由于63不是偶数，把98和63以大数减小数，并辗转相减，得986335，633528，35287，28721，21714，1477.可知98与63的最大公约数为7.小结上述求两个正整数的最大公约数的方法称为更相减损术思考2(1)用更相减损术可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来构造算法？其算法步骤如何设计？答(1)用循环结构设计算法，算法如下：第一步，任意给定两个正整数m，n(mn)第二步，计算mn所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示第四步，若mn，则m，n的最大公约数等于m；否则，返回第二步(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？答程序框图：程序：INPUT m,nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND例1分别用辗转相除法和更相减损术求261和319的最大公约数解辗转相除法：3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.更相减损术：31926158，26158203，20358145，1455887，875829，582929，29290，所以319与261的最大公约数是29.反思与感悟1.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数2利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个正整数是否都是偶数若是，用2约简也可以不除以2，直接求最大公约数，这样不影响最后结果跟踪训练1用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果解803628，36844,8420，即80与36的最大公约数是4.验证：80240362184022018292091111929277255233212111224所以80与36的最大公约数为4.探究点三秦九韶算法的基本思想思考1怎样计算多项式f(x)x5x4x3x2x1当x5时的值呢？统计所做的计算的种类及计算次数分别是什么？答f(5)55545352513 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算思考2我们把多项式变形为f(x)(x1)x1)x1)x1)x1，再统计一下计算当x5时的计算的种类及计算次数分别是什么？答从里往外计算仅需4次乘法和5次加法运算即可得出结果小结思考2中的计算比问题1中的计算显然少了6次乘法运算这种算法就叫秦九韶算法一般地，f(x)anxnan1xn1an2xn2a1xa0(anxn1an1xn2an2xn3a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值例2已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值解将f(x)改写为f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72 826.2；v52 826.250.814 130.2.当x5时，多项式的值等于14 130.2.反思与感悟秦九韶算法步骤：跟踪训练2用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值解f(x)(7x6)x5)x4)x3)x2)x1)x所以有v07，v173627，v2273586，v38634262，v426233789，v5789322 369，v62 369317 108，v77 108321 324.故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21 324.【当堂测、查疑缺】1辗转相除法与更相减损术是求最大公约数的常用方法，从计算结果形式上看，辗转相除法以_得到结果，更相减损术则以_而得到结果答案相除余数为零减数与差相等2用辗转相除法求85与51的最大公约数时，需要做除法的次数为_答案3解析8551134，5134117，341720.3已知f(x)2x3x3，用秦九韶算法求当x3时v2的值解f(x)2x3x32x30x2x3(2x0)x1)x3，v02，v12306，v263119.【呈重点、现规律】1辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数2更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数3用秦九韶算法求多项式f(x)当xx0的值的思路为改写；计算；结论f(x0)vn.课