Dans cet exemple, vous apprendrez à trouver le GCD de deux nombres en utilisant deux méthodes différentes: fonction et boucles et, algorithme euclidien
Pour comprendre cet exemple, vous devez avoir la connaissance des sujets de programmation Python suivants:
- Fonctions Python
- Récursivité Python
- Arguments de la fonction Python
Le facteur commun le plus élevé (HCF) ou le plus grand diviseur commun (GCD) de deux nombres est le plus grand entier positif qui divise parfaitement les deux nombres donnés. Par exemple, le HCF de 12 et 14 est 2.
Code source: utilisation de boucles
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Production
Le HCF est 6
Ici, deux entiers stockés dans les variables num1 et num2 sont passés à la compute_hcf()fonction. La fonction calcule le HCF ces deux nombres et le renvoie.
Dans la fonction, nous déterminons d'abord le plus petit des deux nombres puisque le HCF ne peut être que inférieur ou égal au plus petit nombre. Nous utilisons ensuite une forboucle pour passer de 1 à ce nombre.
À chaque itération, nous vérifions si notre nombre divise parfaitement les deux nombres d'entrée. Si c'est le cas, nous stockons le nombre comme HCF. À la fin de la boucle, nous nous retrouvons avec le plus grand nombre qui divise parfaitement les deux nombres.
La méthode ci-dessus est facile à comprendre et à mettre en œuvre mais n'est pas efficace. Une méthode beaucoup plus efficace pour trouver le HCF est l'algorithme euclidien.
Algorithme euclidien
Cet algorithme est basé sur le fait que HCF de deux nombres divise également leur différence.
Dans cet algorithme, nous divisons le plus grand par le plus petit et prenons le reste. Maintenant, divisez le plus petit par ce reste. Répétez jusqu'à ce que le reste soit égal à 0.
Par exemple, si nous voulons trouver le HCF de 54 et 24, nous divisons 54 par 24. Le reste est 6. Maintenant, nous divisons 24 par 6 et le reste est 0. Par conséquent, 6 est le HCF requis
Code source: utilisation de l'algorithme euclidien
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Ici, nous bouclons jusqu'à ce que y devienne zéro. L'instruction x, y = y, x % yéchange des valeurs en Python. Cliquez ici pour en savoir plus sur l'échange de variables en Python.
Dans chaque itération, nous plaçons la valeur de y dans x et le reste (x % y)dans y, simultanément. Quand y devient nul, on a HCF dans x.
