文档：释疑解惑学算法-“黄冈杯”一等奖

释疑解惑学算法开始r开始r≥?输出rn=n+1n=1结束否是输入rn≤9？是否图1疑问1：下面的结构是哪种循环结构?

原题是这样的：某高中男子体育小组的50m跑成绩（单位：s）为：

，，，，，，，，.设计一个算法，从这些成绩中搜索小于的成绩，并画出成绩框图。开始r开始r≥?输出rn=n+1n=1结束是否输入rn>9？是否图2解答：上述的程序框图，其功能是从输入的9个成绩中，输出成绩小于的成绩，从表面上看也是可以执行的，但它是否符合直到型循环结构或当型循环结构呢？如果是直到型循环结构，应该是在“满足条件时终止循环体”，显然不符合；如果是当型循环结构则应该在“每次执行循环体前进行条件的判断”，满足条件时执行循环体，这样我们就应该将循环体写在“边上”，也不符。所以这里的循环结构，既不是当型也不是直到型。

如果是直到型循环结构我们可以改为下面的程序框图，如图2开始r≥?开始r≥?输出rn=n+1n=1结束否是输入rn≤9？否是图3程序框图的设计是我们学习算法程序语句的基础，所以我们在学习程序框图时，要注重两种循环结构的辨析，才能准确的完成程序的设计。疑问2：在用辗转相除法求解8251和6105的最大公约数时，为什么“8251与6105的公约数和6105与2146的公约数相同”？解答：这个问题是初等数论中的整除问题，假设d为8251与6105的公约数，即d|8251(d整除8251记作d|8251)且d|6105,则由于8251=6105+2146可知2146=8251-6105-----------------------(*)则d|(8251-6105)，即d|2146；反过来，假设d为6105与2146的公约数，即d|6105且d|2146，则由于8251=6105+2146，则d|(6105+2146)，即d|8251.疑问3：在辗转相除法的算法分析中为什么没有先对m，n进行比较大小？解答：算法分析中，第一步是这样的：给定两个正整数m，n。这里实际上不用对m，n进行比较大小，如果程序在执行时，给定的m<n，将会“自动转化过来”，比如m=6105，n=8251，将有6105=8251×0+6105，执行完这步循环会继续执行8251=6105+2146，这样就实现了，两个数的“自动转化”。图4图4开始r>0?输出mr=1结束否是输入m,nn=rm=nr=mMODn解答：当型程序框图如图4。疑问5：在上面的当型结构中，为什么要赋r初值为0？解答：我们在较复杂的程序中进行两种循环结构的转化时，往往要给变量赋予初值，因为当型循环结构要求在每次执行循环体前都要对条件进行判断，而我们在判断前没有做任何工作，所以为了让循环得以执行，我们需要给r以初值。这里不是必须给r=0，而是给定r一个大于0的值就可以让程序继续执行。疑问6：辗转相除法与更相减损术存在什么必然联系？解答：我们以求98和63的最大公约数为例进行必要的说明，辗转相除法的解法是：98=63+3563=35+2835=28+728=7×4则7为98和63的最大公约数。更相减损术的解法是：98-63=35开始？开始？是否输出结束图535-28=728-7=2121-7=1414-7=7所以7是98和63的最大公约数。

通过以上的解法我们不难发现，两种算法的实质是一样的，只是辗转相除法是辗转相除，更相减损术是辗转相减，当因式相同时，辗转相除法能一步解决，而更相减损术则需要几步才能完成。这样看来，辗转相除法与更相减损术相比，要简单的多，可以省去很多的步骤。疑问7：如何准确的将包含循环结构的程序框图改写为程序？解答：首先应进行循环结构的判断，