2

次のように定義されている関数gcdが与えられます。

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

ここで、とgcd2(a,b)の3つの数値のリストを返す再帰関数を作成するように求められます。(g, s, t)g = gcd(a, b)g = s*a + t*b

これは(a and b)、gcd(a, b)関数に2つの値を入力することを意味します。それが返す値gは、次の関数で等しくなります。

a次に、これらの同じb値がに呼び出されgcd2(a, b)ます。次に、再帰部分を使用してsとtの値を見つけ、g = s*a + t*b。

「停止条件」sが何であるか、または実際に見つけて実際に見つけるために再帰的にループするのは正確には何であるかを実際に想像することができないため、これにどのようにアプローチするかはわかりませんt。誰かが私を助けることができますか？

4

4 に答える 4

2

重要な洞察は、再帰で、それぞれを見つけsて、逆方向に作業できることです。だから私たちが持っていると言うと。、、、、およびここで、いくつかの値を使用して、各反復を処理する必要があります。まず、基本的なGCDアルゴリズムの各ステップについて考えてみましょう。taba = 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です。これを取得したら、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つの項を削除します。基本アルゴリズムの最後から2番目の行から、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
于 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に注意してください。これは、私の意見では、この質問に対する最も重要な答えの1つです。このトピックについて自分で調べてください。また、このスレッドは洞察に満ちているかもしれません：Python：Linux、Mac、およびWindowsのハード再帰制限は何ですか？

結論として、可能な限り、Pythonでは再帰的アプローチではなく反復的アプローチを使用するようにしてください。

于 2012-09-22T14:40:16.263 に答える
0

これは、ユークリッドの互除法に基づいており、より良いto 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 に答える