python - 使用Python中的递归函数计算扩展gcd

我得到了函数gcd，其定义如下：

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

现在，我被要求编写一个递归函数gcd2(a,b)，该函数返回三个数字(g, s, t)的列表，其中g = gcd(a, b)和g = s*a + t*b。

这意味着您将在(a and b)函数中输入两个值gcd(a, b)。在下一个函数中，它返回的值等于g。

然后将这些相同的a和b值调用到gcd2(a, b)中。然后使用递归部分查找s和t的值，以使g = s*a + t*b。

我不确定如何解决这个问题，因为我无法真正设想“停止条件”是什么，或者我将递归地遍历以真正找到s和t的确切条件。谁能帮我吗？

最佳答案

关键的见解是我们可以向后工作，为递归中的每个s和t查找a和b。假设我们有a = 21和b = 15。我们需要使用几个值-a，b，b % a和c（其中a = c * b + a % b）来完成每次迭代。首先，让我们考虑基本GCD算法的每个步骤：

21 = 1 * 15 + 6
15 = 2 * 6  + 3
6  = 2 * 3  + 0 -> end recursion

因此，我们的gcd（g）为3。一旦有了，我们就确定6和3的s和t。为此，我们从g开始，用(a, b, s, t = 3, 0, 1, -1)表示：

3  = 1 * 3 + -1 * 0

现在我们要消除0项。从基本算法的最后一行，我们知道0 = 6-2 * 3：

3 = 1 * 3 + -1 * (6 - 2 * 3)

简化，我们得到

3 = 1 * 3 + -1 * 6 + 2 * 3
3 = 3 * 3 + -1 * 6

现在我们交换条款：

3 = -1 * 6 + 3 * 3

因此，对于s == -1和t == 3，我们具有a = 6和b = 3。因此，给定a和b的值，gcd2应该返回(3, -1, 3)。

现在，我们逐步递归，希望消除3项。从基本算法的倒数第二行，我们知道3 = 15-2 *6。再次简化和交换（慢慢地，以便您可以清楚地看到这些步骤...）：

3 = -1 * 6 + 3 * (15 - 2 * 6)
3 = -1 * 6 + 3 * 15 - 6 * 6
3 = -7 * 6 + 3 * 15
3 = 3 * 15 + -7 * 6

因此，对于此递归级别，我们返回(3, 3, -7)。现在我们要消除第6项。

3 = 3 * 15 + -7 * (21 - 1 * 15)
3 = 3 * 15 + 7 * 15 - 7 * 21
3 = 10 * 15 - 7 * 21
3 = -7 * 21 + 10 * 15

瞧，我们已经计算出21和15的s和t。

如此示意，递归函数将如下所示：

def gcd2(a, b):
    if (0 == a % b):
        # calculate s and t
        return b, s, t
    else:
        g, s, t = gcd2(b, a % b)
        # calculate new_s and new_t
        return g, new_s, new_t

请注意，出于此处的目的，使用稍有不同的基本案例可以简化操作：

def gcd2(a, b):
    if (0 == b):
        return a, 1, -1
    else:
        g, s, t = gcd2(b, a % b)
        # calculate new_s and new_t
        return g, new_s, new_t

关于python - 使用Python中的递归函数计算扩展gcd，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12544086/