| Exercice 1. Les nombres de Catalan satisfont à : {c_0=1} et à la relation {c_n=\dfrac{2(2n-1)}{n+1}c_{n-1}} pour tout {n\ge 1}. Écrire une fonction récursive « catalan : int -> int » renvoyant {c_n}. |
| Exercice 2. Devinez ce que font les fonctions suivantes, dont l’argument {n} est supposé positif ou nul.
|
| Exercice 3. Deviner le type de la fonction « what », et ce qu’elle fait :
|
| Exercice 4. Deviner ce que fait la fonction « hop » :
|
| Exercice 5. Écrire une fonction « add : int -> int -> int », récursive terminale, et effectuant la somme de ses deux arguments (supposés {\ge0}). Les seules opérations autorisées sont l’addition ou la soustraction de {1}. |
| Exercice 6. Écrire une fonction « mul : int -> int -> int », utilisant une fonction auxiliaire récursive terminale, et effectuant le produit de ses deux arguments (supposés {\ge0}). Les seules opérations autorisées sont l’addition, et la multiplication par 2 (ou la division par 2 d’un nombre pair). |
| Exercice 7. Écrire une fonction « itere : int -> (‘a -> ‘a) -> ‘a -> ‘a » calculant la valeur en un point {x} de la {n}-ième itérée {f\circ f\ldots\circ f} d’une fonction {f} définie sur (et à valeurs dans) le type de {x}. |
| Exercice 8. Écrire une fonction « hanoi : int -> unit » résolvant le problème des tours de Hanoï. |
| Exercice 9. On définit la suite de Syracuse par {u_{0}=a} et {\forall\, n\in\mathbb{N}} : {u_{n+1}=u_{n}/2} si {n} est pair et {u_{n+1}=3n+1} si {n} est impair. Écrire une fonction #{syracuse : int -> int list} renvoyant la liste formée de l’orbite (jusqu’à ce qu’on obtienne {u_{n}=1}) d’un entier {a} donné dans la suite de Syracuse. |
| Exercice 10. Que font les fonctions {f} et {g}?
|
| Exercice 11. Que font les fonctions {f} et {g}?
|
| Exercice 12. Écrire une fonction « somme : (int -> int) * int * int * int -> int » prenant en argument un quadruplet {(f,a,b,h)} et calculant la somme des {f(n)} pour {n} allant de {a} à {b} avec un pas de {h}. |