TD 4 et 5 : Objets et récursion

1. Permutations.
Construire la classe Permutation qui comporte un tableau pour la permutation et des champs pour sa longueur, pour son nombre de cycles et sa signature.
Créer dans la classe les méthodes suivantes:
- Inverse pour calculer la permutation inverse;
- Cycles qui calcule la décomposition en cycles et retourne un tableau qui les stocke;
- Inversions qui calcule le vexcteur des inversions de la permutation;
- tt Generation qui fabrique une permutation aléatoire.

2. Tris.
Écrire les méthodes itératives qui permettent de trier des tableaux d'entiers selon les méthodes suivantes:
- tri par sélection, qui recherche le minimum et le met en position 0, puis qui recherche le second plus petit et le met en position 1, etc.;
- tri par insertion, qui range les deux premiers éléments dans l'ordre, puis place le troisième au bon endroit par rapport aux deux précédents, puis place le quatrième au bon endroit par rapport aux trois précédents, etc.

3. Récursion.
On va transformer trois programmes déjà écrits en version récursive:
- la fonction factorielle;
- le calcul des coefficients binomiaux;
- le calcul de la médiane d'un ensemble d'entiers.