Algorithme d'euclide

Soyez le premier à donner votre avis sur cette source.

Vue 5 221 fois - Téléchargée 509 fois

Description

L'algorithme d'Euclide permet de trouver le PGCD (plus grand commun diviseur) de deux chiffres.
Je l'ai donc adapté en fonction PHP en prenant quasiment tous les cas de figure possible, le code précise même si les nombres sont premiers entre eux.
Code complet et commenté !
Le .zip ne contient qu'un fichier, divisé en 2 parties :
- la fonction
- le formulaire

C'est mon premier vrai code, merci de m'indiquer les erreurs et autre. Je suis bien conscient qu'il y a plus compact et plus optimisé !
Il est à vous d'intégrer le code comme il vous le faut.

Source / Exemple :


<?php

/*

  • ---------------------------------------------------------
  • | Algorithme d'Euclide |
  • | En PHP |
  • ---------------------------------------------------------
  • /
//Création d'une fonction réutilisable à plusieurs endroits, elle n'a plus qu'a être appellée avec les deux variables demandées ! //Elle contiendra l'algorithme d'Euclide. //On définit nos deux variables comme "a" et "b" function PGCD($a, $b) { //Si nos variables "a" et "b" sont des chiffres : if (is_numeric($a) AND is_numeric($b)) { //Si la variable "b" est plus petite que "a" et que "a" est différente de 0, on éxecute le code suivant : if ($b<$a AND $a!=0) { //On crée la variable "reste" qui contient le reste de la division de "a" par "b" (pour qu'il ne soit pas différent de 0 donc que la boucle s'éxecute), $reste = $a%$b; //On crée une boucle qui ne s'arrêtte pas tant que la variable "reste" est différente de 0 : while ($reste!=0) { //On reprend "reste", cela nous servira aux prochaînes executions, $reste = $a%$b; //On donne la valeur de "b" à "a", $a = $b; //On donne le contenu de "reste" à "b", $b = $reste; } //Cette boucle s'éxecutera autant de fois qu'il le faudra. //Pour des raisons d'éstétique, lors de l'affichage du résultat, on va definir l'ordre dest chiffres de départ, (le plus grand chiffre en premier, le plus petit en deuxieme) dans la phrase : //PGCD( nombre ; nombre) = resultat //On las affichera plus tard... //on définit donc dans la variable "premier" le premier chiffre : $premier = $_POST['a']; //Le deuxième dans "deuxième" $deuxieme = $_POST['b']; //Et bien évidement le résultat, dans la variable "resultat"... $resultat = $a; } //Sinon si la variable "a" est plus petite que "b" et que "b" est différente de 0, on éxecute le code suivant : elseif ($a<$b AND $b!=0) { //On récupère le reste de la division de "b" par "a", $reste = $a%$b; while ($reste!=0) { //On reprend le reste, cela nous servira aux prochaînes executions, $reste = $b%$a; //On donne la valeur de "a" à "b", $b = $a; //On donne le contenu du reste à "a", $a = $reste; } $premier = $_POST['b']; $deuxieme = $_POST['a']; $resultat = $b; } //Si les deux variables "a" et "b" sont égales, on execute le code suivant : elseif ($a=$b) { //"premier" et "deuxieme" sont les mêmes, pas besoin de s'embêter ! $premier = $deuxieme = $_POST['a']; //Me résultat est aussi les chiffres de départ, on affiche "a", on peut tout aussi bien afficher "b" ! $resultat = $a; } //Sinon, on a une erreur, ce n'est pas normal, mais il faut toujours prévoir le cas où le script plante ! On définit le résultat comme faux ! else { $resultat = FALSE; }; //Si on a un ordre pour l'affichage des chiffres et que le résultat est égal à un : if (isset($resultat) AND isset($premier) AND isset($deuxieme) AND $resultat == 1) { //On affiche tout comme il se doit, et vu que c'est le cas, on indique aussi que les nombres sont premiers entre eux ! return 'PGCD(' .$premier. ';' .$deuxieme. ') = ' .$resultat. ' .<br/>Les nombres ' .$premier. ' et ' .$deuxieme. ' sont premiers entre eux !'; } //Sinon si on a un ordre pour l'affichage des chiffres : elseif (isset($resultat) AND isset($premier) AND isset($deuxieme)) { //On affiche tout comme il se doit ! return 'PGCD(' .$premier. ';' .$deuxieme. ') = ' .$resultat. ' .'; } //Sinon si le résultat est faux : elseif ($resultat = FALSE) { //On affiche que le visiteur a fait une erreur ! return 'Erreur lors du calcul ! Veuillez réésayer.'; } //Sinon, on a une erreur ! else { //Ce n'est normalement pas une erreur du visiteur. return 'Erreur lors de l\'execution du script ! Veuillez réésayer.'; }; } //Sinon les variables ne sont pas des chiffres ! else { return 'Veuillez indiquer des chiffres !'; }; }; ?> <?php //En cas d'affichage sans envoi du formulaire : on n'affiche rien. On définit quand même la variable pour éviter toute erreur ! $reponse = ''; //Si le formulaire a tét validé : if (isset($_POST['pgcd'])){ //Si les champs sont remplis : if (isset($_POST['a']) AND isset($_POST['b'])) { //On appelle la fonction avec nos variables : $reponse = PGCD($_POST['a'], $_POST['b']); } //Sinon, si les champs sont vides : else { //On demande au visiteur de remplir les champs, normalement, ce texte ne s'affiche pas car plus haut, on vérifie si les champs sont des chiffres. J'ai quand même au cas où mis le même message que lorsque nos variables n'en sont pas ! $reponse = 'Veuillez indiquer des chiffres !'; }; } ?> <!DOCTYPE html> <!-- Minimum pour avoir une page web correcte --> <html lang="en"> <head> <meta charset="utf-8"> <title>Calculer le PGCD de deux nombres</title> </head> <!-- On affiche le contenu de la page --> <body> <!-- ici le formulaire --> <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="post" > Veuillez entrer les nombre à partir desquels le PGCD va être calculé :<br/> <label for="a">Premier nombre : </label><input name="a" id="b" type="text"/> <label for="b">Deuxième nombre : </label><input name="b" id="b" type="text"/> <input type="submit" name="pgcd" value="Envoyer" /> </form> <!-- Ici le résultat --> <?php echo $reponse; ?> </body> </html>

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

<quote>Oui d'accord, tu utilises les fonctions déjà intégrées dans PHP mais moi je voulais le faire juste avec la boucle, c'était aussi pour montrer à des gens comment ça fonctionnait ! Je l'ai par la suite posté !
Dans tous les cas, je ne trouve pas l'erreur de 128 et 34 avec leurs multiplicateurs (j'ai cherché) !</quote>

Bonjour,

il ne s'agit pas d'une fonction intégrée à PHP : c'est "gmp_gcd" la fonction intégrée si je ne ma trompe pas.

Cependant, l'agorithme proposé par PMCOSTE fait appel à la récursivité : la fonction s'appelle elle même pour avec de nouveaux paramètres. L'exemple classique pour illustrer la récursivité, c'est le calcul de factoriel. Il doit y avoir plein d'exemple sur le net pour toutes sortes de langages.
Merci, en effet, erreur non présente sur mon fichier d'origine en local ! C'est quand j'ai commenté je pense... Je met a jours ça demain ;)
Messages postés
4
Date d'inscription
dimanche 24 septembre 2006
Statut
Membre
Dernière intervention
25 juin 2013

Je pense qu'en ligne 47 il faut remplacer $b par $a et ça devrait marcher !
Oui d'accord, tu utilises les fonctions déjà intégrées dans PHP mais moi je voulais le faire juste avec la boucle, c'était aussi pour montrer à des gens comment ça fonctionnait ! Je l'ai par la suite posté !
Dans tous les cas, je ne trouve pas l'erreur de 128 et 34 avec leurs multiplicateurs (j'ai cherché) !
Messages postés
72
Date d'inscription
mercredi 7 février 2007
Statut
Membre
Dernière intervention
25 juillet 2013
1
Bonjour,

Merci pour cette contribution, mais avec une recherche sur un moteur de recherche, on tombe sur une page avec un algo un peu plus simple :
http://snipplr.com/view/6441/
Il donne également le PPCM, ce qui va souvent avec !

function pgcd($a, $b) {
$a = abs($a);
$b = abs($b);
if ($a == 0) {
return $b;
}
elseif ($b == 0) {
return $a;
}
elseif ($a > $b) {
return pgcd($b, $a % $b);
}
else {
return pgcd($a, $b % $a);
}
}
Afficher les 7 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.