MPSI {831, 832} Lycée Masséna TP 4 : Listes et récursivité 1 Fonctions sur les listes Exercice 1. Réécrivez les fonctions de sommation vues en cours pour sommer les entiers de 1 à N , l’une récursive terminale et l’autre non. Vérifiez la différence sur un grand entier, pour obtenir une exception de dépassement mémoire pour la version non récursive terminale. Exercice 2. L’option trace. Il est possible de tracer les appels à une fonction à l’aide de trace, elle s’utilise ainsi : trace "fonction";; où fonction est bien sûr le nom de la fonction à tracer. Recoder rapidement le calcul de la suite de Fibonacci récursif, et regardez ce que donne le calcul de F6 . Exercice 3. Quelques fonctions sur les listes. Écrire des fonctions prenant en entrée une liste et effectuant les actions suivantes. On parcourera la liste une seule fois si possible (ça l’est !). On peut introduire une fonction auxiliaire interne. — three_or_more qui teste si la liste possède au moins trois éléments. — avant_dernier donnant l’avant dernier élément de la liste (si il existe, sinon renvoie une erreur). — maxi qui donne le maximum d’une liste. — nb_maxi qui donne le nombre d’occurences du maximum d’une liste (on calculera le maximum en même temps !) — somme qui calcule la somme des éléments d’une liste (d’entiers) — moyenne qui calcule la moyenne des éléments de la liste (de flottants). — records qui calcule le nombre de records d’une liste, c’est à dire le nombre d’éléments strictement plus grands que les précédents. Exercice 4. La fonction map de signature ('a -> 'b) -> 'a list -> 'b list de Caml prend en entrée une fonction f de signature 'a -> 'b et une liste ` de type 'a list et crée la liste des f (a) pour a dans `. Réécrivez-là. Que pensezvous de celle-ci ? let map_perso f l= let rec aux acc l=match l with | [] -> acc | x::q -> aux (f(x)::acc) q in rev (aux [] l) ;; Exercice 5. Écrire une fonction combine l1 l2 combinant deux listes [a0 ; . . . ; an−1 ] et [b0 ; . . . ; bn−1 ] pour former la liste des couples (ai , bi ) (dans le même ordre) et renvoyant une erreur si les listes n’ont pas même taille. Exercice 6. Écrire une fonction prenant en entrée une liste et renvoyant la liste de ses préfixes. #prefixe [6;8;9;0;1];; - : int list list = [[6; 8; 9; 0; 1]; [6; 8; 9; 0]; [6; 8; 9]; [6; 8]; [6]; []] Svartz Page 1/2 2014/2015 MPSI {831, 832} Lycée Massena On pourra commencer par écrire une fonction prenant en entrée un élément x et une liste de listes l, et renvoyant la liste des x::l. Exercice 7. La fonction do_list en Caml prend en entrée une fonction f de signature 'a list -> unit (appelée un traitement) et une liste ` = [a0 ; . . . ; an−1 ] de type 'a list, et effectue (sans conserver les résultats) les traitments f (a0 ), . . . , f (an−1 ) (dans cet ordre). Écrire une fonction do_list_rev effectuant les traitements f (an−1 ), . . . , f (a0 ) dans cet ordre. Par exmple : #do_list_rev print_int [4;5;6] ;; 654- : unit = () Exercice 8. Tours de Hanoï. Le but de cet exercice est de résoudre le problème classique des Tours de Hanoï. On dispose de trois emplacements et sur le premier se trouve n disques de taille 1, . . . , n formant une tour (le disque le plus grand étant tout en bas). Le but du jeu est de déplacer entièrement la tour sur le troisième emplacement, en déplaçant les disques un à un. La contrainte est la suivante : n’empiler un disque que sur un emplacement vide ou un disque de taille supérieure. 1. Résoudre le problème pour n = 1, 2, 3, à la main. 2. Écrire une fonction deplacement i j affichant i -> j à l’écran. On utilisera les fonctions print_int et print_string, 3. Écrire une fonction récursive résolvant le problème. Votre fonction utilisera la fonction précédente pour les déplacements : la signification du mouvement est « déplacer le disque en haut de l’emplacement numéro i sur l’emplacement numéro j ». Indication : votre fonction hanoi pourra faire appel à une fonction auxiliaire prenant trois arguments i j et k qui sont les 3 entiers 1, 2, 3 et un entier n, et ayant pour but de déplacer n disques de l’emplacement i à l’emplacement j. 4. Combien la fonction fait-elle de déplacements ? 2 Les tris : suite On veut trier une liste (d’entiers, ou de flottants) dans l’ordre croissant. On propose deux algorithmes, qui sont rapides ! Pour les tester, on créera d’abord une fonction qui crée une liste d’entiers aléatoires : random_list n m renvoyant une liste de taille n avec des éléments générés à l’aide de random__int m. 2.1 Tri fusion Ce tri fonctionne suivant le principe « diviser pour régner » : on coupe la liste en deux, on trie récursivement les deux sous-listes, et on les fusionne pour obtenir une liste triée. 1. Écrire une fonction fission l prenant en entrée une liste et retournant deux listes de même taille (à un élément près) dont les éléments réunis sont les mêmes que ceux de `. 2. Écrire une fonction fusion l1 l2 prenant en entrée deux listes qu’on suppose triées dans l’ordre croissant, et renvoyant une liste triée dans l’ordre croissant constituée des éléments de `1 et `2 . (On pourra utiliser rev...) 3. En déduire une fonction tri_fusion. On n’oubliera pas les cas terminaux ! 4. Estimer sa complexité (on la reverra bientôt). 2.2 Tri rapide Ce tri fonctionne également suivant le principe diviser pour régner, mais de manière différente : on ne coupe pas en deux mais on choisit un élément x (le plus simple est de prendre le premier de la liste !) comme pivot. On construit alors deux listes : la première constituée des éléments (sans compter le pivot lui-même) inférieurs ou égaux à x, et la seconde des éléments strictement supérieurs. On trie récursivement ces deux listes. Pour trier complètement la liste, il suffit de réunir les deux listes en intercalant le pivot au milieu. 1. Écrire une fonction partition prenant en entrée une liste et renvoyant un triplet (pivot, première liste, deuxième liste), comme expliqué ci-dessus. 2. En déduire une fonction de tri tri_rapide. On pourra utiliser @ pour la concaténation. Svartz Page 2/2 2014/2015