Pgcd : algorithme d'euclide par recursivité

Soyez le premier à donner votre avis sur cette source.

Snippet vu 17 797 fois - Téléchargée 26 fois


Contenu du snippet

Il existe une fonction pour trouver le PGCD je vous en propose une autre ici.
Cette fonction est recursive et ecrit les étapes intermediaires jusqu'a vous donner le PGCD d'un nombre

Source / Exemple :


<?php
function pgcd($diviseur,$reste)
{
    //
    // Verifie si le reste est egal a 0 si oui on a trouvé le PGCD
    //
    if ($reste == 0)
    {
        echo "<b>PGCD :</b>$diviseur";
    }
    //
    // Sinon on continu de le chercher
    //
    else
    {
        echo "$diviseur/$reste = ".intval(abs($diviseur/$reste))." reste ".$diviseur%$reste."<br />";
        pgcd($reste,$diviseur%$reste); // recursivité
    }
}

echo 'PGCD('.$_GET['nbr1'].';'.$_GET['nbr2'].')<br /><br />';
echo max($_GET['nbr1'],$_GET['nbr2']).'/'.min($_GET['nbr1'],$_GET['nbr2']).' = '.intval(abs(max($_GET['nbr1'],$_GET['nbr2'])/min($_GET['nbr1'],$_GET['nbr2']))).' reste '.max($_GET['nbr1'],$_GET['nbr2'])%min($_GET['nbr1'],$_GET['nbr2']).'<br />';
pgcd(min($_GET['nbr1'],$_GET['nbr2']),max($_GET['nbr1'],$_GET['nbr2'])%min($_GET['nbr1'],$_GET['nbr2']));
?>

Conclusion :


Ce script prend 2 parametres en GET :
nbr1 : qui est le premier nombre
nbr2 : qui est le deuxieme

Exemple d'appelle : script.php?nbr1=15&nbr2=5

Pour rapelle le PGCD est le plus grand commun diviseur

mon site : http://iow4.net

A voir également

Ajouter un commentaire Commentaires
Messages postés
302
Date d'inscription
samedi 22 octobre 2005
Statut
Membre
Dernière intervention
2 novembre 2008
4
Le but principale de cette source est de retourner toutes les étapes nécessaires à l'obtension du PGCD, il faut donc afficher les étapes intermediaire ( pas fait dans votre source )

Merci quand même de votre participation ;-)
Messages postés
53
Date d'inscription
samedi 12 novembre 2005
Statut
Membre
Dernière intervention
25 août 2008

Ouép je pensais à une fonction dans le genre ^^
Mais là tu calcules 2 fois le reste, tu devrais plutôt le stocker dans une variable :

function greatest_common_divisor($a, $b){
if(!is_int($a) || !is_int($b)) return false;
$reste = $a%$b;
return $reste==0 ? $b : greatest_common_divisor($b, $reste);
}
Messages postés
40
Date d'inscription
dimanche 5 octobre 2003
Statut
Membre
Dernière intervention
1 octobre 2006

Bonsoir à toi, Iow4 !

En effet, je crois qu'il existe plus court ;=)
Je ne l'ai pas testé, car j'ai eu un crash de mon serveur Web... mais je te laisse l'essayer toi-même...

Elle devrait fonctionner, c'est un reste de ma vieille mémoire ;=) :

function greatest_common_divisor( $a, $b )
{
if ( is_int( $a ) && is_int( $b ) )
{
return ( $a % $b ) ? greatest_common_divisor( $b, $a % $b ) : $b;
}
}

Bonne soirée à toi !
N'hésite pas à me dire si elle fonctionne ;=)
Messages postés
302
Date d'inscription
samedi 22 octobre 2005
Statut
Membre
Dernière intervention
2 novembre 2008
4
Si tu trouve le moyen d'en faire une plus simple je t'ecoute bien volontier.
Tu entends quoi par "resultat" ?

Les gens qui ne veulent pas voir les opérations intermediaire utilise la fonction de PHP toute faite.
Messages postés
53
Date d'inscription
samedi 12 novembre 2005
Statut
Membre
Dernière intervention
25 août 2008

Ok, j'hésitais entre le fait que tu sois en 3ème ou en Terminale spé maths.
Car en spé maths on revoit le pgcd rapidement. Et comme malgré la simplicité du code, tu a l'air assez expérimenté...
Mais je pense que ta fonction peut-être encore beaucoup plus simple. Le problème c'est qu'elle ne se contente d'afficher un résultat.
Il faudrait qu'elle renvoit en plus les résultat, et mettre par exemple un argument optionnel permettant d'activer ou nom l'affichage des étapes.
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.