Série 4 : Structures de données, récursion et algorithmes (suite)

9 mai 2001

Introduction

Dans cette série nous laissons tomber l'exemple de la banque et des comptes en banque et vous proposons de petits exercices qui devraient vous permettre de vous familiariser avec la récursion et l'algorithmique.

1   La fonction factorielle

Définition mathématique :
A faire [10 lignes environ]:
Ecrire et tester la fonction factorielle.

2   La suite de Fibonacci

Définition mathématique :
A faire [15 lignes environ]:
Ecrire un programme qui affiche les n premiers nombres de la suite de Fibonacci, n étant un nombre demandé à l'utilisateur.

Exemple d'exécution du programme :

Afficher la suite jusqu'à : 10
fibo(0) = 0
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2
fibo(4) = 3
fibo(5) = 5
fibo(6) = 8
fibo(7) = 13
fibo(8) = 21
fibo(9) = 34
fibo(10) = 55

3   Les tours de Hanoi

Si vous ne savez plus quelles sont les règles de ce jeu, reprenez votre cours d'amphithéâtre de la semaine dernière ou visitez la page suivante qui propose en outre une applet pour s'essayer soi-même à ce petit casse-tête. Mais pas trop longtemps, pour avoir le temps d'écrire le petit programme qui résout tout seul ce problème apparemment compliqué.

Spécification :
Il s'agit d'écrire une fonction qui prend en argument un nombre n d'étages, un piquet de départ A, un piquet de destination B et un piquet transitoire C, et qui affiche à l'écran les mouvements à effectuer pour faire passer les n étages supérieurs du piquet A vers le piquet B en s'aidant du piquet C.

Exemple d'exécution du programme :

Nombre d'étages sur le premier piquet : 3
Solution :
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2
Implantation :
L'idée de l'algorithme est la suivante :
  1. Si n est nul (condition d'arret), il n'y a rien à faire.
  2. Si n n'est pas nul, on déplace récursivement n-1 étages du piquet A au piquet C en s'aidant du piquet B.
  3. Puis on affiche le déplacement d'un étage du piquet A au piquet B.
  4. Enfin on déplace récursivement n-1 étages du piquet C au piquet B en s'aidant du piquet A.
A faire [30 lignes environ]:
Ecrire un programme qui affiche les mouvements à effectuer pour résoudre le problème des tours de Hanoi.

4   Le tri rapide (facultatif)

Il existe de nombreux algorithmes pour trier une liste d'éléments comparables. Le tri rapide ou quick sort est l'un des plus rapides. On peut montrer que s'il y a n éléments à trier, l'algorithme mettra en moyenne n.log(n) étapes pour les trier. En comparaison, l'algorithme qui consiste à extraire successivement le plus petit élément de la liste peut utiliser jusqu'à n2 étapes pour arriver au même résultat. Sur de petites listes la différence est minime, mais on peut très vite gagner plusieurs heures de calcul en utilisant l'un plutôt que l'autre.

Spécification :
Il s'agit d'écrire une fonction qui prend en argument une liste d'entiers et qui retourne comme résultat une liste triée contenant les mêmes éléments que la liste de départ.

Implantation :
L'idée de l'algorithme est la suivante :
  1. Si la liste est vide ou ne contient qu'un élément, elle est déjà triée. Il n'y a rien à faire.
  2. Si elle contient au moins 2 éléments, on prend le premier (qu'on appelle désormais le pivot), et on sépare le reste de la liste de départ en deux sous-listes : l'une contenant les éléments plus petits que le pivot, l'autre les éléments plus grands.
  3. On trie récursivement les deux sous-listes obtenues.
  4. On colle la deuxième liste à la première en n'oubliant pas d'intercaler notre pivot.
Indication :
On se propose de réaliser une fonction de tri sur place, c'est-à-dire que la liste à trier est remplacée par la liste triée à la fin du processus de tri. L'avantage est qu'aucune allocation ou désallocation de mémoire n'est requise pendant le tri, ce qui contribue à le rendre encore plus rapide.

Pour vous faire gagner du temps, le squelette contient aussi du code pour générer une liste de façon aléatoire.

A faire [30 lignes environ]:
Compléter le fichier tri.C (vous pouvez le copier-coller dans emacs).

Exemple d'exécution du programme :

Longueur de la liste à trier : 20
Liste générée : 16 12 6 0 6 3 19 10 7 2 1 9 12 6 15 13 15 17 6 3 
Liste triée   : 0 1 2 3 3 6 6 6 6 7 9 10 12 12 13 15 15 16 17 19
This document was translated from LATEX by HEVEA.