我被赋予了函数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
的位置。
这意味着您将在gcd(a, b)
函数中输入两个(a and b)
值。它返回的值等于下一个函数中的g
。
然后将这些相同的a
和b
值调用到gcd2(a, b)
中。然后使用递归部分来查找 s 和 t 的值,以便g = s*a + t*b
。
我不确定如何处理这个问题,因为我无法真正想象"停止条件">会是什么,或者我究竟会递归地循环以实际找到s
和t
。谁能帮我?
关键的见解是,我们可以向后工作,找到每个a
的s
和t
,并在递归中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
基本情况(停止条件)为:
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
。
用Python编写一个递归函数">,至少在CPython中,为此大声疾呼:注意 http://docs.python.org/library/sys.html#sys.getrecursionlimit。在我看来,这是这个问题最重要的答案之一。请自己对这个主题做一些研究。此外,这个线程可能很有见地: Python:Linux,Mac和Windows的硬递归限制是多少?
总之,尽可能在 Python 中使用迭代而不是递归方法。
它基于欧几里得算法,使用更好的循环继续递归甚至更好,执行更少
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)