课程内容

《算法案例—辗转相除法与更相减损术》
知识探究（一）：辗转相除法
思考1：18与30的最大公约数是多少？你是怎样得到的？
思考2：8251与6105的最大公约数是多少？
思考3：注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？
又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等。重复上述操作，你能得到8251与6105这两个数的最大公约数吗？
  8251=6105×1+2146
  6105=2146×2+1813
  2146=1813×1+333
  1813=333×5+148
  333=148×2+37
  148=37×4+0
所以，37是148和37的最大公约数，也就是8251和6105的最大公约数。
上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法。
思考4：一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
思考5：该算法的程序框图如何表示？
思考6：该程序框图对应的程序如何表述？
知识探究（二）：更相减损术
思考1：设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等。反复利用这个原理，可求得98与63的最大公约数为多少？
  98-63=35
  63-35=28
  35-28=7
  28-7=21
  21-7=14
  14-7=7
上述求两个正整数的最大公约数的方法称为更相减损术。
思考2：一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
思考3：该算法的程序框图如何表示？
思考4：该程序框图对应的程序如何表述？
典型例题
例：分别用辗转相除法和更相减损术求168与93的最大公约数。