[PYTHON] Euklidische Methode der gegenseitigen Teilung und erweiterte Methode der euklidischen gegenseitigen Teilung

Euklidische Methode der gegenseitigen Teilung

Wenn die ganzen Zahlen $ a, b (a> b) $ gegeben sind, wird $ a $ durch $ b $ geteilt und der Rest ist $ r $. Unter Verwendung der Tatsache, dass die maximalen Versprechen von $ a $ und $ b $ und die maximalen Versprechen von $ b $ und $ r $ gleich sind (das Prinzip der Teilung), können die maximalen Versprechen von $ a und b $ durch Wiederholen der Teilung berechnet werden. Wie finde ich es?

Algorithmus

Geben Sie Ganzzahlen $ a, b $ ein Maximale Verpflichtung ausgeben $ d $

1. a_0 = a,a_1 = b
2. Wenn $ a_i = 0 $, setzen Sie $ d = a_ {i-1} $ und beenden Sie
3. Kehren Sie zu 2 zurück als $ a_ {i-1} = a_iq_i + a_ {i + 1} $

Code

euclid.py

def euclid(a,b):
    a_list = []
    if a < b: 
        a_list.append(b)
        a_list.append(a)
    if a >= b:
        a_list.append(a)
        a_list.append(b)

    i = 0
    while(a_list[-1]!=0):
        a_list.append(a_list[i]%a_list[i+1])
        i +=1
    return a_list[-2]

Erweiterte euklidische Methode der gegenseitigen Teilung

Ein Verfahren zum Finden einer Lösung einer linearen unbestimmten Gleichung unter Verwendung des folgenden Mechanismus. Wenn Sie $ ax + by = d $ finden, setzen Sie $ a_0 = a, a_1 = b $.

[\begin{array}{cc} a_{i-1} \\ a_i \end{array}]= [\begin{array}{cc} a_iq_i+a_{i+1} \\ a_i \end{array}] Dann $[\begin{array}{cc} a_{i-1} \ a_i \end{array}]= [\begin{array}{cc} q_i & 1 \ 1 & 0 \end{array}] [\begin{array}{cc} a_i \ a_{i+1} \end{array}] $ Anruf. $[\begin{array}{cc} q_i & 1 \ 1 & 0 \ end {array}] Die inverse Matrix von $ sei $ L_i $. $[\begin{array}{cc} a_i \ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \ a_i \end{array}] $ Wenn Sie dies wiederholen, $[\begin{array}{cc} d \ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \ b \end{array}] $ Es wird.

Algorithmus

Geben Sie Ganzzahlen $ a, b $ ein Ausgabe: Ganzzahlen $ x, y $ mit maximalen Verpflichtungen $ d $ und $ ax + by = d $

1. Setzen Sie $ a_0 = a $, $ a_1 = b $.
2. Setzen Sie $ x_0 = 1 $, $ x_1 = 0 $, $ y_0 = 0 $, $ y_1 = 1 $.
3. Wenn $ a_i = 0 $, $ d = a_i - 1 $, $ x = x_ {i - 1} $, $ y = y_ {i - 1} $ und beenden.
4. $ a_ {i - 1} = a_iq_i + a_ {i + 1} $ definiert $ a_ {i + 1} $ und $ q_i $. x_{i+1} = x_{i−1} − q_ix_i y_i+1=y_i−1−q_iy_i Zurück zu 3.

Code

exEuclid.py

def exEuclid(a,b):
    a_list = []
    if a < b: 
        a_list.append(b)
        a_list.append(a)
    if a >= b:
        a_list.append(a)
        a_list.append(b)

    q = []
    x = []
    x.append(1)
    x.append(0)
    y = []
    y.append(0)
    y.append(1)

    i = 0
    while(a_list[-1]!=0):
        a_list.append(a_list[i]%a_list[i+1])
        q.append(a_list[i]//a_list[i+1])
        x.append(x[-2]-q[-1]*x[-1])
        y.append(y[-2]-q[-1]*y[-1])
        i +=1
    return x[-2],y[-2],a_list[-2]