Plus grand diviseur commun avec Python

Un facteur est un nombre qui peut entrer dans un autre numéro sans un reste. Un dividende divise un diviseur pour donner le quotient. Si le dividende et le diviseur sont un nombre entier et si le quotient a un reste de zéro (pas de reste), alors le diviseur est appelé facteur de dividende. Le plus grand diviseur commun est abrégé, g.C.D ou simplement GCD. Un autre nom pour le plus grand diviseur commun est le facteur commun le plus élevé, abrégé H.C.F.

Trouver g.C.F par définition

Le problème est de trouver le facteur commun le plus élevé également appelé le plus grand diviseur commun pour les nombres 108 et 240.

Solution:

Tous les facteurs supérieurs à 1 sont placés dans le tableau suivant:

108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

La première rangée a les facteurs de 108 dans l'ordre croissant. La deuxième rangée a les facteurs de 240 dans l'ordre croissant.

Les facteurs communs (diviseurs) pour 108 et 240 sont: 2, 3, 4, 6 et 12.

Par inspection, le plus grand facteur (diviseur) commun aux nombres 108 et 240 est 12. C'est-à-dire GCD ou H.C.F pour 108 et 240 est 12.

La rédaction d'un programme qui trouvera le GCD, comme expliqué ci-dessus, prendra trop de temps. Deux méthodes plus courtes pour trouver le GCD sont: GCD par soustraction et GCD par division.

GCD par soustraction

Par inspection de la table ci-dessus, GCD pour 108 et 240 est 12. Cela signifie que si 12 est ajouté à plusieurs reprises, le résultat deviendra 108, ce qui est le plus petit des deux nombres. Si l'ajout de 12 se poursuit, le résultat deviendra 240, ce qui est le plus grand des deux nombres. C'est-à-dire:

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

C'est-à-dire:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Ce qui signifie:

108 + 132 = 240

Si le GCD peut être ajouté à plusieurs reprises pour donner l'un des nombres (108 et 240) à partir desquels le GCD est nécessaire, alors il pourrait être possible de faire une sorte de soustraction à plusieurs reprises, en commençant par les nombres donnés pour avoir le GCD. En fait, il est possible de faire un type particulier de soustraction à plusieurs reprises et d'obtenir le GCD. Cela commence par la différence des nombres donnés.

Problème: Trouvez le plus grand diviseur commun (facteur commun le plus élevé) pour 108 et 240 par soustraction.

Solution:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Entre 108 et 240, 240 est le plus grand nombre. Après la différence de ces nombres donnés, la différence de la différence résultante (132 pour la première étape) et le subtrahend (108 pour la première étape) sont obtenus à plusieurs reprises jusqu'à ce que la différence finale soit nulle. Dans les étapes, le plus petit nombre est soustrait du plus grand nombre. À la dernière étape, le Minuend et le Subtrahend sont les mêmes. Cette même valeur est le plus grand diviseur commun.

Laissez les chiffres dont le GCD est nécessaire être «A» et «B». Si ces nombres n'ont pas de GCD supérieur à 1, cela signifie que leur plus grand diviseur commun est 1. En programmation, la complexité temporelle pour trouver le GCD par soustraction est O (A + B). Si «A» est 1 et B est 6, alors les étapes sans programmation seront:

6 - 1 = 5
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

Le GCD ici est 1. Il y a six étapes ici et pas sept étapes par (a + b). Cependant, dans la programmation, le nombre maximal possible d'opérations de code est ce qui est considéré comme la complexité temporelle.

Codage GCD par soustraction

La fonction du plus grand diviseur commun par soustraction, en python, est:

Def GCDS (A, B):
Si a == b:
retourner un
Si A> B:
retourner GCDS (A - B, B)
autre:
retourner GCDS (A, B - A)

La première déclaration s'occupe de la dernière étape mathématique. L'énoncé composé suivant (si / else) fait la soustraction entre le Miniend et la différence, selon lequel est plus grand.

Regardez en profondeur les soustractions de mathématiques GCD

240 - 108 = 132
132 = 12 x 11 (132 a 12 comme facteur)
132 - 108 = 24
24 = 12 x 2 (24 a 12 comme facteur)
108 - 24 = 84
84 = 12 x 7 (84 a 12 comme facteur)
84 - 24 = 60
60 = 12 x 5 (60 a 12 comme facteur)
60 - 24 = 36
36 = 12 x 3 (36 a 12 comme facteur)
24 - 12 = 12
12 = 12 x 1 (12 a un facteur ou 12 - lui-même)
24 - 12 = 12
12 = 12 x 1 (12 a un facteur ou 12 - lui-même)

