论坛 › Python交流 › 欧几里得算法

archieass 发表于 2022-9-28 00:14:50

欧几里得算法

# 1. 编写一个函数，利用欧几里得算法（脑补链接）求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。
def gcd(x,y):
    a = x
    b = y
    while b > 0:
      c = b
      b = a % b
      a = c
    print(b)

家人们，我想知道为什么我这样是不对的，我手算这样是行得通的诶
球球解答万分感谢

lassiter 发表于 2022-9-28 00:58:17

data=input('为获取最大公约数，请任意输入两个整数，以英文逗号隔开：').split(",")
a,b=int(data),int(data)

while a%b>0:
    a,b=b,a%b

print(f'最大公约数为{b}')

Twilight6 发表于 2022-9-28 07:29:25

最后你都将 a = c 也就是 a = b 了，那么实际上的 a 就是每次循环后的 b

且循环条件是 b > 0 ，那么求余数 当 b = 0 时才会结束，肯定打印 b 为 0 了，应该将 print(b) 改成 print(c)

参考代码：

def gcd(x,y):
    a = x
    b = y
    while b > 0:
      c = b
      b = a % b
      a = c
    print(a)

另外建议函数用 return 返回值，不要直接 print，直接print 函数没有返回值，那么外部就使用不到函数内部计算的值，参考代码：

def gcd(x,y):
    a = x
    b = y
    while b > 0:
      c = b
      b = a % b
      a = c
    return a


>>>print(gcd(100, 120)

# 前者代码输出结果：
20
None

# 后者代码输出结果：
20

jackz007 发表于 2022-9-28 10:35:01

本帖最后由 jackz007 于 2022-9-28 11:03 编辑

def gcd(a , b):
    while b > 0:
      c = a % b
      a = b
      b = c
    return a
print(gcd(64 , 96))
    【简写版】：
def gcd(a , b):
    while b > 0:
      a , b = b , a % b
    return a
print(gcd(64 , 96))
    【递归函数版】：
def gcd(a , b):
    return gcd(b , a % b) if b else a
print(gcd(64 , 96))

查看完整版本: 欧几里得算法