[已解决]求最大公约数的程序没看懂，想大家帮助一下

justkingbo

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x

最佳答案

月排行榜 / 总排行榜

jackz007

2019-3-18 10:08:57

    这是著名的欧几里得算法也叫辗转相除法，是求取最大公约数的一种方法。
    首先，以 x 对 y 取余，如果余数为 0 那么 y 便是最大公约数，否则，让 y 成为 x，余数成为 y 继续上述取余操作，直到余数为零。

1. def gcd(x, y):
   
2.     while y:          # 如果除数（同时，也是前一次取余操作的余数） y 不为零就继续循环
   
3.         t = x % y     # x 对 y 取余
   
4.         x = y         # 准备下一次循环，除数 y 成为新被除数 x
   
5.         y = t         # 准备下一次循环，余数 t 成为新除数 y
   
6. 
   
7.     return x          # 返回除数 y 也就是最大公约数

复制代码

    请参考百度百科 https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%B7%E7%AE%97%E6%B3%95

跳转到最佳答案楼层

heidern0612

当y不为零的时候，t = x%y的求余，x = y , y =t, 再跳回t= x%y ……反复执行上述操作。

jackz007

    这是著名的欧几里得算法也叫辗转相除法，是求取最大公约数的一种方法。
    首先，以 x 对 y 取余，如果余数为 0 那么 y 便是最大公约数，否则，让 y 成为 x，余数成为 y 继续上述取余操作，直到余数为零。

1. def gcd(x, y):
   
2.     while y:          # 如果除数（同时，也是前一次取余操作的余数） y 不为零就继续循环
   
3.         t = x % y     # x 对 y 取余
   
4.         x = y         # 准备下一次循环，除数 y 成为新被除数 x
   
5.         y = t         # 准备下一次循环，余数 t 成为新除数 y
   
6. 
   
7.     return x          # 返回除数 y 也就是最大公约数

复制代码

    请参考百度百科 https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%B7%E7%AE%97%E6%B3%95

justkingbo

谢谢jackz007的解释，也谢谢heidern0612