La dernière étape a une différence de 0. Il marque la fin des étapes de soustraction et donne le GCD comme le subtrahend ou le minuend.

GCD par division

Entre 108 et 240, le GCD est supérieur à 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

C'est-à-dire:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Ce qui signifie:

108 + 132 = 240

C'est-à-dire:

12 x 9 + 12 x 11 = 240

Aussi, 108 = 12 x 9 et 240 = 12 x 20.

Maintenant, si le GCD peut être multiplié par un nombre entier (entier positif) pour donner l'un des nombres (108 ou 240) à partir de laquelle le GCD est nécessaire, il pourrait être possible de faire une sorte de division à plusieurs reprises, en commençant par le donné des nombres pour avoir le GCD. En fait, il est possible de faire un type particulier de division à plusieurs reprises et d'obtenir le GCD. Cette division est une division spéciale de module de répétition. Il commence par la division module des nombres donnés.

Dans la division du module, lorsque le dividende est divisé par le diviseur, le reste du quotient est la réponse.

Problème: Trouvez le plus grand diviseur commun (facteur commun le plus élevé) pour 108 et 240 par division module:

Solution:

240% 108 = 24 (i.e. 2 r 24)
108% 24 = 12 (i.e. 4 r 12)
24% 12 = 0 (i.e. 2 r 0)

À la dernière ligne, où le reste est nul, le diviseur est le plus grand diviseur commun (facteur commun le plus élevé).

Ce problème est de trouver le GCD entre 108 et 240 par division. La solution ici a fait 3 pas. Le problème précédent était similaire, mais il devait rechercher le même GCD par soustraction; Et il avait 8 étapes. Bien que la complexité temporelle de la méthode de soustraction soit O (A + B), la complexité temporelle de la méthode de division est O (log (A + B)).

Dans la division du module, peu importe que «A» soit plus grand que B ou B est plus grand que «A»; Le reste est le même entier positif.

Trouver mathématiquement, le plus grand diviseur commun par division, pour les nombres, 5 et 2.

Solution:

5% 2 = 1
1% 1 = 0

Le GCD est 1. Cela avait besoin de deux étapes mathématiques.

Codage GCD par division

Le mot «division» fait ici référence à la division du module. La fonction est:

def gcdd (a, b):
si (un% b == 0):
retour b
autre:
retour gcdd (b, a% b)

L'IF-part de l'If / else-Construct s'occupe de la dernière déclaration mathématique, pour les étapes de la division du module. La partie d'autre s'occupe de la division modulo réelle (résultant en le reste). Dans la division du module, peu importe que «A» soit plus grand que B ou B est plus grand que «A»; Le reste est le même entier positif.

Pour appeler et imprimer un GCD, le code suivant peut être utilisé:

ret = gcdd (240, 108)
print (ret, end = '\ n')

Regardez en profondeur les divisions mathématiques GCD

240% 108 = 24 (le GCD entre 240 et 108 est 12)
24 = 12 x 2 (24 a 12 comme facteur)
108% 24 = 12 (le GCD entre 108 et 24 est 12)
12 = 12 x 1 (12 a 12 comme facteur, lui-même)
24% 12 = 0 (le GCD entre 24 et 12 est 12)

Il a été démontré ici que:

gcd (a, b) = gcd (b, r)

où «a» et b sont deux nombres entiers différents et «r» est le reste de la division entre A et B. B peut être plus grand que «A» ou «A» peut être plus grand que b. Ainsi, si le reste d'une division n'est pas nul, alors le plus grand diviseur commun entre les deux nombres donnés est le même que le plus grand diviseur commun entre le diviseur et le reste. Cela s'étend à différentes étapes jusqu'à ce que le reste est nul, même si le GCD est 1.

La dernière étape a un reste de 0. Il marque la fin des étapes de la division du module et le GCD est le diviseur.

Conclusion

Le plus grand diviseur commun peut être déterminé par des soustractions répétées ou des divisions modulo répétées.

S'il s'agit de soustraction, après la soustraction des nombres donnés, le reste des soustractions se situe entre la différence et le Miniend, selon lequel est plus grand. Lorsque la différence est nulle, le subtrahend est égal à la Miniend, et soit le GCD.

Si c'est par division, alors les divisions répétées sont des divisions de module. Dans cette situation, après la division du module des nombres donnés, le reste des divisions du module se situe entre le diviseur et le reste, selon lequel on est plus grand. Lorsque le reste est nul, le diviseur est le GCD. À strictement parler, dans la division du module, peu importe que «A» soit plus grand que B ou B est plus grand que «A»; Le reste est le même entier positif.