Université Pierre Marie Curie
Maîtrise d'informatique --- AlgoProg
Mise à niveau Objective Caml
T.M.E 1

E. Chailloux   P. Manoury

2-3 Oct. 2002

1   Petit calcul simple

Question

  1. définir la fonction aire_couronne telle aire_couronne r1 r2 calcule l'aire d'une couronne de rayon interne r1 et de rayon externe r2. La fonction déclenche une exception lorsque les arguments sont incorrects : valeurs négative ou r2 < r1.

2   Fonctions d'ordre supérieur

Soient les définitions mathématiques suivantes :

Questions

  1. définir la fonction fun_comp telle que fun_comp f g x soit égale à (f°g) x.
  2. définir la fonction fun_pow telle fun_pow f n x soit égal à fn x.
  3. utilisez fun_pow pour définir la fonction exponentielle.
    Indication : on a que mn = fn(1) si f est la fonction qui multiplie par m sont argument : f(x) = m× x.

3   Fonctions simples sur les listes

Questions

  1. définir une fonction index telle que index x xs donne la position de la première occurence de x dans xs (i.e. la plus à gauche) ou déclenche une exception si x n'apparaît pas dans xs.
    Un élément en tête de liste est en position 0.
  2. si ce n'est déjà fait, donner une version récursive terminale de index.
  3. définir une fonction skip0 et une fonction skip1 telles que skip0 xs est la liste ne contenant que les éléments d'indice pair de xs et skip1 xs est la liste ne contenant que les éléments d'indice impair de xs.
    Remarque : il est inutile d'utiliser la fonction index, un filtrage ad hoc suffit.

4   Chiffres

Question

  1. définir la fonction rsh_char telle que rsh_char n c retourne le n-ième caractère aprés c dans l'ordre alphabétique circulaire (ie: 'A' (re)vient aprés 'Z').
    Hypothèse : pour simplifier, on suppose que c est toujours une lettre majuscule.
    Indication : utilisez les fonctions de conversion int_of_char et char_of_int.
  2. définir une fonction encode telle que encode cs n calcule la liste de caracères résultant d'un décalage de n des caractères contenus dans cs.
    Indication : s'écrit trés simplement si l'on pense à utiliser le bon itérateur sur les listes !
  3. définir la fonction lsh_char, invers de rsh_char et en déduire la fonction de décodage decode
  4. pour faire joli, définir une fonction trigramme telle que trigramme cs retourne une liste où les éléments de cs sont groupés par 3 (i.e. on obtient une liste de triplets). On complètera, si besoin, le dernier trriplet par des caractères choisis au hasard.
    La fonction Random.int permet d'obtenir un entier pseudo aléatoire.
  5. définir une fonction int_of_3chars telle que int_of_3chars (c1,c2,c3) donne l'entier obtenu en concaténant le code ASCII des trois caractères c1, c2 et c3.
  6. définir la fonction stamp telle que stamp cccs est l'entier obtenu en appliquant un ou exclusif sur tous les triplets de cccs convertis en entiers.
    Remarque : s'écrit facilement si l'on utilise le bon itérateur sur les listes !
  7. définir la fonction encode_and_stamp telle que encode_and_stamp cs n retourne le couple constituer de
  8. définir la fonction decode_and_check telle que decode_and_check (cccs, s) n retourne la liste des caractères encodés par cccs (avec un décalage de n) mais déclenche une exception si la signature s ne correspond pas à cccs.

5   Arbres

On se donne le type des arbres binaires suivant : 
type 'a ab =
  Lf of 'a 
| Nd1 of 'a * 'a ab
| Nd2 of 'a ab * 'a * 'a ab

Questions

  1. définir la fonction count telle que count x t donne le nombre d'occurence de x dans t.
  2. définir la fonction max_depth telle que max_depth x t donne la profondeur maximale de x dans t. Si x n'apparaît pas dans t, on renverra -1.
  3. définir la fonction path telle que path x t donne la liste des noeuds d'une branche menant jusqu'à x dans t ou la liste vide si x n'apparaît pas dans t.
This document was translated from LATEX by HEVEA.