Version imprimable
Bonjour tout le monde,
voila j'ai un problème avec la récursivité. Je suis censé programmer un tri par sélection de manière récursive mai je vois pas du tout comment faire. Est ce que quelqu'un pourrai m'expliquer en gros la logique d'un tel tri?
merci beaucoup
Tu peux regarder ici :
http://algo.developpez.com/
Notamment ici :
http://algo.developpez.com/sources/?...#tri_selection
Salut,
La première chose à savoir, c'est que la récursivité peut, tres souvent, etre remplacée intelligemment par une boucle qui fera le travail :P
Evidemment, si c'est pour un travail scolaire, ou dans d'autres circonstances, on peut aussi etre tenu d'appliquer la récursivité, alors qu'il serait vraissemblablement plus facile de faire sans... Donc... il est peut etre intéressant de rappeler ce qu'est la récursivité, et comment arriver à l'envisager sereinement ;)
La récursivité, c'est quoi:question: c'est tout simplement une fonction qui est en mesure de s'appeler elle-même.
Le problème, c'est que si la fonction s'appelle elle-même, elle risque fort de le faire "ad-vitam", et donc qu'il faut trouver le moyen pour que, quoi qu'il arrive, elle finisse par se trouver dans une situation où elle arretera de le faire.
Cette situation dans laquelle la fonction ne se rappellera plus elle-meme est ce que l'on nomme "le cas de base", et l'ensemble des parametres passés à la fonction n'aura qu'un seul but: atteindre ce "cas de base".
Typiquement, l'action qui sera effectuée dans le cas de base est relativement simple: soit on en fait purement et simplement rien (si la fonction ne doit renvoyer aucune valeur), soit, on renvoit la valeur "de base" (celle qui permettra, de proche en proche, de calculer la suite)
Le gros du travail consiste donc, finalement, à pas grand chose:
- déterminer le cas de base
- déterminer le moyen d'atteindre le cas de base
- savoir comment modifier le cas de base pour pouvoir le renvoyer à l'appel précédent...
L'algorithme générique est du genre de
Deux exemples, parfaitement inutiles (hormis leur coté didactique) de récursivité seraient le calcul de l'élévation à l'exposant N d'une valeur et celui de la factorielle d'un nombre:Code:
2
3
4
5
6
7
8
9
Pour le problème qui t'intéresse, il nous manque trois données primordiales pour te répondre correctement: ce que tu dois trier, l'ordre de tri et le critère de tri...Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
En effet, les actions à mener pour tendre vers le cas de base et le cas de base seront vraissemblablement différentes si tu dois simplement trier un tableau ou si tu dois trier une structure dynamique (liste ou arbre binaire/naire), si tu dois les trier par ordre croissant ou décroissant et si le tri doit s'effectuer sur un critère ou sur plusieurs critères, ce qui influencera fortement l'algorithme à mettre au point...
Si, apres ces explications, la récursivité n'est pas claire pour toi, tu peux toujours passer sur ==>cette page<== où elle est expliquée en long, en large et en travers.
Retiens également que la création de l'algorithme vient apres une étape primordiale: l'expression claire nette et concise des besoins de l'application à concevoir...
Or, tu avoueras que
fait un peu léger comme expression de ce qu'il te faut ;)Citation:
un tri par sélection de manière récursive
En plus, il n'est pas d'usage sur ce forum de faire tout le travail à ta place: c'est le pire des services que l'on puisse te rendre, car cela mene bien souvent à faire quelque chose que tu n'aurais peut etre pas compris...
Si tu as un problème de compréhension sur un point bien précis, n'hésite pas à poser la question
Si tu as un problème à un moment bien précis de l'algorithme, montre nous ce que tu as déjà fait, et indique nous le problème que tu n'arrive pas à résoudre
Ce n'est qu'ainsi que tu obtiendras une aide à la fois efficace (pour résoudre ton problème) et utile (pour te permettre de comprendre et d'adapter la solution par la suite ;)
/me se souvient avec emotion de son premier algo récursif.
C'était a mes débuts en progs, et avec mon binôme de l'époque on devait colorier une zone (pour refaire un paint). Il fallait donc parcourir (et stocker) tous les points pour changer leur couleurs.
C'était en turbo pascal, et ca a été mon premier bug vraiment difficile à corriger "Stack overflow error" :aie: . L'algo était nickel sur le papier, mais une fois implémenté, la mémoire explosait pour des images plus grande que... 2cm² sur l'écran. J'ai refait l'algo differement, et on a pu colorier une image un peu plus grande, mais ca explosait toujours dans certains cas (genre colorier une image completement blanche).
Pour finir un prof nous a expliqué que la plupart du temps, un algo récursif peut se faire avantageusement remplacer par un while, et la, plus de soucis de mémoire ;-)
Sinon, pour revenir a ton problème, ben... je crois pas pouvoir en dire beaucoup plus que Koala01. Montre nous ce que tu as déjà ou ce qui te pose problème pour commencer et on verra ce qu'on peut faire ^_^
Bonjour
Je suis désolé. Je sais que ce post est assez vieux mais c'est exactement ce que je cherche ( ou presque ).
Il faut que je fasse un tri par sélection de manière récursive. Il faut que je tri un tableau à indice simple dans l'ordre croissant.
Je suis pas sur de savoir ce qu'est le critère de tri mais bon...Citation:
ce que tu dois trier, l'ordre de tri et le critère de tri...
Je ne recherche pas du code mais plutot la logique. Je ne vois pas ce que peut être le cas de base à retourner. Est-ce que le programme est aussi court que pour calculer une factoriel ( avec un si ... sinon... et 2 instructions seulement ) ? Ou est-ce qu'il faut développer un peu plus ?
Merci
Le critère de tri, c'est la méthode que tu utilises pour savoir quel élément est supérieur a un autre. Pour faire un cas simpleCitation:
Je suis pas sur de savoir ce qu'est le critère de tri mais bon...
"aaaa" "b".
Si le critère de tri est l'ordre alphabétique, le "aaaa" arrive en premier.
Si le critère est le nombre de lettres, alors "b" arrive en premier.
Sinon pour revenir plus précisement a ta question, si je me souvient bien de mes cours d'algo, dans un tri par selection, du doit trouver l'élément le plus grand, le mettre a la fin du tableau et recommencer.
Intuitivement, ce que je ferai (ca n'est probablement pas optimal) c'est une fonction avec le tableau a trier en parametre. Premiere itération, je recherche l'élément le plus grand, je le sauve, puis je relance la fonction avec le même tableau moins l'élément que je vient de trouver (genre du peux passer l'élément a -1 si tu ne teste que des entiers positifs, ou autres astuces du genre) puis je continue jusqu'a ce qu'il ne reste plus que les éléments "éliminé" dans le tableau.
Ensuite je dépile, donc je retourne un tableau avec en derniere position l'élément que je viens de trouver (ici on est au niveau le plus profond, donc le tableau ne contient qu'un seul élément, le plus petit du tableau). Puis on remonte d'un niveau, et je retourne le tableau que j'ai récupéré avant, après avoir rajouté en derniere position l'élément trouvé a ce niveau, et ainsi de suite.
Et au final on se retrouve avec un tableau trié par ordre croissant ;-)
Merci je commence à y voir un peu plus clair.
Mais quand tu dis qu'il faut savegarder l'élément, tu le sauvegarde comment ?
J'ai essayé un programme :
Au premier appel, je cherche dans le tableau la valeur maximale avec la boucle for. max étant la valeur maximale et Pmax la position de la valeur maximale. Une fois que j'ai trouvé dans le tableau la valeur max, je l'intervertis avec la dernière valeur du tableau grâce à :Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Puis je rappelle la fonction avec pour arguments le tableau puis comparaison - 1, c'est à dire qu'au prochain appel, la fonction va recherché la valeur la plus grande sans tenir compte de la dernière case.Code:
2
3
4
5temp = tableau[Pmax]; tableau[Pmax] = tableau[comparaison]; tableau[comparaison] = temp; triSelection( tableau, comparaison - 1 );
Avec :
si comparaison vaut 0, alors c'est que le tableau est trié. Le code est en c++, normalement les tableaux sont appelés par référence, il est directement modifié depuis la fonction principal.Code:if ( comparaison > 0 )
Le compilateur compile ( c'est pas terrible à dire mais je sais pas comment dire autrement :D ) mais lors de l'execution du programme, il met un message d'erreur et se ferme. Je ne pense pas que se sois la mémoire puisque j'ai essayé avec un tableau de 5 éléments. J'ai pas fait exactement comme tu m'a expliqué, mais ton expliquation m'a bien aidé quand même.
Si on pouvais m'expliqué où le programme bogue. :help:
merci.
Quand on travaille avec des tableaux en C et en C++, il est primordial de garder une information en tête: les index commencent à 0.
Cela signifie que si tu as un tableau de N élément, le dernier index valide est N-1 ;)
Dés lors, il faut décider de la signification que l'on donne au deuxième paramètre de la fonction:
- Soit, il s'agit du nombre d'éléments qu'il reste à trier,
- Soit il s'agit de la valeur du dernier index valide à tester
Généralement, on optera pour la première solution... Mais cela sous entend que, chaque fois que l'on fera appel à la valeur fournie, l'index correspondant sera cette valeur - 1...
Avant d'écrire la première ligne de code, il est - comme toujours - nécessaire de réfléchir correctement à l'ensemble de ce qui doit être fait...
Il faut commencer par réfléchir aux informations qui doivent être fournies à la fonction, et à ce qu'elle doit renvoyer.
Ce qu'elle doit renvoyer, c'est relativement simple: il s'agit d'un pointeur sur le premier élément du tableau...
Ce qu'il faut lui fournir comme paramètres, ce n'est pas beaucoup plus compliqué:
- un pointeur sur le premier élément du tableau
- le nombre (sous la forme d'un entier - tant qu'à faire - non signé) d'éléments à prendre en compte
Ce qui nous donnera une fonction dont le prototype sera de l'ordre de
Comme tu semble d'avis de partir sur une optique récursive, il faut donc réfléchir au cas de base.Code:int* TriParSelection(int* tab, size_t count)
Il n'est pas bien compliqué à saisir: s'il n'y a qu'un seul élément à tester, le travail est fini :D
On partirait donc sur un algorithme dont la base serait
La logique de la fainéantise nous incitera cependant, étant donné qu'il faut renvoyer tab de toutes manières, à inverser le test, et à transformer l'algorithme enCode:
2
3
4
5
6
7
8
9
Mais, il y a toujours une étape qui reste très floue: c'est "tri de tab"...Code:
2
3
4
5
6
7
La question que l'on se posera fatalement, c'est "Comment trier tab" :question:
la réponse tient en une simple boucle et une inversion:
En remplaçant "tri de tab" par cette partie d'algorithme, on en arrive à l'algorithme finalCode:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Qu'il n'y a plus qu'à traduire en C++... et là, je vais te laisser faire :D (je t'ai déjà beaucoup trop aidé sur ce coup :roll:)Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
:merci: beaucoup
Je commence à y voir un peu plus clair dans ce qui est du récursif. Je vais me lancer dans sa programmation.
merci