ALGORITME

Résolu/Fermé

mouni - 14 janv. 2009 à 16:03
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 - 15 janv. 2009 à 10:48

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 lundi 29 décembre 2008 Statut Contributeur Dernière intervention 24 septembre 2009 9
14 janv. 2009 à 23:49

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

A.Turing Messages postés 8 Date d'inscription mardi 13 janvier 2009 Statut Membre Dernière intervention 23 février 2009 2
15 janv. 2009 à 10:19

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

Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329 > A.Turing Messages postés 8 Date d'inscription mardi 13 janvier 2009 Statut Membre Dernière intervention 23 février 2009
15 janv. 2009 à 10:48

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,

Réponse 2 / 3

Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329
14 janv. 2009 à 16:08

Bonjour,

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

Lire.

Réponse 3 / 3

A.Turing Messages postés 8 Date d'inscription mardi 13 janvier 2009 Statut Membre Dernière intervention 23 février 2009 2
14 janv. 2009 à 21:57

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

Discussions similaires

algoritme