python - 如何在 Python 中使用堆栈方法编写欧几里德算法？

Question

在这里寻求帮助！

有谁知道如何将欧几里得算法的递归版本（找到最大公约数 GCD）转换为使用堆栈的版本？

这是欧几里得算法的递归版本：

def euclid_gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a, a)

现在我有一个起始代码可以转换为欧几里得算法的堆栈版本：

def euclid_gcd_stack(a, b):
    s = Stack()
    s.push(a)
    s.push(b)

    while s.count() > 0:
        b = s.pop()
        a = s.pop()

 <code to be continued here>

先感谢您！:)

标签： pythonalgorithmrecursionstackcomputer-science

Answer 1

def euclid_gcd_stack(a, b):
    s = Stack()
    s.push(a)
    s.push(b)

    while s.count() > 0:
        b = s.pop()
        a = s.pop()

        if a > b:
            a, b = b, a
        if a == 0:
            return b
        else:
            s.push(a)
            s.push(b - a)
``