如何实现扩展欧几里得算法？

2024-04-30 • 问答

使用扩展的欧几里得算法：我希望输出看起来像这样：

algo(700,440) =   [20,-5,8]
algo(88,35) =     [1,2,-5]
algo(35,88) =     [1,2]
algo(-88,35) =    [1,-5]
algo(88,-35) =    [1,-5]
algo(0,777) =     Error(algo): Invalid input num

但是我得到以下输出：

#enter code here
algo(700,440) =   (20,8)
algo(88,35) =     (1,-5)
algo(35,88) =     (1,2)
algo(-88,35) =    (-1,5)
algo(88,-35) =    (1,5)
algo(0,777) =     (777,1)

我的代码是：

def algo(a,b):
    if a == 0:
        return (b,1) 
    else:
        g,y,x = algo(b % a,a)
        return (g,x - (b // a) * y,y)

我对如何将值放入列表中感到困惑，并且在打印错误消息时遇到麻烦。每当我在第一个if情况下更改为打印语句时，都会收到错误消息。函数不需要递归，但是任何帮助将不胜感激！

表示错误的正确方法是raise，而不是return某种错误消息：

def algo(a,b):
    if a == 0 and b == 0:
        raise ValueError('HCF of 0,0 is undefined')
    elif a == 0:
        return [b,1] 
    else:
        g,y,x = algo(b % a,a)
        return [g,x - (b // a) * y,y]

要在其他代码中处理此问题，请使用try / except：

pairs = [(700,440),(88,35),(35,88),(-88,-35),(0,0),777)]

for a,b in pairs:
    try:
        r = algo(a,b)
        print('algo({0},{1}) = {2}'.format(a,b,r))
    except ValueError as e:
        print(e)

输出：

algo(700,440) = [20,-5,8]
algo(88,35) = [1,2,-5]
algo(35,88) = [1,2]
algo(-88,35) = [-1,5]
algo(88,-35) = [1,5]
HCF of 0,0 is undefined
algo(0,777) = [777,1]

请注意，当一个数字为零时，最高公因数是明确定义的；仅当两个数字均为零时，输入才真正无效。

如何实现扩展欧几里得算法？

lwt770906 回答：如何实现扩展欧几里得算法？

大家都在问