Exercices - Séance 0

Exercice (-1) - L' échauffement

• Problème 0: Implémentez une fonction prod-list qui, étant donné une liste de nombres, calcule leur produit. Exemple de résultat attendu :

  # prod_list [1;2;3;5];;
  - : int = 30
  

• Problème 1: Implémente zune fonction succ-list qui, étant donné une liste de nombres, produit une nouvelle liste dont les éléments sont les successeurs des éléments respectifs de la liste initiale. Rappelons que le successeur d'un nombre est . Exemple de résultat attendu:

  # succ_list [1;2;3;4;5];;
  - : int list = [2; 3; 4; 5; 6]
  

Exercice 0 - Points

• Problème 0: Implémentez une fonction dot_line : int -> string telle que dot_line k renvoie une chaîne de k points. Exemple de résultat attendu :

  # dot_line 5;;
  - : string = "....."
  

• Problème 1: Implémentez une fonction dot_rect : int -> string telle que dot_rect m n renvoie une chaîne qui, lorsqu'elle est imprimée, produit m lignes de n points. Exemple de résultat attendu:

  # print_string (dot_rect 5 12);;
  ............
  ............
  ............
  ............
  ............- : unit = ()
  

Exercice 1 - Recherche des nombres premier

Un entier naturel \(n > 1\) est premier si ses seuls diviseurs sont lui-même et \(1\).

• Problème 1: Implémenter en OCaml une fonction is_prime : int -> bool telle que is_prime n, pour n > 2, donne vrai si n est premier et false sinon. Exemple de résultat attendu :

  # is_prime 51;;
  - : bool = false
  # is_prime 67;;
  - : bool = true
  

• Problème 2: En utilisant la fonction que vous avez implémentée ci-dessus, implémentez une fonction primes_leq_than : int -> string telle que primes_leq_than n :
  • pour n positif est égale à la chaîne de caractères obtenue en concaténant tous les nombres premiers inférieurs ou égaux à n,
  • pour n nul ou négatif est égale à unechaîne de caractères contenant un message d'erreur approprié de votre choix. Exemple de résultat attendu :

    # primes_leq_than 100;;
    - : string =
    " 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97"
    # primes_leq_than (-5);;
    - : string = "L'entrée doit être positive."
    

Exercice 2 - Dénombrement des arbres binaires

• Problème 0: Trouvez une définition récursive pour les arbres binaires.

Solution

• Problème 1: En utilisant cette définition récursive, dérivez une récurrence pour le nombre \(C_n\) d'arbres binaires avec \(n\) sommets internes.

Solution

En raisonnant de manière récursive, nous obtenons la récurrence suivante pour les fameux nombres Catalans:

\(C_0 = 1, C_n = \sum_{i=1}^{n}C_{i-1}C_{n-i}\) pour \(n > 0\).

• Problème 2:

La récurrence que nous avons dérivée n'est pas très efficace (et un peu délicate à mettre en oeuvre comme vous le découvrirez dans votre devoir). Une récurrence plus efficace pour \(C_n\) est la suivante :

\(C_0 = 1, C_n = \frac{2(2n-1)}{n+1} C_{n-1}\) pour \(n > 0\).

En utilisant cette récurrence, implémentez en OCaml une fonction catalan : int -> int telle que catalan n donne \(C_n\). Exemple de résultat attendu:

# catalan 5;;
- : int = 42

Hint

Le facteur \(\frac{2(2n-1)}{n+1}\) est un nombre rationnel. Pourtant, nous sommes sûrs que le résultat final est un entier puisqu'il s'agit du nombre de quelque chose - à savoir des arbres avec \(n\) sommets internes. Par conséquent, vous devrez peut-être utiliser les opérations arithmétiques +., -., *., /. décrites dans la documentation du module Float, mais à la fin, vous devrez arrondir et reconvertir le résultat final en int - vous pouvez trouverez des fonctions pour faire ça en utilisant la fonction de recherche de la documentation d'API, comme indiqué dans la classe !

• Problème 3: Réécrivez la fonction pour qu'elle soit récursive terminale.

Devoir à rendre avant le 06 octobre 2023, 23h59, heure de Paris:

• Problème 0 : Implémentez en OCaml une fonction catalan_2 : int -> int telle que catalan_2 n donne \(C_n\) en utilisant la récurrence obtenue comme solution du Problème 1. Exemple de résultat attendu:

  # catalan_2 5;;
  - : int = 42
  

Hint

Vous pouvez calculer la somme \(\sum\limits_{i=1}^{n} C_{i-1}C_{n-i}\) de manière récursive. Créez une fonction cauchy i n qui calcule la somme ci-dessus à partir de l'indice \(i\) = i. Attention: cette fonction est à la fois récursive en elle-même et mutuellement récursive avec catalan.

• Problème 1 : Implémentez une fonction print_catalans : (int -> int) -> int -> string dont le premier argument est une fonction qui calcule le \(n\)-ième nombre catalan et dont le second argument est un nombre entier positif ou nul. La fonction doit être telle que print_catalans f n renvoie une chaîne de caractères obtenue en concaténant les résultats de f appliqués à chacun des entiers compris entre 0 et n (y compris 0 et n).

Exemple de résultat attendu :

# print_catalaéns catalan 10;;
- : string = " 1 2 5 14 42 132 429 1430 4862 16796"
# print_catalans catalan_2 10;;
- : string = " 1 2 5 14 42 132 429 1430 4862 16796"