Pgcd : algorithme d'euclide par recursivité

Soyez le premier à donner votre avis sur cette source.

Snippet vu 18 341 fois - Téléchargée 28 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
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
24 oct. 2006 à 20:18
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 ;-)
Skreo Messages postés 53 Date d'inscription samedi 12 novembre 2005 Statut Membre Dernière intervention 25 août 2008
2 oct. 2006 à 18:01
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);
}
cs_Kevin007 Messages postés 40 Date d'inscription dimanche 5 octobre 2003 Statut Membre Dernière intervention 1 octobre 2006
1 oct. 2006 à 21:48
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 ;=)
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
1 oct. 2006 à 19:02
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.
Skreo Messages postés 53 Date d'inscription samedi 12 novembre 2005 Statut Membre Dernière intervention 25 août 2008
26 sept. 2006 à 12:53
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.