ALGORITME

Résolu
mouni -  
Marco la baraque Messages postés 996 Date d'inscription   Statut Contributeur Dernière intervention   -
Bonjour,

Exercice :

on appelle PGCD de deux entier A et B positifs .un entier calculé comme suit:

- Si a = b alors PGCD ( a,b) = a=b
- Si a < b alors PGCD ( a,b) =PGCD ( a,b-a).
- Si a >b alors PGCD ( a,b) = PGCD ( a - b,b).

Donnez un algorithme qui réalise cette fonction.

3 réponses

Réponse 1 / 3
lexayo Messages postés 27 Date d'inscription   Statut Contributeur Dernière intervention   9
 
l'algo est peut etre tout simplement ceci


fonction PGCD (a,b)
si a = b alors retourne a
sinon
si a < b alors retourne PGCD (a,b-a)
sinon
retourne PGCD (a-b,b)


c'est récursif mais je ne voit pas pour quoi ça serait un problème
2
A.Turing Messages postés 8 Date d'inscription   Statut Membre Dernière intervention   2
 
Les algorithmes récursifs ont une trop grande complexité et il en résulte des explosions combinatoires. Pour un petit exemple ça semble aller, mais dès que les nombres commencent à devenir plus imposants l'algorithme nécessite exponnentiellement plus de temps et de ressources pour tourner
0
Marco la baraque Messages postés 996 Date d'inscription   Statut Contributeur Dernière intervention   329 > A.Turing Messages postés 8 Date d'inscription   Statut Membre Dernière intervention  
 
Bonjour,
La complexité dont tu parles n'est que purement pratique : en effet l'implémentation de la récursivité dans les langages impératifs va être très coûteuse en terme de mémoire, mais ce n'est dû qu'aux langages en eux-mêmes.
L'utilisation de la récursivité dans des langages fonctionnels n'est par contre pas à proscrire.

Ceci dit, ici on ne nous demande qu'un algorithme résolvant le problème, pas une implémentation dans un langage particulier. Je pense donc que l'utilisation de la récursivité a le double avantage d'être clair et pédagogique.

Cordialement,
0
Réponse 2 / 3
Marco la baraque Messages postés 996 Date d'inscription   Statut Contributeur Dernière intervention   329
 
Bonjour,

Astuce :
http://www.commentcamarche.net/faq/sujet 10925 demander de l aide pour vos exercices sur ccm

Lire.
0
Réponse 3 / 3
A.Turing Messages postés 8 Date d'inscription   Statut Membre Dernière intervention   2
 
Bonjour,

Je ne te donnerai pas d'algorithme mais je t'éviterai de faire un mauvais. Evite la solution récursive à ce problème tant que possible.

Bonne chance
0