On définit la fonction factorielle par récurrence de la façon suivante :
|
Écrire la fonction factorielle : int -> int qui à n associe n!.
Écrire la fonction factorielle_acc : int -> int -> int telle que factorielle_acc n k calcule k(n!)
Écrire une fonction factorielle_bis : int -> int qui invoque factorielle_acc de sorte que factorielle_bis n calcule n!.
L’élévation de b à la puissance n se définit récursivement par itération du produit
|
Écrire une fonction slow_exp : int -> int -> int prenant b et n en paramètres en calculant bn à l’aide de la relation de récurrence mentionnée ci-dessus.
Écrire une fonction recursive terminale slow_exp_acc : int -> int -> int -> int prenant a, b et n en paramètres en calculant a.bn.
Écrire une fonction slow_exp_bis : int -> int -> int qui invoque slow_exp_acc de sorte que slow_exp_bis b n calcule bn.
Nous allons calculer bn à l’aide des relations de récurrence suivantes
|
Ecrire une fonction even : int -> bool telle que even n retourne true si et seulement si n est pair.
Définir la fonction fast_exp : int -> int -> int telle que fast_exp b n calcule bn avec les égalités ci-dessus.
Prouvez que la fonction fast_exp se termine toujours.
Donnez une version récursive terminale de fast_exp.
On définit le plus grand commun diviseur (greatest common divider) de deux entiers récursivement de la façon suivante :
|
Prouvez que cette relation de récurrence permet d’écrire une fonction qui se termine toujours.
Définir la fonction gcd : int -> int -> int telle que gcd n m calcule le PGCD de n et de m à l’aide des relations ci-dessus.
Écrire la fonction lettre_suivante : char -> char telle que lettre_suivante a retourne la lettre située après a dans l’alphabet. Nous ne gérerons pas le cas particulier où a = ’z’.
Écrire la fonction figure_of_int : int -> char telle que figure_of_int n retourne le caractère représentant le chiffre n. Par exemple, figure_of_int 4 retourne ’4’. Nous ne gérerons pas les cas particuliers où n est un nombre de plusieurs chiffres.
Écrire la fonction compare_lettres : char -> char -> bool telle que compare_lettres a b retourne vrai ssi la lettre a et située avant la lettre b dans l’alphabet ou si les deux lettres sont les mêmes.
Écrire la fonction alphabet : char -> char -> unit telle que alphabet lettre_depart lettre_arrivee affiche l’alphabet entre les lettres lettre_depart et lettre_arrivee.
Écrire la fonction mult : int -> int -> int telle que mult x y retourne le produit de x par y sans effectuer de multiplication.
Mettez la fonction précédente sous forme récursive terminale. Encapsulez-là dans une fonction mult_bis : int -> int -> int.
Écrire une fonction ind_euler : int -> int retournant l’indicatrice d’Euler de l’entier passé en paramètre.