1.Fonctions retournant un doublet.

On veut implanter une fonction calculant le quotient et le reste de la division euclidienne de deux entiers naturels.

Plus précisément, on veut écrire diverses définitions d'une fonction admettant comme paramètres un entier naturel a et et un entier naturel non nul b et retournant le doublet (q, r) tel que

a = bq + r avec 0 <= r < b

1.1Version directe utilisant les opérateurs Ocaml sur les entiers

Écrivez une définition de la fonction euclide : int -> int -> int * int telle que (euclide a b) retourne, lorsque a est un entier naturel et b un entier naturel non nul, le doublet (q, r) où q est le quotient et r la reste de la division entière de a par b.

Testez cette définition.

Quel résultat obtenez-vous si le paramètre b est nul ?

Essayer et analyser les résultats obtenus lorsque a et b sont des entiers relatifs.

Quelle spécification donneriez-vous à cette définition de la fonction ?

1.2Versions récursives

Dans la suite, on ne veut plus utiliser la division entière par b (opérateurs (/) et (mod) avec b comme opérande droit).

On supposera, sans vérification, que le paramètre a est un entier naturel et que le paramètre b est un entier naturel non nul.

1.2.1.Calcul récursif par soustraction du diviseur au dividande

Écrire une définition récursive euclide1 basée sur la propriété suivante :

SI (a-b) = bq + r avec 0 <= r < b ALORS a = b(q + 1) + r avec toujours 0 <= r < b

Dans quel cas doit-on arrêter la récursivité ?

Tester cette définition.

1.2.2.Calcul récursif par division par deux du dividende

Écrire une défintion récusive euclide2 basée sur la propriété suivante :

SI (a/2) = bq + r avec 0 <= r < b ALORS

en posant r1 = 2r si a est pair ou r1 = 2r + 1 si a est impair,

on obtient a = b(2q) + r1 avec 0 <= r1 < 2b

et donc

si r1 < b : a = b(2q) + r1 avec 0 <= r1 < b ou
si r1 >= b : a = b(2q + 1) + (r1 - b) avec 0 <= (r1 - b) < b

Dans quel cas peut-on arrêter la récursivité ?

Dans quel cas doit-on arrêter la récursivité ?

Tester cette définition.