1

という関数があるとしましょうmy_func(a,b,s,t)。aandを値渡ししたいbが、 and を参照渡ししたいsとtします。のように、私はいくつか言いたいと思います(4,5,s',t')。この関数は、 を呼び出して計算を実行しmy_func(a/2,b/2,s/2,t/2)ます。s問題は、再帰の「下部」に、とに具体的な値を与える基本ケースがあることですt。

ちょっとした例を挙げましょう：

def e_euclid(a,b,s,t):
    
if (a == b):
    s = 4
    t = -3
    return a


if (a%2 == 0 and b%2 == 0):
    
    if (s%2 == 0 and t%2 == 0):
        return 2*e_euclid(a/2,b/2,s/2,t/2)
    else:
        return 2*e_euclid(a/2,b/2,(s+b)/2,(t-a)/2)
...

したがって、この関数を と呼びますe_euclid(a,b, something, something)が、 と に具体的な値を指定する必要がsありtます。私がここで何をしようとしているのか、ちょっとわかりますか？

(s,t) を返す場所で再帰を実行すると、実行したくない難しい計算が発生するため、この方法で実行したいと考えています。

4

1 に答える 1

0

あなたのコードは壊れているようですが、すでにその基本ケース (?) とa == bandは意味がs = 4ありt = -3ません。ただし、この C++ 実装と、C++ の参照の代わりに単一要素リストを使用した私の Python 翻訳を参照してください。

def gcd(a, b, x=[None], y=[None]):
    if b == 0:
        x[0] = 1
        y[0] = 0
        return a
    x1, y1 = [None], [None]
    d = gcd(b, a % b, x1, y1)
    x[0] = y1[0]
    y[0] = x1[0] - y1[0] * (a // b)
    return d

a, b = 123, 321
x, y = [None], [None]
print(gcd(a, b, x, y), x, y, a*x[0] + b*y[0])

出力 (オンラインで試してみてください! ):

3 [47] [-18] 3

アルゴリズムのバイナリバージョンを使用しようとしていると思いますが、これは同じ方法で実行できるはずです。

于 2021-09-19T20:05:50.793 に答える