Compléments de syntaxe

Comme nous l'avons vu au précédent TP, les entiers sont très différents des flottants. Il est cependant possible de convertir certains types de base en d'autres à l'aide de fonctions prédéfinies.

• float_of_int : int -> float prend un entier en paramètre et retourne le flottant correspondant. Par exemple, float_of_int 0 retourne 0. .
• int_of_float : float -> int retourne la troncature du flottant passé en paramètre. Par exemple, int_of_float 3.2 retourne 3 et int_of_float -3.2 retourne -3 .
• string_of_int : float -> string (resp. string_of_float : float -> string) prend un entier (resp. un flottant) en paramètre et retourne la chaîne correspondante. Par exemple, string_of_float 3.2 retourne la valeur "3.2" .
• int_of_string : string -> int (resp. float_of_string : string -> float) retourne l'entier (resp. le flottant) correspondant à la chaîne de caractères passée en paramètre. Une erreur survient si la chaîne ne correspond pas à un entier (resp. un flottant). Par exemple, int_of_string "3" retourne 3 mais int_of_string "toto" retourne une erreur.

Il existe d'autres fonctions de conversion. De manière générale, les spécifications détaillées de toute la bibliothèque standard Ocaml sont accessibles depuis la page http://caml.inria.fr.

Enregistrements et couples

Un rationnel p/q peut être représenté à l'aide d'un enregistrement ou d'un couple.

• Proposer un type pour les rationnels en utilisant des enregistrements.
• Écrire une fonction réalisant l'addition de deux rationnels (sans chercher à réduire la fraction obtenue).
• Proposer un type pour les rationnels en utilisant les couples.
• Écrire une fonction réalisant l'addition de deux rationnels (sans chercher à réduire la fraction obtenue).

Types sommes et types énumérés

Mixité entiers/flottants

Les entiers (au sens int) sont très différents des flottants mais les définitions de type nous permettent cependant de les manipuler en un seul type.

• Définir le type nombre (un nombre est soit un entier, soit un flottant).
• Proposer des fonctions permettant d'additionner, de soustraire, de multiplier et de diviser deux nombres.
• Proposer une fonction permettant de tester si un nombre est plus petit qu'un autre.

Money (money money...)

• Définir un type énuméré monnaie permettant de décrire pour les euros les pièces (1 centime, 2 centimes, 5 centimes, 10 centimes, 20 centimes, 50 centimes, 1 euro, 2 euros) et les billets (5 euros, 10 euros, 20 euros et 50 euros).
• Proposer une fonction qui, étant donné un élément m de type monnaie, retourne true s'il s'agit d'un billet et false sinon.
• Proposer une fonction qui, étant donnés un entier s représentant une certaine somme et un élément m de type monnaie, permet de trouver combien d'éléments m sont nécessaires pour atteindre la somme s en question. Par exemple, pour atteindre 270 euros avec des billets de 50 euros, il faut 6 billets tandis qu'avec des billets de 10 euros, il en faut 27.

Fonctions récursives

Étude du calcul d'une puissance

• Proposer une fonction, qui étant donnés deux entiers x et p (p > 0), retourne l'entier x^p en utilisant l'équation

  ∀ x,   x⁰ = 1

  ∀ x, ∀ p > 0,   x^p = x × x^(p-1)

• Tester cette fonction sur différentes valeurs de x et p, dont au moins une grande valeur pour p (p > 300000).
• Proposer une fonction, qui étant donnés deux entiers x et p, retourne l'entier x^p en utilisant l'équation

  ∀ x,   x⁰ = 1

  ∀ x, ∀ p > 0, p pair,   x^p = (x^(p/2))²

  ∀ x, ∀ p > 0, p impair,   x^p = x × (x^((p-1)/2))²

• Tester cette fonction sur les mêmes valeurs que précédemment.

Suite de Fibonacci

La suite de Fibonacci est une suite d'entiers usuellement définie comme suit:

fib(0) = 0

fib(1) = 1

∀ n,   fib(n+2)=fib(n+1)+fib(n)

• Proposer une fonction naïve fib_naive: int->int retournant pour tout entier n la valeur fib(n).
• Tester cette fonction avec les paramètres 0, 1, 10 et 40. Pour 40, un temps de calcul d'environ une minute est normal.

Le temps de calcul important pour des valeurs relativement faibles du paramètre peut s'expliquer par le très grand nombre d'appels récursifs requis pour cette méthode. En effet, pour calculer fib(n+2), il faut calculer fib(n+1) et fib(n). Mais pour calculer fib(n+1), il faut calculer fib(n) et fib(n-1). il faut donc effectuer de l'ordre de 2ⁿ opérations pour calculer fib(n). On peut cependant calculer cette suite plus efficacement (de l'ordre de n opérations), en utilisant la définition suivante et à l'aide de couples:

fib_aux(0) = (1, 0)

∀ n,   fib_aux(n+1)=(a+b, a) si fib_aux(n)=(a, b)

• Proposer une fonction utilisant cette méthode pour calculer la suite de Fibonacci et comparer les résultats et les temps d'excécution avec ceux obtenus par la première méthode.