[FONCTION RÉCURSIVE] DETERMINER LE PGDC DE DEUX NOMBRES

Evangun Messages postés 1980 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 24 septembre 2012 - 10 août 2006 à 14:45
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 - 25 sept. 2006 à 17:38

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/39030-fonction-recursive-determiner-le-pgdc-de-deux-nombres

iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
25 sept. 2006 à 17:38

Hello j'ai moi même codé une fonction recursive pour le PGCD de deux nombre mais qui affiche les étapes si ça interesse :

http://www.phpcs.com/codes/PGCD-ALGORITHME-EUCLIDE-RECURSIVITE_39603.aspx

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
15 août 2006 à 01:16

à mon avis, le is_int doit se faire dans une première fonction (fonction de lancement) et le reste dans une seconde fonction (fonction de calcul) histoire de faire moins de vérifications de type

Palleas_44 Messages postés 130 Date d'inscription lundi 12 décembre 2005 Statut Membre Dernière intervention 19 avril 2009
11 août 2006 à 13:16

Ah ui c'est pas mal, dans tout les cas il y a toujours la fonction php qui fait ca tres bien aussi ^^

cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
11 août 2006 à 10:12

Yep ;)
No pb de toute facon, c'est marrant de voir des fonctions récursives héhé ^^
Voici une version itérative d'Euclide qui a l'air de marcher pour ceux que ca intéresseraient :
function pgcd_($a,$b) {
for($c = $a % $b ; $c != 0 ; $c = $a % $b) { $a = $b; $b = $c; }
return $b;
}

Palleas_44 Messages postés 130 Date d'inscription lundi 12 décembre 2005 Statut Membre Dernière intervention 19 avril 2009
10 août 2006 à 20:44

Pitite mise à jour, effectivment cette méthode est celle des soustractions successives :$ j'ai confondu les deux algos, autant pour moi ^^

cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
10 août 2006 à 15:28

Non...
L'algorithme d'Euclide, c'est effectuer des divisions entières successives, en décalant diviseur et reste.. pas des soustractions.
Fondamentalement, une division revient peut être à une soustraction, mais bon là, ca fait un peu tout péter sur de grands nombres ^^

Click: http://villemin.gerard.free.fr/ThNbDemo/AlgoEucl_fichiers/image004.gif

Palleas_44 Messages postés 130 Date d'inscription lundi 12 décembre 2005 Statut Membre Dernière intervention 19 avril 2009
10 août 2006 à 15:21

C'est l'algorithme d'Euclyde qui est comme ca...

cs_PaDa Messages postés 1804 Date d'inscription mardi 15 juillet 2003 Statut Membre Dernière intervention 22 septembre 2009 5
10 août 2006 à 15:20

<?php echo PGCD(40000,1); ?>
Erreur 502.. Glurps.

Il aurait sûrement été plus malin d'exécuter de vraies divisions/multiplications/modulos, plutot que de réinventer le principe de la division.. Là tu fais exploser la mémoire en étant si "brutal". Cela dit ca semble marcher sur de petits nombres ^^

Evangun Messages postés 1980 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 24 septembre 2012 4
10 août 2006 à 14:45

Bonjour, il y a aussi la fonction gmp_gcd() : php possède beaucoup de fonctions mathématiques en natif.
Après, je ne suis pas super matheux alors je ne peux pas savoir s'il y a moyen de calculer autrement ;^)

Discussions similaires

Parcourir des repertoires (fonction recursive)

génerateur de nombre aléatoire

calcul d'un nombre de jours entre deux dates

Calculer le nombre de jour entre deux dates

interval entre deux date en mois seulement

Votre réponse

Discussions similaires