2

给我函数gcd，定义如下：

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

现在我被要求编写一个递归函数gcd2(a,b)，它返回一个包含三个数字的列表(g, s, t)whereg = 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。

我不确定如何解决这个问题，因为我无法真正想象“停止条件”会是什么，或者我将递归地循环到底是什么来实际找到sand t。谁能帮我吗？

4

4 回答 4

2

关键的见解是我们可以向后工作，在递归中找到and for seach t。所以说我们有和。我们需要使用几个值—— 、、和where来完成每次迭代。首先，让我们考虑基本 GCD 算法的每一步：aba = 21b = 15abb % a ca = c * b + a % b

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

所以我们的 gcd ( g) 是 3。一旦有了它，我们就确定6s和t3 的 和。为此，我们从 开始，用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。因此，鉴于 and 的这些值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

瞧，我们已经计算了 21s和t15。

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

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
于 2012-09-22T14:37:02.493 回答
1

基本情况（停止条件）是：

if a%b == 0:
    # a = b*k for the integer k=a/b
    # rearranges to b = -1*a + (k+1)*b
    #             ( g =  s*a + t*b )
    return (b, -1, a/b+1) # (g, s, t)

然而，练习是重写递归部分：

g1, s1, t1 = gcd(b, a%b) # where g1 = s1*b + t1*(a%b)
g, s, t = ???            # where g = s*a + t*b
return (g, s, t)

根据g1,s1和t1...归结为a%b根据a和重写b。

于 2012-09-22T14:05:57.960 回答
0

“在 Python 中编写递归函数”，至少在 CPython 中，为此而哭泣：请注意http://docs.python.org/library/sys.html#sys.getrecursionlimit。在我看来，这是对这个问题最重要的答案之一。请自己对此主题进行一些研究。此外，这个线程可能很有见地：Python：Linux、Mac 和 Windows 的硬递归限制是什么？

总之，尽可能在 Python 中尝试使用迭代而不是递归方法。

于 2012-09-22T14:40:16.263 回答
0

它基于欧几里得算法，使用更好的while循环继续递归甚至更好，更少执行 

def gcd(m,n):
#assume m>= n
if m <n:
    (m,n) = (n,m)
if (m%n) == 0:
    return(n)
else:
    diff =m-n
    #diff >n ?Possible!
    return(gcd(max(n,diff),min(n,diff)))

可以通过while循环更好

def gcd(m,n):
if m<n :
    (m,n) =(n,m)
while (m%n) !=0:
    diff =m-n
    (m,n) =(max(n,diff),min(n,diff))
return(n)
于 2017-09-20T02:27:49.793 回答