Comment utiliser Python pour implémenter l'algorithme de recherche du plus grand diviseur commun ?

Comment utiliser Python pour implémenter l'algorithme de recherche du plus grand diviseur commun ?

Le plus grand diviseur commun, également appelé plus grand diviseur commun, fait référence au plus grand nombre parmi les diviseurs partagés par deux nombres ou plus. Le calcul du plus grand diviseur commun est une tâche très courante dans les domaines mathématiques et informatiques. Python, en tant que langage de programmation populaire, propose diverses méthodes pour implémenter cet algorithme.

Ce qui suit présentera trois algorithmes Python couramment utilisés pour implémenter le plus grand diviseur commun, à savoir la méthode exhaustive, la méthode de division euclidienne et la méthode de soustraction à changement de phase.

1. Méthode exhaustive
   La méthode exhaustive est la méthode la plus intuitive mais la moins efficace. Cette méthode essaie tous les facteurs possibles un par un pour trouver le plus grand diviseur commun.

def gcd_exhaustive(a, b):
    if a > b:
        smaller = b
    else:
        smaller = a
    for i in range(1, smaller+1):
        if ((a % i == 0) and (b % i == 0)):
            gcd = i
    return gcd

2. Division euclidienne
   La division euclidienne, également connue sous le nom d'algorithme euclidien, est un algorithme récursif de division euclidienne. Cet algorithme est basé sur le théorème suivant : le plus grand commun diviseur de deux entiers positifs a et b (a > b) est égal au plus grand commun diviseur entre le reste c et b de a divisé par b.

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

3. Méthode de soustraction de phase supplémentaire
   La méthode de soustraction de phase supplémentaire est également un algorithme récursif, qui résout le plus grand diviseur commun en soustrayant continuellement la différence entre deux nombres. Cependant, cet algorithme est moins efficace et peut expirer lors du traitement de grands nombres.

def gcd_subtraction(a, b):
    if a == b:
        return a
    elif a > b:
        return gcd_subtraction(a-b, b)
    else:
        return gcd_subtraction(a, b-a)

peut être testé par le code suivant :

a = 374
b = 256

print("穷举法求解最大公约数：")
print(gcd_exhaustive(a, b))

print("辗转相除法求解最大公约数：")
print(gcd_euclidean(a, b))

print("更相减损法求解最大公约数：")
print(gcd_subtraction(a, b))

Selon le code ci-dessus, lorsque l'entrée a est 374 et b est 256, le plus grand diviseur commun calculé est 2 (en utilisant la méthode exhaustive) et 2 (en utilisant la phase euclidienne) et 2 (en utilisant la méthode de soustraction de phase).

Ci-dessus sont trois algorithmes couramment utilisés pour résoudre le plus grand diviseur commun à l'aide de Python. En fonction de la situation spécifique et de la taille des données, un algorithme approprié peut être sélectionné pour résoudre le plus grand diviseur commun.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!