辗转相除法与最大公约数,最小公倍数问题情境求18和30的最大公约数结论18和30的最大公约数为618和30的最小公倍数为90(牢记方法!)问题1求204与85的最大公约数问题2求8251与6105的最大公约数204与85的最大公约数是178251与6105的最大公约数是34辗转相除法:我们可以证明，对于任意两个正整数，上述步骤总可以在有限步之后完成，从而总可以用辗转相除的方法求出最大公约数算法设计:如何用辗转相除法找出两个正整数a,b的最大公约数？(1)结合问题1和问题2，应该利用什么结构实现该算法?（循环结构）(2)每一次循环中所进行的是什么样的运算？（求a÷b的余数）(3)下一次循环的输入整数应该是什么？循环何时结束？设a>b,a除以b的余数为r(b>r),则下一次循环的两个数为b,r.直到r=0为止.算法S1输入两个正整数a,b（a＞b）；S2若Mod（a,b）＝0，则输出最大公约数b，算法结束；否则rMod（a,b），ab，br，转S2．流程图伪代码Reada,bWhileMod(a,b)≠0rmod(a,b)abbrEndWhilePrintb思考：rmod(a,b)abbr能否改为abbmod(a,b)例1试画出求正整数a,b最小公倍数的流程图，并写出其伪代码。Reada,bcabWhileMod(a,b)≠0rMod(a,b)abbrEndWhilePrintc/b例2下面一段伪代码的目的是求10Reada,b20Ifa/b＝Int(a/b)ThenGoto7030ca－Int(a/b)×b40ab50bc60Goto2070PrintbA.求a,b的最小公倍数B.求a,b的最大公约数C.求a被b整除的商D.求b除以a的余数分析：解题关键就是：a－int(a/b)×b＝mod(a,b)回顾反思1．辗转相除法的算法；2．如何实现当型循环。
