TOUR HANOI
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
3 août 2004 à 23:43
vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 - 8 août 2004 à 10:39
vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 - 8 août 2004 à 10:39
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/25140-tour-hanoi
https://codes-sources.commentcamarche.net/source/25140-tour-hanoi
8 août 2004 à 10:39
8 août 2004 à 02:42
Et d'après le théorème de terminaison, une fonction récursive qui fonctionne doit utiliser une fonction décroissante dans un ensemble qui n'admet aucune fonction strictement décroissante (par exemple N)
C'est-à-dire simplifier un problème...
exemple simple : factorielle
On sait faire pour 0 : 0!= 1
Si on cherche pour 7 : trop compliqué -> on s'appuie sur 6!, là encore trop compliqué, etc... jusqu'à 0 : qu'on sait traiter
La programmation modulaire c'est juste le fait de décomposer en fonctions et sous-fonctions... rien d'algorithmique !
7 août 2004 à 18:27
conio.h pas standard
main() -> int main()
clrscr() pas standard
getch() pas standard
hanoi ne retourne rien donc mets la en void
7 août 2004 à 18:21
Pour ce qui est de la récursivité, je dirais qu'en effet il faut traiter à part les cas simple, ou les cas particuliers (il existe un sous ensemble sur lequel on sait résoudre le problème), et pour tous les autres cas, on doit trouver un processus qui nous permet ne nous ramener aux cas qu'on connait déja.
4 août 2004 à 10:46
4 août 2004 à 10:40
L'exemple le plus connu etant sans aucun doute la suite de fibonacci. La version récursive doit planter à l'indice 10 alors que la méthode itérative peut en supporter plusieurs milliers (et même certainement davantage)
Ceci-dit le passage à l'itératif est très souvent une simulation de la pile d'appels... en quelques sortes un tableau qui garde les résultats précédents.
D'après moi le récursif est plus beau (oui oui la beauté existe en informatique) mais moins performant.
D'ailleurs BruNews je parlerai plus d'amélioration de performances que d'optimisation car la méthode récursive a des avantages comme la lisibilité et la compréhensibilité.
Et pour teddy_bear, tu abordes ici tout juste les bases de la programmation récursive... Tu as d'ailleurs commis une faute dans ta fonction hanoi, puisqu'elle ne renvoie rien quand n<=0...
Je te rappelle le principe de base des algos récursifs :
- traitement du cas de base (c'est-à-dire le cas le plus simple)
- si le cas est plus compliqué, on découpe le problème en sous-problèmes un peu moins compliqués (diviser pour mieux régner!)
Ici tu n'as fait que la deuxieme partie
3 août 2004 à 23:43
Penche toi donc la dessus pour ta prochaine source, il y a des bouquins entiers sur le sujet.
Reflechir est toujours bon.
Bonne continuation.