搜索
湖南省长沙市一中卫星远程学校1.3算法案例高中新课程数学必修③第一课时湖南省长沙市一中卫星远程学校问题提出1.两种条件语句的一般格式分别是什么？格式1:IF条件THEN语句体ENDIF格式1:IF条件THEN语句体ENDIF格式2:IF条件THEN语句体1ELSE语句体2ENDIF格式2:IF条件THEN语句体1ELSE语句体2ENDIF湖南省长沙市一中卫星远程学校2.两种循环语句的一般格式分别是什么？DO循环体LOOPUNTIL条件WHILE条件循环体WEND循环体循环体满足条件？满足条件？是是否否湖南省长沙市一中卫星远程学校问题提出1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.湖南省长沙市一中卫星远程学校思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？湖南省长沙市一中卫星远程学校2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？湖南省长沙市一中卫星远程学校思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.湖南省长沙市一中卫星远程学校思考6:该程序框图对应的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTm开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否开始开始输入m，n输入m，n求m除以n的余数r求m除以n的余数rm=nm=nn=rn=rr=0？r=0？是输出m是输出m结束结束否否湖南省长沙市一中卫星远程学校思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？湖南省长沙市一中卫星远程学校开始m=nn0？结束是n=rINPUTm，nWHILEn0r=mMODnm=nn=rWENDPRINTmEND求m除以n的余数r求m除以n的余数r否输出m否输出m输入m，n输入m，n湖南省长沙市一中卫星远程学校优化设计P37页例1(1):用辗转相除法求840与1785的最大公约数.湖南省长沙市一中卫星远程学校知识探究（二）:更相减损术98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？湖南省长沙市一中卫星远程学校思考2:上述求两个正整数的最大公约数的方法称为更相减损术．一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.湖南省长沙市一中卫星远程学校思考4:该程序框图对应的程序如何表述？开始输入m，nnk？m=n是输出m结束m≠n？k=m-n是否n=km=k否思考4:该程序框图对应的程序如何表述？开始输入m，nnk？m=n是输出m结束m≠n？k=m-n是否n=km=k否开始开始输入m，n输入m，nnk？nk？m=n是m=n是输出m输出m结束结束m≠n？m≠n？k=m-n是k=m-n是否否n=kn=km=km=k否否INPUTm，nWHILEmnk=m-nIFnkTHENm=nn=kELSEm=kENDIFWENDPRINTmEND湖南省长沙市一中卫星远程学校“更相减损术”在中国古代数学专著《九章算术》中记述为：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.湖南省长沙市一中卫星远程学校理论迁移例1分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.湖南省长沙市一中卫星远程学校更相减损术: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=130×2+65，130=65×2，所以325与130的最大公约数是65.因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.故325，130，270三个数的最大公约数是5.湖南省长沙市一中卫星远程学校优化设计P37页例1(2):用更相减损术求612与468的最大公约数.湖南省长沙市一中卫星远程学校小结作业1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.