Algorithme d'Euclide

Répondre

Messages : 1

Enregistré le : 26 nov. 2019 19:07

Algorithme d'Euclide

Message par Piroueman » 04 déc. 2019 18:51

Bonjour,

Enoncé : Créér une fonction qui reçoit deux entiers naturels a et b et qui renvoie leur pgcd.

J'ai fait le programme suivant, qui ne fonctionne pas. J'aimerais savoir pourquoi :

def pgcd(a,b) :
while (b!=0) :
a=b
b=a%b
return a

J'ai essayé de l'appliquer pour a=8 et b=3. Si je déroule j'ai, puisque b différent de 0 :
a prend la valeur 3 puis b prend la valeur 2. 2 différent de 0 donc je continue et ainsi de suite. Pourquoi faudrait-il introduire une variable supplémentaire ?


Enfin, dans la correction (que je ne comprends pas) ils posent : a ,b=b, a%b
Que signifie-t'elle ?

Quelques questions supplémentaires : on est d'accord que l'ordre d'attribution des variables est à prendre en compte : par exemple si j'ai trois variables a,b,c, et que je pose
a=b
b=c, je n'aurai pas le même résultat que si je faisais =
b=c
a=b.

Est-ce une règle d'introduire print plutôt que return pour renvoyer des phrases : ex print "le gain est de", euro"

Quand je cherche à déterminer par un algorithme si un nombre est parfait et que je pose L=diviseurs (n) :
1) Si j'ai déjà écrit le programme des diviseurs de n plus haut, faut-il re-spécifier que L est la liste les diviseurs de n, où Python le reconnait, étant donné qu'on avait fait return L
2) Quand j'écris (Return sumL==2n), Python regarde si c'est vrai ou faux et répond en booléen ?


Merci d'avoir pris le temps de lire !

Messages : 1573

Enregistré le : 13 févr. 2018 09:22

Re: Algorithme d'Euclide

Message par matmeca_mcf1 » 04 déc. 2019 20:00

Piroueman a écrit :
04 déc. 2019 18:51

Code : Tout sélectionner

def pgcd(a,b) :
	while (b!=0) :
		a=b
		b=a%b
	return a 
Quand vous faites b=a%b, votre "a" a déjà été modifié, c'est la nouvelle valeur de "a" et donc la valeur initiale de b qui est utilisé. Votre code renverra toujours b.
Piroueman a écrit :
04 déc. 2019 18:51
Est-ce une règle d'introduire print plutôt que return pour renvoyer des phrases : ex print "le gain est de", euro"
Afficher quelque chose et retourner une valeur sont deux choses très différentes.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'Enseirb-Matmeca (Bordeaux INP)
Les opinions exprimées ci-dessus sont miennes et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

Messages : 11287

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Algorithme d'Euclide

Message par fakbill » 06 déc. 2019 17:54

Deux conseils:
Faire tourner l'algo à la main ou au débugger (mais à la main c'est mieux dans ce cas).
on part de a=8 et b=3
donc b!=0 donc on rentre dans la boucle.
a=b donc a vaut 3.
et ainsi de suite...
Comme ça on comprend ce qui se passe.


print / return : Je ne sais pas comment on vous l'apprend car on voit des horreurs jusque dans le sujet de concours. une fonction c'est un machin qui renvoie une valeur. On peut donc écrire x = pgcd(a,b) et ça stocke le pgcd de a et de b dans la variable x.
print ça affiche. Afficher un résultat n'a que rarement un intéret car seul un humain peut le voir. Si on fait une fonction qui calcule le pgcd, c'est bien pour qu'elle renvoie le pgcd et non pour qu'elle l'affiche. Si on veut l'afficher, on fait print(pgcd(a,b)) et ça marche. Par contre, si tu écris une fonction qui ne fait qu'afficher une valeur, tu ne peux pas t'en resservir.

On n'en plus dans les années 80 ou il était marrant de faire afficher "1 2 3 4 bonjour" à un MO5 en basic...Certains semblent coincés à cette époque quand on lit les sujets de concours des premières années post arrivée de l'info pour tous en prépa :(
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre