Discuter:Algorithme d'Euclide

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Algorithme d'Euclide fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Élevée Cet article a été classé comme d'Importance élevée selon le Tableau d'évaluation du projet.

Sommaire

[modifier] Complexité

La complexité serait plutôt en O(log(n))... il serait intéressant de revoir ça. (surtout la preuve "il apparait que..." voir théorème de Lamé)

[modifier] Refonte de l'article

J'essaie de donner un fil directeur à l'article, en lien notamment avec l'article division euclidienne. Travail en cours. J'essaie de garder au maximum les sections qui existaient précédemment.Salle 20 mai 2006 à 02:23 (CEST)

[modifier] Erreur dans le code du programme C

Le code contient le test suivant :

while(a =! b)

En prenant l'exemple d'un cours en ligne (par exemple http://www-rocq.inria.fr/codes/Anne.Canteaut/COURS_C/chapitre1.html) je trouve que la bonne syntaxe est while(a != b)

  • Je l'ai remarqué aussi. Code corrigé.

Mais tu aurais pu le corriger directement, c'est tout l'intérêt de wikipedia. ;) Zoidberg 14 février 2007 à 23:21 (CET)

[modifier] Erreurs dans le code du programme C

C'est pire que ça. Je reprends point par point:

 #include <stdio.h>
 #include <stdlib.h>
 int main ()

Il faut écrire int main (void). L'ancienne forme (K&R) est toujours acceptée, mais dans le cas général, elle ne permet pas de faire de vérification de paramètres (probablement pas important pour main, mais autant ne pas prendre de mauvaises habitudes).

 {
  double a = 0, b = 0;

Pourquoi des double pour un calcul typiquement sur des entiers? Ce n'est pas faux tant qu'on s'assure que les entiers ne sont pas trop gros (pour que tous les calculs se fassent exactement), mais dans ce contexte, c'est bizarre.

    scanf("%i %i", &a, &b);

Au passage, c'est incompatible avec le double plus haut.

    while(a =! b)

Erreur déjà notée.

    {
      if (a > b)
       a = a - b;

C'est correct, mais on utilise généralement l'idiome du C: a -= b;

       else
       b = b - a;
    }
    printf("PGCD = %i", a);

Il manque un \n à la fin de la chaîne (c'est nécessaire sur certaines plateformes).

    system("PAUSE");

Pas standard. Ne fonctionne pas sur la plupart des systèmes.

    return 0;
 }

Je pense qu'il faudrait plutôt reprendre ce qui se trouve sur la page en anglais (qui donne d'ailleurs uniquement les algos, indépendamment du langage de programmation). Vincent Lefèvre 5 janvier 2007 à 14:22 (CET)

J'ai essayé le code C donné pour l'algo d'Euclide, mais il me donnait toujours 0 quel que soit a et b. J'ai donc remplacé ce code par un autre code qui marche, même si l'écriture n'a pas été simplifié pour l'instant.

Au posteur précédent: J'ai suivi tous tes conseils et rectifié le code. Par contre, je trouve qu'il vaut mieux le laisser. Je suis d'accord qu'il n'est pas indispensable et que l'algo général est plus important que l'algo codé dans un langage donné, mais c'est très pratique. J'étais bien content de le trouver ici, même si j'ai été obligé de le corriger. ^^ Zoidberg 14 février 2007 à 23:28 (CET)

[modifier] Structure d'anneau euclidien pas assez mise en valeur

Tel qu'il est écrit actuellement, l'article me semble trop centré sur l'anneau des nombres entiers, alors que l'algorithme est applicable dans n'importe quel anneau euclidien. C'est à peine évoqué en une ligne ! Cela mériterait un paragraphe complet, avec peut-être un exemple dans le cas de polynômes… Bon, je n'ai pas le temps de le faire ce soir mais si cela tente quelqu'un, qu'il n'hésite pas. --DSCH (m'écrire) 14 février 2007 à 23:37 (CET)

[modifier] Fusion Algorithme d'Euclide et Algorithme d'Euclide (mathématiques élémentaires)

Ces deux articles traitent du même sujet. La nécessité d'avoir une présentation élémentaire ne se fait pas réellement sentir. Mais une fusion serait à réaliser : il y a dans le deuxième article un organigramme intéressant à récupérer. Kelemvor 29 septembre 2007 à 18:35 (CEST)

Fait Jerome66|me parler 5 octobre 2007 à 12:20 (CEST)

[modifier] Implémentation C et PHP

Cet article n'est pas un article de programmation. Je pense qu'il est inutile de multiplier les exemples dans différents langages. On peut s'en tenir à donner les pseudos code des algos récursifs et itératifs. Si vous êtes d'accord, j'aimerais supprimer les exemples donc. J'attend votre avis. --Max81 (d) 10 mai 2008 à 11:09 (CEST)

Je suis d'accord. Salle (d) 10 mai 2008 à 11:32 (CEST)
Je suis aussi tout à fait d'accord (comme je l'avais mentionné plus haut, cf la page en anglais). Vincent Lefèvre (d) 15 mai 2008 à 00:40 (CEST)