[已解决]17课课后作业：最大公约数的问题

spacex_dragon

1. 编写一个函数，利用欧几里得算法（脑补链接）求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。

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

    return x
   
print(gcd(4, 6))

以上是小甲鱼原代码，但真心表示难以理解，望表达能力强、关爱小白人士帮我理下思路，感谢！

最佳答案

月排行榜 / 总排行榜

jackz007

2020-11-9 19:34:03

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

def gcd(x, y):
    while y:          # 如果除数（同时，也是前一次取余操作的余数） y 不为零就继续循环
        t = x % y     # x 对 y 取余
        x = y         # 准备下一次循环，除数 y 成为新被除数 x
        y = t         # 准备下一次循环，余数 t 成为新除数 y

    return x          # 返回除数 y 也就是最大公约数

    请参考百度百科 https://baike.baidu.com/item/%E6 ... 7%E7%AE%97%E6%B3%95

跳转到最佳答案楼层

liuzhengyuan

可以百度一下欧几里得算法（或辗转相除法）

jackz007

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

def gcd(x, y):
    while y:          # 如果除数（同时，也是前一次取余操作的余数） y 不为零就继续循环
        t = x % y     # x 对 y 取余
        x = y         # 准备下一次循环，除数 y 成为新被除数 x
        y = t         # 准备下一次循环，余数 t 成为新除数 y

    return x          # 返回除数 y 也就是最大公约数

    请参考百度百科 https://baike.baidu.com/item/%E6 ... 7%E7%AE%97%E6%B3%95

spacex_dragon

jackz007 发表于 2020-11-9 19:34
这是著名的欧几里得算法也叫辗转相除法，是求取最大公约数的一种方法。
    首先，以 x 对 y 取余，如 ...

不甚明，但觉历！容我消化下，非常感谢~

spacex_dragon

liuzhengyuan 发表于 2020-11-9 19:18
可以百度一下欧几里得算法（或辗转相除法）

好的，这就去了解~