Méthode de division mutuelle euclidienne et méthode de division mutuelle euclidienne étendue

Méthode de division mutuelle euclidienne

Étant donné les entiers $ a, b (a> b) $, si $ a $ est divisé par $ b $ et le reste est $ r $. En utilisant le fait que les promesses maximales de $ a $ et $ b $ et les promesses maximales de $ b $ et $ r $ sont égales (principe de division), les promesses maximales de $ a et b $ peuvent être calculées en répétant la division. Comment le trouver.

algorithme

Entiers d'entrée $ a, b $ Engagement maximum de sortie $ d $

  1. a_0 = a,a_1 = b
  2. Lorsque $ a_i = 0 $, définissez $ d = a_ {i-1} $ et terminez
  3. Revenir à 2 comme $ 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]

Méthode de division mutuelle euclidienne étendue

Une méthode pour trouver une solution d'une équation linéaire indéfinie en utilisant le mécanisme suivant. Lorsque vous recherchez $ ax + by = d $, définissez $ 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}] Puis $[\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}] $ Appel. $[\begin{array}{cc} q_i & 1 \ 1 & 0 \ end {array}] Soit $ L_i $ l'inverse de $. $[\begin{array}{cc} a_i \ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \ a_i \end{array}] $ Si vous répétez ceci, $[\begin{array}{cc} d \ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \ b \end{array}] $ Il devient.

algorithme

Entiers d'entrée $ a, b $ Sortie: Entiers $ x, y $ avec engagements maximum $ d $ et $ ax + by = d $

  1. Définissez $ a_0 = a $, $ a_1 = b $.
  2. Définissez $ x_0 = 1 $, $ x_1 = 0 $, $ y_0 = 0 $, $ y_1 = 1 $.
  3. Quand $ a_i = 0 $, $ d = a_i − 1 $, $ x = x_ {i − 1} $, $ y = y_ {i − 1} $ et le processus se termine.
  4. $ a_ {i − 1} = a_iq_i + a_ {i + 1} $ définit $ a_ {i + 1} $ et $ q_i $. x_{i+1} = x_{i−1} − q_ix_i y_i+1=y_i−1−q_iy_i Revenir à 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]

Recommended Posts

Méthode de division mutuelle euclidienne et méthode de division mutuelle euclidienne étendue
Comparaison d'écriture R et Python (méthode de division mutuelle euclidienne)
Algorithme de lapin et de tortue
Reproduire la méthode de division mutuelle euclidienne en Python
Explication et implémentation de l'algorithme ESIM
Algorithme de tri et implémentation en Python
Comprendre et implémenter l'algorithme Tonelli-Shanks (2)
Transformation de Box Cox et algorithme de bois
Comprendre et implémenter l'algorithme Tonelli-Shanks (1)
Théorie et implémentation de Lasso - Algorithme d'estimation de solution clairsemée -
Derrière l'algorithme de dessin graphique et Networkx
Résumé de la classification et de la mise en œuvre des algorithmes d'apprentissage automatique
Explication et implémentation de l'algorithme Decomposable Attention