Il manque encore le cas de la factorielle de zéro, qui vaut un. Au final, la fonction récursive fact() pourrait ressembler à
ceci, car une factorielle n’est possible qu’avec des entiers positifs :
Font fact(n:entier):entier
Début
Si n=0 Alors
Retourne 1
Sinon
Retourne n*fact(n-1)
FinSi
Fin
La même fonction en Java avec son programme d’accompagnement :
class chap6_fact {
static int fact(int n)
{
if(n==0) return 1;
else return n*fact(n-1);
}
public static void main(String[] args) {
int n;
n=fact(10);
System.out.println(n);
}
}
3. Un exemple pratique : les tours de Hanoi
Les tours de Hanoi sont un jeu de réflexion qui a été inventé en 1883 par N. Claus de Siam professeur au collège de LiSouStian. Si la curiosité vous a poussé à rechercher ces noms et villes, peutêtre avezvous eu une surprise : aucun
des deux n’existe. Ce sont en fait des anagrammes faisant croire que ce jeu a été inventé par un asiatique. Tout faux !
N. Claus de Siam est l’anagramme de Lucas D’Amiens, (Edouard Lucas en fait), né à Amiens, et LiSouStian est
l’anagramme de SaintLouis, nom du Lycée où Lucas enseignait.
Les tours de Hanoi dérivent d’une légende Hindou qui dit qu’un temple dispose de trois poteaux sur lesquels s’empilent
64 disques en or de diamètres différents. Les prêtres de Brahma déplacent continuellement les disques du premier
poteau vers le troisième en passant éventuellement par un poteau intermédiaire et en respectant quelques règles
simples :
q Ils ne peuvent déplacer qu’un seul disque à la fois.
q Ils ne peuvent déplacer un disque que dans un emplacement vide ou sur un disque de plus grand diamètre.
La légende dit aussi que quand les disques ont été empilés au début des temps, et que lorsque les prêtres auront fini
de les déplacer, ce sera la fin du monde.
Nul doute que si les prêtres de la légende avaient eu un ordinateur, nous serions tous déjà morts… Quoique !
Avec 64 disques il faut 2 64 1 déplacements (18446744073709551615 et uniquement sans se tromper), soit à
raison de un par seconde 584 542 046 090 ans (584 milliards d’années). Sachant que l’univers a environ 14 milliards
d’années (c’est théorique), il nous reste 570 milliards d’années pour en profiter. En plus, les disques en or doivent
être très lourds à déplacer.
Le jeu fait référence à Hanoï car dans la capitale du Vietnam, une anciennen colonie française, les toits de certaines
pagodes ont la forme de plateaux empilés.
L’algorithme récursif pour résoudre ce problème est un grand classique nécessitant un peu de torture mentale.
Supposons que vous sachiez déplacer n1 disques. Pour en déplacer n, il suffit de déplacer (n1) disques du piquet 1
au piquet 3, puis de déplacer le grand disque du piquet 1 au piquet 2, et de terminer en déplaçant les (n1) autres
disques du piquet 3 vers le piquet 2.
Soient :
- 3 -
© ENI Editions - All rigths reserved - Jonifar lina
143
ceci, car une factorielle n’est possible qu’avec des entiers positifs :
Font fact(n:entier):entier
Début
Si n=0 Alors
Retourne 1
Sinon
Retourne n*fact(n-1)
FinSi
Fin
La même fonction en Java avec son programme d’accompagnement :
class chap6_fact {
static int fact(int n)
{
if(n==0) return 1;
else return n*fact(n-1);
}
public static void main(String[] args) {
int n;
n=fact(10);
System.out.println(n);
}
}
3. Un exemple pratique : les tours de Hanoi
Les tours de Hanoi sont un jeu de réflexion qui a été inventé en 1883 par N. Claus de Siam professeur au collège de LiSouStian. Si la curiosité vous a poussé à rechercher ces noms et villes, peutêtre avezvous eu une surprise : aucun
des deux n’existe. Ce sont en fait des anagrammes faisant croire que ce jeu a été inventé par un asiatique. Tout faux !
N. Claus de Siam est l’anagramme de Lucas D’Amiens, (Edouard Lucas en fait), né à Amiens, et LiSouStian est
l’anagramme de SaintLouis, nom du Lycée où Lucas enseignait.
Les tours de Hanoi dérivent d’une légende Hindou qui dit qu’un temple dispose de trois poteaux sur lesquels s’empilent
64 disques en or de diamètres différents. Les prêtres de Brahma déplacent continuellement les disques du premier
poteau vers le troisième en passant éventuellement par un poteau intermédiaire et en respectant quelques règles
simples :
q Ils ne peuvent déplacer qu’un seul disque à la fois.
q Ils ne peuvent déplacer un disque que dans un emplacement vide ou sur un disque de plus grand diamètre.
La légende dit aussi que quand les disques ont été empilés au début des temps, et que lorsque les prêtres auront fini
de les déplacer, ce sera la fin du monde.
Nul doute que si les prêtres de la légende avaient eu un ordinateur, nous serions tous déjà morts… Quoique !
Avec 64 disques il faut 2 64 1 déplacements (18446744073709551615 et uniquement sans se tromper), soit à
raison de un par seconde 584 542 046 090 ans (584 milliards d’années). Sachant que l’univers a environ 14 milliards
d’années (c’est théorique), il nous reste 570 milliards d’années pour en profiter. En plus, les disques en or doivent
être très lourds à déplacer.
Le jeu fait référence à Hanoï car dans la capitale du Vietnam, une anciennen colonie française, les toits de certaines
pagodes ont la forme de plateaux empilés.
L’algorithme récursif pour résoudre ce problème est un grand classique nécessitant un peu de torture mentale.
Supposons que vous sachiez déplacer n1 disques. Pour en déplacer n, il suffit de déplacer (n1) disques du piquet 1
au piquet 3, puis de déplacer le grand disque du piquet 1 au piquet 2, et de terminer en déplaçant les (n1) autres
disques du piquet 3 vers le piquet 2.
Soient :
- 3 -
© ENI Editions - All rigths reserved - Jonifar lina
143