+- N-PN White-Hat Project (https://dev.n-pn.fr/forum)
+-- Forum : Programmation (https://dev.n-pn.fr/forum/forumdisplay.php?fid=72)
+--- Forum : Langages interprétés (https://dev.n-pn.fr/forum/forumdisplay.php?fid=27)
+--- Sujet : [PHP] apprendre la récursivité (jeu des tours de hanoi) (/showthread.php?tid=2689)
[PHP] apprendre la récursivité (jeu des tours de hanoi) - JadnX - 12-02-2013
Salut à tous,
Je vous partage un cours que j'ai eu sur la programmation, l'objectif est d'apprendre la récursivité, grâce à un jeu qui s'appel " Les Tours d'Hanoï ".
Je vais vous décrire, ou plutôt wiki, brièvement le principe du jeu:
Wiki a écrit :Merci Wikipedia ! :pLe problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de «départ» à une tour d'«arrivée» en passant par une tour «intermédiaire», et ceci en un minimum de coups, tout en respectant les règles suivantes :
- on ne peut déplacer plus d'un disque à la fois,
- on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.
![[Image: 300px-Tower_of_Hanoi.jpeg]](http://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Tower_of_Hanoi.jpeg/300px-Tower_of_Hanoi.jpeg)
C'est bien beau, mais la récursivité quésaco..!?
La récursivité pour une fonction c'est le fait de faire appel à elle même, c'est un espèce d'empilage de la même fonction !
Prenez par exemple le film INCEPTION avec Leonardo DiCaprio
, ils descendent à travers plusieurs niveaux de rêves (des rêves imbriqués les un dans les autres) pour pouvoir arriver à un résultat qui est d'introduire une idée dans l'esprit d'un bouffon. (mes excuses aux fans !)Dans notre cas :
Le résultat est de trouver les déplacements à faire pour pouvoir déplacer la pile de disques.
La fonction, n'est pas le rêve mais, c'est le mouvement à répéter pour pouvoir arriver au résultat.
Problème, comment trouver le mouvement !?
On va donner des nom à nos trois tours ! Celle la plus à gauche sera la tour de départ ($td) la tour du milieu intermédiaire ($ti) et celle de droite la tour d'arrivé ($ta).
Résolvons le jeu avec 3 disques et relevons les mouvements. (simple non ?
) Vous pouvez testé ICI:td -> ta
td -> ti
ta -> ti
td -> ta
ti -> td
ti -> ta
td -> ta
Bien
maintenant interprétons :1) on part du départ pour tous stocker sur l'intermédiaire !
td -> ta
td -> ti
ta -> ti
on résume => td devient ti et ti devient td
2) on fait le but du jeu on va du départ à l’arrivé !
td -> ta
3) on prend ce qu'on a stocker sur l'intermédiaire pour le mettre sur l'arrivé !
ti -> td
ti -> ta
td -> ta
on résume => ti devient ta et ta devient ti
Application PHP:
On va donc crée la fonction principale hanoi qui va nous permettre d'arrivé au résultat (déplacement du 2 ci dessus):
Code PHP :
hanoi($td, $ti, $ta){} //on met en paramètres le départ l'intermédiaire et l'arrivé.
On fait la fonction pour le 1er déplacement (déplacement du 3 ci dessus):
Code PHP :
hanoi($td,$ta,$ti); //ti devient ta et ta devient ti.
On fait la fonction pour le 2eme déplacement (déplacement du 1 ci dessus):
Code PHP :
hanoi($ti, $td, $ta); //td devient ti et ti devient td.
Si vous m'avez suivis jusque là c'est bien, le plus gros est fait !
On construit la fonction pour 3 disques :
Code PHP :
function hanoi($td,$ti,$ta){ // pour aller au résultat
hanoi($td,$ta,$ti); // on fait un déplacement
hanoi($ti,$td,$ta); // puis le second
}
On y ajoute le nombre de disque pour pouvoir faire les déplacement,
ainsi qu'une vérification inutile de faire les déplacement si il n'y a qu'un disque :
Code PHP :
function hanoi($nb, $td, $ti, $ta) {
if ($nb == '1') {
echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
} else {
hanoi($nb - 1, $td, $ta, $ti);
echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
hanoi($nb - 1, $ti, $td, $ta);
}
}
Pour finir on y ajoute un formulaire pour demander le nombre de disques à l'utilisateur :
Code PHP :
header('Content-type: text/html; charset=utf-8');
$formulaire = '<form method="post" action="">
<label for="var1">Nombre de disques :</label>
<input type="text" name="var1" id="var1" />
<br />
<input type="submit" name="submit" value="Envoyer" />
</form>';
if (isset($_POST['submit'])) {
$n = $_POST['var1'];
function hanoi($nb, $td, $ti, $ta) {
if ($nb == '1') {
echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
} else {
hanoi($nb - 1, $td, $ta, $ti);
echo 'Déplacer ' . $td . ' vers ' . $ta . '<br />';
hanoi($nb - 1, $ti, $td, $ta);
}
}
hanoi($n, 'td', 'ti', 'ta');
} else {
echo $formulaire;
}
Voila pour la récursivité on utilise la fonction hanoi dans la fonction hanoi...
Un rêve dans un rêve dans un rêve...
N’hésitez pas à m’envoyer un message pour corriger d’éventuelles erreurs ou fautes d’orthographes.
Un merci fait toujours plaisir !
En espèrent vous aider autant que vous le faites pour moi,
Cordialement,
JadnX
RE: [PHP] apprendre la récursivité (jeu des tours de hanoi) - InstinctHack - 12-02-2013
Merci du tuto
Autre exemple, peut-etre plus parlant, celle du parcours récursive d'un dossier, compliqué à mettre en place sans appeller une fonction par elle-meme
Et voilà un exemple de code simple à comprendre :
Code PHP :
<?php
function liste_Dirs($dir)
{
$output = '<ul>';
$dossier = opendir($dir);
while($item = readdir($dossier))
{
$berk = array('.', '..'); // ne pas tenir compte de ses répertoires / fichiers
if (!in_array($item, $berk))
{
$new_Dir = $dir.'/'.$item;
if(is_dir($new_Dir))
{
$output .= '<li><strong>'.$item.'</strong></li>';
$output .= liste_Dirs($new_Dir);
$output .= '</li>';
}
else
{
$output .= '<li>'.$item.'</li>';
}
}
}
$output .= '</ul>';
return $output;
}
// on appelle la fonction de cette façon :
echo liste_Dirs('./');
?>
source : http://www.viaphp.net/portions/fichiers-repertoires/4-lecture-recursive-d-un-repertoire
Et pour finir, celle de la fonction mathématiques factorielle (qui définie x multiplier par tous les entiers positifs inférieurs à lui)
en gros
4! == 4*3*2*1 == 4*3*2
(elle représente par exemple, le nombre d'ordres possible avec des élements)
avec 3 boules : [1] [2] [3]
les ordres possibles sont:
[1] [2] [3]
[1] [3] [2]
[2] [1] [3]
[2] [3] [1]
[3] [1] [2]
[3] [2] [1]
Bien que php possède des fonctions mathématiques (http://php.net/manual/fr/book.math.php), ainsi que des modules (http://www.php.net/manual/fr/ref.gmp.php) il est facile de coder soi-même cette fonction
voici donc l'équivalent de la fonction http://www.php.net/manual/fr/function.gmp-fact.php
Code PHP :
<?php
function factorielle($nbre)
{
//Si $nbre = 0 on retourne 1 car soit 1! = 1, soit on est arrivés à la fin du calcul
if($nbre === 0)
{
return 1;
}
else //Sinon on retourne le nombre multiplié par le reste de sa factorielle (avec $nbre décrémenté)
{
return $nbre*factorielle($nbre-1);
}
}
//On affiche la factorielle de 6
echo factorielle(6);
Le code est extrait du ce tuto http://www.siteduzero.com/informatique/tutoriels/initiation-a-la-recursivite-en-php-notions-mise-en-oeuvre-et-utilisation
voilà pour un petit rajout sympa
