Inscription / Connexion Nouveau Sujet
Niveau première
Partager :

PGCD algorithme

Posté par
pferd101996
29-03-13 à 13:41

Bonjour, je dois résoudre l'exercice suivant mais malheureusement mon programme ne fonctionne pas.

Voici l'énoncé:
Votre programme attend l'entrée de 2 nombres entiers positifs, si c'est le cas il recherchera par divisions euclidiennes successives leur PGCD puis affichera l'écriture suivante: PGCD(a;b)=g où a,b sonrt les nombres entrés et g leur PGCD.
Mon programme est l'image attachée.

Le problème est qu'il reprend le B du départ et non celui qui a été calculé dans la boucle. Que faire?

PGCD algorithme

Posté par
Bachstelze
re : PGCD algorithme 29-03-13 à 13:50

Tu n'affectes jamais de nouvelle valeur à G, donc la boucle tourne à l'infini.

Posté par
Bachstelze
re : PGCD algorithme 29-03-13 à 13:52

Tu ne donnes même pas de valur initiale à G, d'ailleurs. Je suppose qu'algobox l'initialise à 0, donc en fait la boucle n'est jamais exécutée.

Posté par
pferd101996
re : PGCD algorithme 29-03-13 à 14:28

Merci, j'ai effectivement oublier d'ajouter "LIRE G".
Je viens de le rajouter et j'ai testé l'algorithme et il se bloque à la ligne 14 (FIN_TANT_QUE) et m'affiche "dépassement de la capacité autorisée pour les boucles". Je ne vois pas ce qu'il tente de m'expliquer...

Posté par
Bachstelze
re : PGCD algorithme 29-03-13 à 14:29

Relis mon message de 13 h 50. Tu n'affectes jamais de nouvelle valeur à G à l'intérieur de ta boucle.

Posté par
pferd101996
re : PGCD algorithme 29-03-13 à 14:38

J'ai effectivement mis R a la place de G dans la boucle. (Je voulais mettre: G PREND_LA_VALEUR A%B)
Je l'ai changé dans mon algorithme mais lorsque je le lance, je peut mettre n'importe quel nombre pour A, B et G le résultat est toujours 0. C'est normal??

Posté par
Bachstelze
re : PGCD algorithme 29-03-13 à 14:49

La boucle s'arrête quand G = 0. La dernière chose que tu fais dans ta boucle, c'est affecter à B la valeur de G, donc à la fin B vaudra forcément 0.

Posté par
pferd101996
re : PGCD algorithme 29-03-13 à 14:55

Donc a la fin je dois afficher A et non B?

Posté par
Glapion Moderateur
re : PGCD algorithme 29-03-13 à 15:07

pferd101996 je ne suis pas sûr que tu sois sur la bonne voie.

Commence par penser l'algorithme. On va prendre la logique Euclide.
Tant que le produit A*B n'est pas nul, on va retrancher B à A (ou A à B si c'est B le plus grand) donc si A est plus grand on va boucler en retirant B jusqu'à ce que B devienne plus petit que A. Puis c'est A que l'on va retrancher de B. On continue comme ça jusqu'à ce que A ou B soit nul (S'ils sont premiers entre eux il y a un moment où ils seront tout deux égaux à 1 et on va tomber soit sur A=0 soit sur B=0, sinon c'est qu'en retirant B de A (ou A de B) on est tombé avant sur 0 et auquel quoi on est tombé sur le PGCD.
Bon c'est un plus compliqué à expliquer qu'à faire en fait. Ça donne :
(tu peux le copier/coller en mode editeur de texte dans algobox)

VARIABLES
A EST_DU_TYPE NOMBRE
B EST_DU_TYPE NOMBRE
FF EST_DU_TYPE CHAINE
DEBUT_ALGORITHME
AFFICHER " Entrez deux nombres : "
LIRE A
LIRE B
FF PREND_LA_VALEUR "PGCD("+A+";"+B+")="
TANT_QUE (A*B != 0) FAIRE
DEBUT_TANT_QUE
SI (A>B) ALORS
DEBUT_SI
A PREND_LA_VALEUR A-B
FIN_SI
SINON
DEBUT_SINON
B PREND_LA_VALEUR B-A
FIN_SINON
FIN_TANT_QUE
SI (A==0) ALORS
DEBUT_SI
FF PREND_LA_VALEUR FF+B
FIN_SI
SINON
DEBUT_SINON
FF PREND_LA_VALEUR FF+A
FIN_SINON
AFFICHER FF
FIN_ALGORITHME

Posté par
pferd101996
re : PGCD algorithme 29-03-13 à 15:28

J'étais effectivement loin de la reponse...
Merci beaucoup pour votre aide

Posté par
Glapion Moderateur
re : PGCD algorithme 29-03-13 à 15:29

Remarque, je m'aperçois que je t'ai mis une autre logique et tu vas peut-être avoir du mal à comprendre. En voilà un autre qui est plus proche de la logique que tu avais commencé à faire :

VARIABLES
A EST_DU_TYPE NOMBRE
B EST_DU_TYPE NOMBRE
X EST_DU_TYPE NOMBRE
FF EST_DU_TYPE CHAINE
DEBUT_ALGORITHME
LIRE A
LIRE B
FF PREND_LA_VALEUR "PGCD("+A+";"+B+")="
TANT_QUE (B != 0) FAIRE
DEBUT_TANT_QUE
X PREND_LA_VALEUR A
A PREND_LA_VALEUR B
B PREND_LA_VALEUR X%B
FIN_TANT_QUE
SI (A==0) ALORS
DEBUT_SI
FF PREND_LA_VALEUR "pas de PGCD pour deux nombres nuls"
FIN_SI
SINON
DEBUT_SINON
FF PREND_LA_VALEUR FF+A
FIN_SINON
AFFICHER FF
FIN_ALGORITHME



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !