算法案例学习教案

1、会计学1第一页，共22页。问题问题(wnt)提提出出t57301p2 1. 1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开. .在程序框图中算法的基本在程序框图中算法的基本(jbn)(jbn)逻辑结构有哪几种？在程序设计中基本逻辑结构有哪几种？在程序设计中基本(jbn)(jbn)的算法语句有哪几种？的算法语句有哪几种？ 2.“ 2.“求两个正整数的最大公约数求两个正整数的最大公约数”是数学中的一个基础性问题是数学中的一个基础性问题(wnt)(wnt)，它有各种解决办法，我们以此为案例，对该问题，它有各

2、种解决办法，我们以此为案例，对该问题(wnt)(wnt)的算法作一些探究的算法作一些探究. .第1页/共21页第二页，共22页。第2页/共21页第三页，共22页。知识探究（一）知识探究（一）:辗转辗转(zhnzhun)相除法相除法思考思考(sko)1:18(sko)1:18与与3030的最大公约数是多少？你是怎样得到的？的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得先用两个数公有的质因数连续去除，一直除到所得(su d)(su d)的商是互质数为止，然后把所有的除数连乘起来即为最大公约数的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. . 第3页/

3、共21页第四页，共22页。思考思考2:2:对于对于(duy)8251(duy)8251与与61056105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约数有什么关系？的公约数有什么关系？ 第4页/共21页第五页，共22页。思考思考3:3:又又6105=21466105=21462+18132+1813，同

4、理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公约数相等的公约数相等. .重复上述重复上述(shngsh)(shngsh)操作，你能得到操作，你能得到82518251与与61056105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462

5、+2+18131813，第5页/共21页第六页，共22页。思考思考4:4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法(sun f).(sun f).一般地，用辗转相除法求两个正整数一般地，用辗转相除法求两个正整数m m，n n的最大公约数，可以用什么逻辑结构来构造算法的最大公约数，可以用什么逻辑结构来构造算法(sun f)(sun f)？其算法？其算法(sun f)(sun f)步骤如何设计？步骤如何设计？ 第一步，给定第一步，给定( (i dni dn) )两个正整数两个正整数m m，n(mn).n(mn).第

6、二步，计算第二步，计算(j sun)m(j sun)m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步. . 第6页/共21页第七页，共22页。思考思考5:5:该算法该算法(sun f)(sun f)的程序框图如何表示？的程序框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否第7页/共21页第八页，共22页。思考思考6:6:该程序框图对应的程序如何该程序框图对应

7、的程序如何(rh)(rh)表述？表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否第8页/共21页第九页，共22页。思考思考7:7:如果用当型循环结构构造算法，则用辗转如果用当型循环结构构造算法，则用辗转(zhnzhun)(zhnzhun)相除法求两个正整数相除法求两个正整数m m，n n的最大公约数的程序框图和程序分别如何表示？的最大公约数的程序框

8、图和程序分别如何表示？第9页/共21页第十页，共22页。开始开始输入输入m，n求求m除以除以n的余数的余数rm =nn 0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND第10页/共21页第十一页，共22页。知识知识(zh shi)探究（二）探究（二）:更相更相减损术减损术 思考思考1:1:设两个正整数设两个正整数mnmn，若，若m-n=km-n=k，则，则m m与与n n的最大公约数和的最大公约数和n n与与k k的最大公约数

9、相等的最大公约数相等. .反复反复(fnf)(fnf)利用这个原理，可求得利用这个原理，可求得9898与与6363的最大公约数为多少？的最大公约数为多少？98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，第11页/共21页第十二页，共22页。思考思考2:2:上述求两个正整数的最大公约数的方法称为上述求两个正整数的最大公约数的方法称为(chn wi)(chn wi)更相减损术更相减损术. .一般地，用更相减损术求两个正整数一般地，用更相减损术求两个正整数m m，

10、n n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定第一步，给定( (i dni dn) )两个正整数两个正整数m m，n(mn). n(mn). 第二步，计算第二步，计算(j sun)m-n(j sun)m-n所得的所得的差差k. k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步. .

11、 第12页/共21页第十三页，共22页。思考思考(sko)3:(sko)3:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m- -n是是否否n=km=k否否第13页/共21页第十四页，共22页。思考思考4:4:该程序该程序(chngx)(chngx)框图对应的程序框图对应的程序(chngx)(chngx)如何表述？如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND

12、 IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m- -n是是否否n=km=k否否第14页/共21页第十五页，共22页。“更相减损术更相减损术”在中国在中国(zhn u)(zhn u)古代数学专著九章算术中记述为：古代数学专著九章算术中记述为： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之. . 第15页/共21页第十六页，共22页。理论理论(lln)迁移迁移 例1 分别用辗转(zhnzhun)相除法

13、和更相减损术求168与93的最大公约数. 辗转辗转(zhnzhun)(zhnzhun)相除法：相除法：168=93168=931+751+75， 93=75 93=751+181+18， 75=18 75=184+34+3， 18=3 18=36.6.第16页/共21页第十七页，共22页。更相减损更相减损(jin sn)(jin sn)术术:168-93=75:168-93=75， 93-75=18 93-75=18， 75-18=57 75-18=57， 57-18=39 57-18=39， 39-18=21 39-18=21， 21-18=3 21-18=3， 18-3=15 18-3=1

14、5， 15-3=12 15-3=12， 12-3=9 12-3=9， 9-3=6 9-3=6， 6-3=3. 6-3=3.第17页/共21页第十八页，共22页。 例例2 2 求求325325，130130，270270三个数的最大公约数三个数的最大公约数. . 因为因为(yn wi)325=130(yn wi)325=1302+652+65，130=65130=652 2，所以，所以325325与与130130的最大公约数是的最大公约数是65. 65. 因为因为(yn wi)270=65(yn wi)270=654+104+10，65=1065=106+56+5，10=510=52 2，所以，

15、所以6565与与270270最大公约数是最大公约数是5. 5. 故故325325，130130，270270三个数的最大公约数是三个数的最大公约数是5.5.第18页/共21页第十九页，共22页。 1. 1.辗转相除法，就是辗转相除法，就是(jish)(jish)对于给定对于给定的两个正整数，用较大的数除以较小的数，若的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大为止，这时的较小的数即为原来两个数的最大公约数公约数. . 小结小结(xioji)作作业业 2. 2. 更相减损更相减损(jin sn)(jin sn)术，就是对于给术，就是对于给定的两个正整数，用较大的数减去较小的数，定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数的两数即为原来两个数的最大公约数. .第19页/共21页第二