实现扩展欧几里得算法 | 实现扩展欧几里得算法

本文介绍了实现扩展欧几里得算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

为什么的以下实现失败？

Why is the following implementation of the Extended Euclid Algorithm failing?

def extended_euclid(a,b):
    if b == 0:
        return {a, 1, 0}

    d1,x1,y1 = extended_euclid(b, a % b)
    d = d1
    x = y1
    y = x1 - math.floor(a/b) * y1
    return {d, x, y}

推荐答案

这是在，看起来与您的相似。

This is the implementation found in https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm , looks similar to your's one.

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

这篇关于实现扩展欧几里得算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！