第一章 1.3 算法案例2课时

返回1.3算法案例返回复习回顾1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？新课引入2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.返回知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.新课讲授18302915335故18与30的最大公约数为2x3=6返回思考2:对于8251与6105这两个数，由于数较大，利用上述方法求最大公约数就比较困难了.8251与6105的公约数和6105与2146的公约数有什么关系？注意到8251=6105×1+2146，相同又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作,你能得到8251与6105这两个数的最大公约数吗？8251=6105×1+2146，6105=2146×2+1813，2146=1813×1+333，1813=333×5+148，333=148×2+37，148=37×4+0.37上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.返回次数123456mnr8251和6105的最大公约数解:8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，37）=37关系式m=np+r中m,n,r得取值变化情况82516105214661052146214618131813333181333314814833337148370返回辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表示出右边的过程r=mMODnm=nn=rr=0?是否返回上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.第一步，给定两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？返回上述算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND返回思考：如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？开始输入m，nn0？否输出m结束是求m除以n的余数rm=nn=rINPUTm，nWHILEn0r=mMODnm=nn=rWENDPRINTmEND返回知识探究（二）:更相减损术思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数有什么关系？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，相等.反复利用这个原理，可求得：98与63的最大公约数为多少？7这种求两个正整数的最大公约数的方法称为更相减损术.用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.如何设计程序框图返回程序框图开始输入m，nnk？m=n是输出m结束m≠n？k=m-n是否n=km=k否INPUTm，nWHILEmnk=m-nIFnkTHENm=nn=kELSEm=kENDIFWENDPRINTmEND其对应的程序如何？程序“更相减损术”在中国古代数学专著《九章算术》中记述为:可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.返回（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数比较大时更适合用辗转相除法。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到的。〖辗转相除法与更相减损术的区别〗返回课程讲授：求最大公约数[例1]分别用辗转相除法和更相减损术求779与209的最大公约数．[解](1)辗转相除法：779＝209×3＋152，209＝152×1＋57，152＝57×2＋38，57＝38×1＋19，38＝19×2.所以，779与209的最大公约数为19.返回(2)更相减损术：779－209＝570，152－57＝95，570－209＝361,95－57＝38，361－209＝152,57－38＝19，209－152＝57,38－19＝19.所以779和209的最大公约数为19.返回[活学活用]用辗转相除法和更相减损术求1515与600的最大公约数，需要运算的次数分别为()A．4,15B．5,14C．5,13D．4,12答案：B返回解析：辗转相除法：1515＝600×2＋315；600＝315×1＋285,315＝285×1＋30,285＝30×9＋15,30＝15×2故最大公约数为15，且需计算5次．用更相减损术法：1515－600＝915,9－15－600＝315,600－315＝285，315－285＝30,285－30＝255,255－30＝225，225－30＝195,195－30＝165,165－30＝135,135－30＝105，105－30＝75,75－30＝45,45－30＝15,30－15＝15.故最大公约数为15，且需计算14次.答案：B返回思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.4+3+2+1=10次乘法运算，5次加法运算.（1）若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？（2）若计算f(x)=((((x+1)x+1)x+1)x+1)x+1的值，那么一共做了多少次乘法运算和多少次加法运算？4次乘法运算，5次加法运算.对比上述两种算法，显然第二种算法使得运算次数减少。课程讲授——秦九韶算法的基本思想返回利用第二种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由内向外逐层计算多项式的值，其算法步骤如何？这种求多项式值的方法称为秦九韶算法返回第一步，计算v1=anx+an-1.第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.…第n步，计算vn=vn-1x+a0.利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？至多n次n次在秦九韶算法中，记v0=an，那么第k步的算式是什么？返回思考2:在秦九韶算法中，记v0=an，那么第k步的算式是什么？0112…，n,,nkknkvavvxak返回[例2](1)已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算当x＝3时，v3的值为()A．27B．11C．109D．36秦九韶算法及其应用[答案]D返回[解析]将多项式改写成如下形式：f(x)＝((((x＋0)x＋2)x＋3)x＋1)x＋1，由内向外依次计算：v0＝1，v1＝1×3＋0＝3，v2＝3×3＋2＝11，v3＝11×3＋3＝36.[答案]D返回(2)用秦九韶算法求多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x，当x＝2时的值．[解]f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x，当x＝2时，有v0＝6，v1＝6×2＋5＝17，v2＝17×2＋4＝38，v3＝38×2＋3＝79，v4＝79×2＋2＝160，v5＝160×2＋1＝321，v6＝321×2＝642，故当x＝2时，多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x的值为642.返回[类题通法]秦九韶算法原理及注意事项(1)秦九韶算法的原理是v0＝an，vk＝vk－1x＋an－k，(k＝1,2，…，n)．(2)在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，那么下一步，一直到最后一步就会全部算错，同学们在计算这种题时应格外小心．返回[活学活用]用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是()A．6,6B．5,6C．5,5D．6,5解析：f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，所以需要进行6次乘法和6次加法.答案：A返回思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次项的系数an和x的值.第二步，令v=an，i=n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i≥0是否成立.若是，则返回第二步；否则，输出多项式的值v.如何设计程序框图课程讲授——秦九韶算法的程序设计返回程序框图开始输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否其对应的程序如何？程序INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi=0INPUT“ai=”；bv=v*x+bi=i-1WENDPRINTvEND返回例.阅读下列程序，说明它解决的实际问题是什么？INPUT“x=”；xn=0y=0WHLEn5y=y+(n+1)*x∧nn=n+1PRINTyWENDEND求多项式在x=a时的值？234()12345fxxxxx该算法中需进行几次乘法和加法运算返回知识点三：进位制[提出问题]问题1：今天是星期二，那么20天后是星期几？提示：20天后是星期一．问题2：每周七天，逢七便又是一循环，这与我们所学过的十进制，逢十进一是否有相似之处？提示：其实一周七天，与十进制一样，相当于逢七进一，是七进制论法．返回1．进位制(1)概念：进位制是为了而约定的记数系统，“满几进一”就是几进制．(2)基数：几进制的基数就是．计数和运算方便几返回2．不同进位制之间的互化(1)k进制化为十进制的方法：anan－1…a1a0(k)＝(an，an－1，…，a1，a0∈N,0＜an＜k,0≤an－1，…，a1，a0＜k)．(2)十进制化为k进制的方法——．an×kn＋an－1×kn－1＋…＋a1×k＋a0除k取余数返回[化解疑难]常见的进位制(1)二进制：①只使用0和1两个数字；②满二进一，如1＋1＝10.(2)八进制：①使用0,1,2,3,4,5,6,7八个不同的数字；②满八进一，如7＋1＝10.(3)十六进制：①使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10,11