AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

  • PHP CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2009 07 05 00:13:55
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

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


Information sur la source

Catégorie :Maths & Algorithmes Classé sous : algorithme, fonction, maths, récursivité, pgcd Niveau : Initié Date de création : 10/08/2006 Date de mise à jour : 10/08/2006 20:43:57 Vu / téléchargé: 8 765 / 77
Auteur : Palleas_44 Site perso
Ecrire un message privé
Note :
Aucune note
Commentaire sur cette source (9)
Ajouter un commentaire et/ou une note

Description

J'avais besoin de determiner le PGCD de 2 nombres, j'ai voulu le faire avec une fonction recursive, elle marche très bien donc je la mets à dospisition ici, ca peut toujours servir même si ca mange pas de pain ^_^.
 

Source

  • <?php
  • /**************************************************
  • Calcul du pgcd de deux nombres
  • **************************************************/
  • function diff($n1,$n2) {
  • $tablo = array($n1,$n2,abs($n1-$n2));
  • sort($tablo,SORT_NUMERIC);
  • return $tablo;
  • }
  • function PGCD($n1,$n2) {
  • if(is_int($n1) && is_int($n2)) {
  • $tablo=diff($n1,$n2);
  • if($tablo[0]>0) {
  • return PGCD($tablo[0],$tablo[1]);
  • } else {
  • return $tablo[1];
  • }
  • }
  • }
  • ?>
<?php
	/**************************************************
			Calcul du pgcd de deux nombres
	**************************************************/
	function diff($n1,$n2) {
		$tablo = array($n1,$n2,abs($n1-$n2));
		sort($tablo,SORT_NUMERIC);
		return $tablo;
	}
	function PGCD($n1,$n2) {
		if(is_int($n1) && is_int($n2)) {
			$tablo=diff($n1,$n2);
			if($tablo[0]>0) {
					return PGCD($tablo[0],$tablo[1]);
			} else {
				return $tablo[1];
			}
		}
	}
?>

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

10 août 2006 20:43:57 :
J'ai confondu les algos, autant pour moi, mon année de troisieme est plutôt loin... :$

Commentaires et avis

signaler à un administrateur
Commentaire de Evangun le 10/08/2006 14:45:09

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 ;^)

signaler à un administrateur
Commentaire de PaDa le 10/08/2006 15:20:07

<?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 ^^

signaler à un administrateur
Commentaire de Palleas_44 le 10/08/2006 15:21:27

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

signaler à un administrateur
Commentaire de PaDa le 10/08/2006 15:28:07

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

signaler à un administrateur
Commentaire de Palleas_44 le 10/08/2006 20:44:59

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

signaler à un administrateur
Commentaire de PaDa le 11/08/2006 10:12:13

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;
}

signaler à un administrateur
Commentaire de Palleas_44 le 11/08/2006 13:16:06

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

signaler à un administrateur
Commentaire de coucou747 le 15/08/2006 01:16:27

à 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

signaler à un administrateur
Commentaire de iow4 le 25/09/2006 17:38:50

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

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

Cherche algorithme de devinette [ par ycochard ] Bonjour,Je cherche l'algorithme qui se trouve derrière ce petit jeu :http://www.akinator.com/aki_fr/ (attention les yeux, ça flashe)Vous savez comment probleme fonction mail [ par PSG_Silver ] Bonjour.je voudrai utilisé la fonction mail.je propose a l'utilisateur d'envoyer un mail a l'admin en remplissant une zone de texte.l'utilisateur est Variables ARRAY (Eclater une variable en fonction de ses keys) [ par dlimouzin ] Bonjour en ce superbe week-end de maiJ'utilise beaucoup dans la lecture de mes formulaires envoyés d'un script A vers un script Bla variable d'environ passer deux parametres a la fonction explode [ par omarboutkhoum ] slt t le monde,puis-je passer deux parametres a la fonction explode par exemple ': decouper une chaine a chaque foi qu'il ya 'espace' ou ':'.merci fonction php pour trouver une variable dans un tableau [ par TheArrow ] Salut à tous!Donc voilà, je suis face à un problème qui m'a l'air super simple à résoudre mais je ne trouve pas de réponse! donc je viens demander vot lien intrene et variable [ par bellaing ] bonjour :j'ai le même problème .Je cherche à faire un lien qui ne mène vers une autre partie de la même page et qui lance une fonction php!voici mon c in_array() [ par Epoc22 ] Bonjour a tous, J'ai un problème conçernant la fonction in_array(). En fait, je cherche à vérifier si le nombre<fo


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version


LG KP501
Entre 9€ et 159€


Visiter le guide achat

Photothèque Nouveau !

Photo alphabet langue des sourdsPhoto friends
Photo femme, Plage, Bien être,Photo maison 80 plan top 1

Visiter la photothèque


Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés
Temps d'éxécution de la page : 0,858 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.