12《算法案例1》（新人教A版必修3）.ppt

v主讲老师 潘学国第一课时第一课时 1、研究一个实际问题的算法，主要、研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面从算法步骤、程序框图和编写程序三方面展开展开.在程序框图中算法的基本逻辑结构在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？在程序设计中基本的算法语句有哪几种？有哪几种？ 2、“求两个正整数的最大公约数求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算决办法，我们以此为案例，对该问题的算法作一些探究法作一些探究.问题提出问题提出思考思考1:18与与30的最大公约数是多少？你是的最大公约数是多少？你是怎样得到的？怎样得到的？ 先用两个数公有的质因数连续去除，先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数所有的除数连乘起来即为最大公约数. 辗转相除法辗转相除法1823091535318与与30的最大公约的最大公约数是数是23=6.短除法短除法思考思考2:对于对于8251与与6105这两个数，由于其这两个数，由于其公有的质因数较大，利用上述方法求最大公有的质因数较大，利用上述方法求最大公约数就比较困难。那么，有其它解决的公约数就比较困难。那么，有其它解决的办法吗办法吗?注意到注意到8251=61051+2146，那，那么么8251与与6105这两个数的公约数和这两个数的公约数和6105与与2146的公约数有什么关系？的公约数有什么关系？ 相等相等.思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+2146，6105=21462+1813，最大公约数是最大公约数是37.思考思考4：什么是辗转相除法（欧几里得算什么是辗转相除法（欧几里得算法）？法）？ 所谓辗转相除法，就是对于给定的两个数，所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。这种算法是数就是原来两个数的最大公约数。这种算法是由欧几里得在公元前由欧几里得在公元前300年左右首先提出的，年左右首先提出的，因而又叫欧几里得算法。因而又叫欧几里得算法。练习：练习： 用辗转相除法求用辗转相除法求225和和135的的最大公约数。最大公约数。225=1351+90135=901+4590=452+0 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 练习练习2 2：利用辗转相除法求两数利用辗转相除法求两数40814081与与2072320723的最大公约数的最大公约数. . (53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0. 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止停止的步骤，这实际上是一个循环结构。的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = nqr用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否否思考思考5：辗转相除法中的关键步骤是那种逻辑结构？辗转相除法中的关键步骤是那种逻辑结构？思考思考6:上述求两个正整数的最大公约数的方法上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法称为辗转相除法或欧几里得算法.一般地，用辗一般地，用辗转相除法求两个正整数转相除法求两个正整数m，n的最大公约数，可的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如以用什么逻辑结构来构造算法？其算法步骤如何设计？何设计？ 第一步，给定两个正整数第一步，给定两个正整数m，n(mn).第二步，计算第二步，计算m除以除以n所得的余数所得的余数r. 第三步，第三步，m=n，n=r.第四步，若第四步，若r=0，则，则m，n的最大公约数的最大公约数等等 于于m；否则，返回第二步；否则，返回第二步. 思考思考7:该算法的程序该算法的程序框图如何表示？框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考8:该程序框图对应的程序如何该程序框图对应的程序如何表述？表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考9: 如果用当型循环结构构造算如果用当型循环结构构造算法，则用辗转相除法求两个正整数法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分的最大公约数的程序框图和程序分别如何表示？别如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则，则m与与n的最大公约数和的最大公约数和n与与k的最大公约数的最大公约数相等相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，最大公约数是最大公约数是7.更相减损术更相减损术思考思考2:上述求两个正整数的最大公约数的上述求两个正整数的最大公约数的方法称为方法称为更相减损术更相减损术.一般地，用更相减损一般地，用更相减损术求两个正整数术求两个正整数m，n的最大公约数，可的最大公约数，可以用什么逻辑结构来构造算法？其算法步以用什么逻辑结构来构造算法？其算法步骤如何设计？骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m，n(mn). 第二步，计算第二步，计算m-n所得的差所得的差k. 第三步，比较第三步，比较n与与k的大小，其中大者用的大小，其中大者用m表表 示，小者用示，小者用n表示表示. 第四步，若第四步，若m=n，则，则m，n的最大公约数等于的最大公约数等于 m；否则，返回第二步；否则，返回第二步. 思考思考3:该算法的该算法的程序框图程序框图如何表示？如何表示？开始开始输入输入m，nnk？m=n是是输出输出mm=n？k=m-n是是n=km=k否否否否结束结束开始开始输入输入m，nnk？m=n是是输出输出mm=n？k=m-n是是n=km=k否否否否结束结束INPUT m，nLOOP UNTIL m=nk=m-nIF nk THENm=nn=kELSEm=kEND IFPRINT mENDDOWHILE语句语句INPUT m，nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m-n是是否否n=km=k否否 可半者半之，不可半者，副置分母、子之数，以少减多，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。更相减损，求其等也，以等数约之。第一步，任意给定两个正整数；判断他们是否都是偶数。第一步，任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步，以较大的数减较小的数，接着把所得的差与较小第二步，以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。减数和差相等为止，则这个等数就是所求的最大公约数。（1）、）、九章算术九章算术中的更相减损术：中的更相减损术：背景介绍：（2）、现代数学中的更相减损术：）、现代数学中的更相减损术：INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFk=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m- nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd 例例1：分别用辗转相除法和更相减分别用辗转相除法和更相减损术求损术求168与与93的最大公约数的最大公约数. 辗转相除法：辗转相除法：168=931+75， 93=751+18， 75=184+3， 18=36+0.典例剖析典例剖析更相减损术更相减损术: : 168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3. 例例2：求求325，130，270三个数的最大三个数的最大公约数公约数. 因为因为325=1302+65，130=652，所以所以325与与130的最大公约数是的最大公约数是65. 因为因为270=654+10，65=106+5，10=52，所以，所以65与与270最大公约数是最大公约数是5. 故故325，130，270三个数的最大公约三个数的最大公约数是数是5.课时小结课时小结: : 1、辗转相除法，就是对于给定的两个正整数，、辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数即为原来两个数的最大公约数. 2、更相减损术，就是对于给定的两个正整数，、更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的小的数相等，此时相等的两数即为原来两个数的最大公约数最大公约数.课时小结课时小结: :比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到。差相等而得到。1： P45 练习练习12： P48 A组组 13：资料：资料作业布置作业布置