DEUG MIAS 24

Types et Structures de données

TD 5

1.Enregistrements

1.1.Dossier médical

Soit le type patient de déclaration :

type patient = {nom : string ; taille : float ; poids : float} ;;

dont les éléments représentent un embryon de dossier médical pour une personne.

Écrire une implantation de la fonction anonyme telle que, lorsque p est un enregistrement de type patient, (anonyme p) retourne un nouvel enregistrement dont le champ nom ne contient plus que l'initiale, en lettre majuscule, du nom de l'enregistrement p et dont les champs taille et poids contiennent les mêmes valeurs que les champs correspondants de p.

1.2.Représentation d'un point du plan dans un repère cartésien

1.2.1.Déclaration d'un type

Définir un type point, enregistrement de champs x et y représentant respectivement l'abscisse et l'ordonnée d'un point du plan.

1.2.2.Symétrie par rapport à l'origine

Donnez la spécification et une définition de la fonction sym_O telle que (sym_O p) retourne la représentation du point image du point de représentation p dans la symétrie de centre O origine du repère cartésien.

1.2.3.Symétrie par rapport à l'axe des ordonnées

Donnez la spécification et une définition de la fonction sym_Oy telle que (sym_Oy p) retourne la représentation du point image du point de représentation p dans la symétrie par rapport à l'axe Oy

du repère cartésien.

1.2.4.Rotation de centre O et de 90 degrés dans le sens trigonométrique

Donnez la spécification et une définition de la fonction rot_O_90 telle que (rot_O_90 p) retourne la représentation du point image du point de représentation p dans la rotation de centre O, origine du repère cartésien et d'angle 90 degrés dans le sens trigonométrique..

2.Fonctions récursives sur les listes

2.1.Somme des éléments d'une liste de réels

Ecrire une implantation de la fonction somme telle que (somme l) retourne la somme des réels de la liste l.

2.2.Moyenne des éléments d'une liste de réels

Écrire une implantation de la fonction moyenne telle que (moyenne l) retourne la moyenne des réels de la liste l.

On évitera de parcourir deux fois la liste.

2.3.Élément d'une liste

Écrire une définition du prédicat element tel que (element x l) retourne true si et seulement si x est un élément de la liste l.

2.4.Indice de première occurrence d'un élément dans une liste

Écrire une implantation de la fonction indice telle que (indice x l) retourne l'indice de la première occurrence de l'élément x dans la liste l ou lève l'exception prédéfinie Not_found si l'élément x n'a pas d'occurrences dans l.

2.5.Premier indice, dans une liste, d'un élément vérifiant une propriété

Plus généralement, écrire une implantation de la fonction pos telle que (pos p l) retourne l'indice, dans la liste l, du premier élément x de l tel que l'application (p x) retourne true ou lève l'exception prédéfinie Not_found lorsqu'aucun élément de l ne vérifie le prédicat p.

2.6.Valeur d'un polynôme

On représente le polynome a₀ + a₁x + a₂x² + ... + a_nxⁿ par la liste de ses coefficients [a₀ ; a₁ ; a₂ ; ... ; a_n].

Écrire une implantation de la fonction eval telle que (eval x l) retourne la valeur du polynome associé à la liste l en x.

3.Fonctions retournant une liste

3.1.Liste croissante des entiers d'un intervalle

Écrire une implantation de la fonction sequence telle que (sequence n m) retourne la liste croissante des entiers consécutifs compris entre les entiers n et m inclus ou la liste vide si l'entier n est strictement supérieur à l'entier m.

3.2.Liste amputée de ses cinq premiers éléments

Écrire une implantation de la fonction sauf_5 telle que (sauf_5 l) retourne la liste l amputée de ses 5 premiers éléments ou la liste vide lorsque la liste l a 5 éléments ou moins.

3.3.Sous-listes

3.3.1.

Écrire une définition de la fonction pairs telle que, lorsque l est une liste d'entiers, (pairs l) retourne la liste, dans le même ordre, des seuls entiers pairs de la liste l.

3.3.2.

Pus généralement, écrire une définition de la fonction sous_liste telle que (sous_liste p l) retourne la liste, dans le même ordre, des seuls éléments x de la liste l tels que l'application (p x) retourne true.

3.4.Suffixe d'une liste

Écrire l'implantation d'une fonction suffixe telle que (suffixe p l) retourne la queue de la liste l commençant au premier élément x de l tel que l'application (p x) retourne true ou la liste vide lorsqu'aucun des éléments de l ne vérifie le prédicat p.

4.Suite de listes

On veut écrire une fonction retournant, pour un entier k > 0 la liste L_k de la suite de listes définie comme suit :

L₁ = [1]

L₂ = [1;1]

L₃ = [2;1]

L₄ = [1;2;1;1]

L₅ = [1;1;1;2;2;1]

L₆ = [3;1;2;2;1;1]

...

On obtient la liste L_k en "lisant" le contenu de la liste L_k-1.

Par exemple, la liste L₆ s'obtient à partir de L₅ en lisant :

3 répétitions de 1 suivies de 2 répétitions de 2 suivies d'1 répétition de 1 !

4.1.

Décrire une approche récursive du calcul de la liste L_k à partir de la liste L_k-1.

Quand arrêter la récursivité ?

4.2.

Écrire une fonction récursive suivante telle que, lorsque l est une liste d'entiers, (suivante l) retourne la liste suivant l dans la construction décrite précédemment. Par exemple (suivante L5) retourne la liste L6. On supposera, pour simplifier, que tous les entiers de la liste sont compris entre 1 et 9.

4.3.

Écrire une implantation de la fonction list telle que, lorsque k est un entier strictement positif (list k) retourne la liste L_k.