Calculer le PGCD de deux nombres !

Bonjour les débutants ,

Règles de l'exercice :

Aujourd'hui, je vous propose de coder un tout petit script qui sera chargé de trouver le PGDC de deux entiers relatifs.

Heu ... deux petites secondes, c'est quoi le PGCD ?

Quoi ? ça ne vous dit rien du tout ? Allons, reprenez vos bouquins de 3ème et feuilletez-le ... C'est bon, ça vous revient ? :p) Bon, pour ceux à qui ça ne dit toujours pas (les mauvais élèves ><), lisez cette article. ^^

Pour parvenir à vos fins, je vous propose d'utiliser l'algorithme d'Euclide. C'est pour moi le plus rapide de tous (et il n'est pas plus compliqué que les autres). Si vous ne le connaissez pas, je vous propose de lire ceci. N'hésitez pas à le relire plusieurs fois si vous ne le comprenez pas, mais normalement ça ne devrait pas vous poser de soucis.

Enfin, votre code devra se présenter sous la forme d'une petite fonction (deux arguments requis : nombre1 et nombre2 par exemple) qui retournera ... le PGCD bien sûr !

Un petit exemple :

<?php

$pgcd = pgcd(15, 12);
echo $pgcd; // Le résultat est 3 !

?>

Difficulté : /

Astuces : Aucune ! Débrouillez-vous !

Bonne chance à tous les participants !

NB : La correction dans quelques jours !

Peut-tu mettre la mise en page?
Merci
Clique Ici pour voir la mise en page

Voilà, c'est fait ! Tu comptes participer au concours ?

Ouais je vais tenter !

Fini !

Code:

<?php
function pgcd($nombre,$nombre2){

  while($nombre>1){
        $reste = $nombre%$nombre2;

        if($reste == 0){
        break; // sorti quand resultat trouvé
        }

        $nombre=$nombre2;
        $nombre2=$reste;
    }
return $nombre2; // retourne le resultat
}
if(isset($_POST['i']) && isset($_POST['j'])){
extract($_POST);
$pgcd = pgcd($i, $j);
echo "Le PGCD de $i et $j est $pgcd";
}
?>
<form method="post" action="pgcd.php">
<p>Nombre 1</p><input type="text" name="i"/><br/>
<p>Nombre 2</p><input type="text" name="j"/><br/>
<input type="submit" value="Calculer le PGCD !"/>
</form>

Etant donné que la fonction pgcd() n'existe apparemment pas, j'ai dû la créer, d'où le

Code:

function pgcd($nombre,$nombre2)

Voilà !
Si vous avez des questions posez-les ici ^^

Ta solution est pas mal mais comment repéres-tu le plus grand nombre du plus petit ? :p

Voilà ma solution :

Code:


<?php

function pgcd($nombre1, $nombre2)
{
    $dividende = max($nombre1, $nombre2);
    $diviseur = min($nombre1, $nombre2);
 
    while(1)
    {
        $reste = $dividende % $diviseur;
     
        if($reste != 0)
            $pgcd_tmp = $reste;
        else
            break;
     
        $dividende = $diviseur;
        $diviseur = $reste;
    }
 
    $pgcd = $pgcd_tmp;
 
    return $pgcd;
}

$pgcd = pgcd(15, 12);
echo $pgcd;

?>


C'est pas pour vous enfoncer, mais je fait beaucoup plus court :

Code:

function pgcd($a, $b)
{
  if($a<$b)
      list($a, $b)=array($b, $a);

  if($a%$b==0)
      return $b;
  else
      return pgcd($b, $a%$b);
}

Le fonctionnement est très simple :
Le PCGD de deux nombre a et b, c'est le PGCD de b et du reste de la division euclidienne (= modulo) a/b, jusqu'à ce que a modulo b (= reste de la division euclidienne a/b) soit égale à 0.
Le tout avec a>b.
Voilà pour la partie algorithmique.

Ensuite, voici l'explication du fonctionnement de la ligne 4 : list($a, $b)=array($b, $a);
C'est surement la ligne la plus compliqué du code. Elle permet d'inverser les valeurs de $a et de $b. Au niveau du fonctionnement, c'est plus complexe. En fait on peut considérer ça comme une assignation multiple (= plusieurs assignations en une seul ligne).

Code:


list($a, $b ,$c)=array('coca', 'limonade', 'café');
// fait la même chose que :
$a = 'coca;
$b = 'limonade';
$c = 'café';


L'avantage ici, c'est que l'on ne peut pas faire :

Code:

// $a = 10 et $b = 5
$a = $b; // $a = 5
$b = $a; // $b = 5
// on se retrouve avec $a == $b


On peut éviter ça en utilisant une variable temporaire :

Code:


$tmp = $a;
$a = $b;
$b = $tmp;


Mais c'est quand même plus simple d'utiliser list() :

Code:


list($a, $b) = array($b, $a);


Voilà, si vous voulez plus d'explication, n'hésitez pas

Merci pour tes explications, mais je connaissais la fonction list. ^^

Par contre bravo pour l'utilisation de la récursivité hein, j'y avais pas du tout pensé. ^^