Le plus grand diviseur commun (GCD) de a et b est le plus grand nombre qui les divise tous les deux sans reste.
Une façon de trouver le GCD de deux nombres est l'algorithme d'Euclid, qui est basé sur l'observation que si r
est le reste quand a
est divisé par b
, alors gcd(a, b) = gcd(b, r)
. Comme cas de base, nous pouvons utiliser gcd(a, 0) = a
.
Ecrivez une fonction appelée gcd qui prend les paramètres a
et b
et renvoie leur plus grand diviseur commun.
Réponses:
C'est dans la bibliothèque standard .
Code source du
inspect
module en Python 2.7:À partir de Python 3.5, se
gcd
trouve dans lemath
module ; celui defractions
est obsolète. De plus,inspect.getsource
ne renvoie plus le code source explicatif pour l'une ou l'autre méthode.la source
fractions.gcd(1, -1)
est-1
mais1 > -1
c'est-à-dire1
divise les deux1
et-1
sans reste et il est plus grand que-1
, voir bugs.python.org/issue22477gcd(1, -1) == -1
me semble totalement légitime.fractions.gcd()
quel (il fonctionne sur les éléments d'anneau euclidien).math.gcd(1, -1)
retourne1
.Les algorithmes avec mn peuvent être extrêmement longs.
Celui-ci fonctionne beaucoup mieux:
la source
x
avant d'être affectée. Vous avez attribuéy
à lax
première , donc maintenanty
va être défini sur0
(commey % y
toujours 0).Cette version de code utilise l'algorithme d'Euclid pour trouver GCD.
la source
def gcd(a, b): if b == 0: return a return gcd(b, a % b)
la source
la source
Solution très concise utilisant la récursivité:
la source
en utilisant la récursivité ,
en utilisant while ,
en utilisant lambda,
la source
Une approche différente basée sur l'algorithme d'euclid.
la source
la source
Je pense qu'une autre façon est d'utiliser la récursivité. Voici mon code:
la source
gcd(10,5)
en python avec récursivité:
la source
la source
Pour
a>b
:Pour l'un
a>b
ou l' autre oua<b
:la source
b, a = a, b
. essayez d'en savoir plus sur la langueJ'ai dû faire quelque chose comme ça pour un devoir à la maison en utilisant des boucles while. Ce n'est pas le moyen le plus efficace, mais si vous ne souhaitez pas utiliser une fonction, cela fonctionne:
la source
la source
Ce code calcule le pgcd de plus de deux nombres en fonction du choix donné par # l'utilisateur, ici l'utilisateur donne le nombre
la source
L'échange de valeur n'a pas bien fonctionné pour moi. Je viens donc de mettre en place une situation de type miroir pour les nombres entrés dans a <b OU a> b:
la source
plus grand_common_devisor (A)
la source
la source
break
déclaration tente de réaliser.Voici la solution mettant en œuvre le concept de
Iteration
:la source