最大公约数 (python)

Question

我正在尝试让我的代码打印出我最大的公约数。从技术上讲，我的代码应该可以工作，但它总是更进一步直到 x = 0，即使它应该打印 x = gcd 由于我学校的分配，您在代码中看到的所有内容都必须保留在结构基础上。这意味着我必须打印出 x 并使用 r != 0 进行 while 循环等等...... 无论您最有可能知道如何修复它，而无需我过度解释我的代码 xD

def ggt2(x, y):
    r = 1
    while r != 0:       #I have to use a while loop
        if x < y:
            r = x % y
            x = y
            y = r
            print(x)    #here it prints nothing at all
        elif x > y:
            r = x % y
            y = x
            x = r
            print(x)    #here it prints x = 0
x = input()
y = input()
ggt2(int(x), int(y))

编辑：这是我们得到的伪代码。这基本上是我必须遵循的结构。如果 x < y，我们还被告知切换 x <-> y。

GCD :var X,Y,R: int;
input X,Y;
R:=1;
while R ≠ 0 do
R:=X mod Y; X:=Y; Y:=R;
od;
output X.

Answer 1

你给出的伪代码叫做欧氏算法。它是基于除法的，x 和 y 的顺序无关紧要。

def ggt2(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a

ggt2(24, 60)
ggt2(60, 24)

输出：

12
12

顺序对于基于减法的算法很重要，这就是为什么如果 x < y

要求您切换 x,y

阅读 wiki 以了解这两种算法。

Answer 2

def ggt2(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a if a != 0 else None

a = int(input("Enter a: "))
b = int(input("Enter b: "))
print("Their GCD is: "+str(ggt2(a,b)))

此代码已从 Wikipedia 上的伪代码转换为 Python，并做了一些小改动。

您的代码有些问题。这是你给出的伪代码：

GCD :var X,Y,R: int;
input X,Y;
R:=1;
while R ≠ 0 do
R:=X mod Y; X:=Y; Y:=R;
od;
output X.

这是什么意思：

开始GCD
分别创建 X、Y 和 R 类型的变量 int
给X和Y输入一个值
将 R 设置为 1
虽然 R 不等于 0 做：
（在 5 的循环中）将 R 设置为 X % Y（X 和 Y 的余数）
（在 5 的循环中）将 X 设置为 Y
（在 5 的循环中）将 Y 设置为 R
循环结束从语句 5 迭代开始
打印出来X

此伪代码转换为 Python 将是：

def GCD():
    X = int(input("Enter X: "))
    Y = int(input("Enter Y: "))
    R = 1
    while R != 0:
        R = X % Y
        X = Y
        Y = R
    print(X)

GCD()

试着弄清楚它是如何工作的，如果它对你有用，请在评论中告诉我！

最大公约数 (python)

greatest common divisor (python)

python

greatest-common-divisor