Le jeu de tests d'une division euclidienne

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 4 — Discipline de programmation, validation et test

Énoncé

Écrire un jeu de tests pour division(a, b, &q, &r) de l'exercice 1.8, qui range le quotient et le reste de $a$ par $b$ . Partitionner le domaine, éprouver les limites. Que se passe-t-il si l'on retire la précondition $a \geq 0$ et $b > 0$ ?

Corrigé

Le partitionnement. La postcondition est $a = b q + r$ . Les classes qui comptent :

Classe	Représentant	Ce qu'elle éprouve
division exacte	$(6, 3)$	$r = 0$
division inexacte	$(7, 2)$	le cas nominal
dividende nul	$(0, 5)$	$q = r = 0$
$a < b$	$(2, 7)$	$q = 0$ , $r = a$
$a = b$	$(5, 5)$	$q = 1$ , $r = 0$
diviseur $1$	$(7, 1)$	limite basse du diviseur
grandes valeurs	$(INT_MAX, 2)$	pas de débordement


void tester_division(void) {
    int q, r;
    division(6, 3, &q, &r);   assert(q == 2 && r == 0);
    division(7, 2, &q, &r);   assert(q == 3 && r == 1);
    division(0, 5, &q, &r);   assert(q == 0 && r == 0);
    division(2, 7, &q, &r);   assert(q == 0 && r == 2);
    division(5, 5, &q, &r);   assert(q == 1 && r == 0);
    division(7, 1, &q, &r);   assert(q == 7 && r == 0);
    division(INT_MAX, 2, &q, &r);
    assert(2 * (long) q + r == (long) INT_MAX);   /* la POSTCONDITION elle-meme */
    printf("division : tous les tests passent\n");
}

Le dernier test ne compare pas à une constante écrite à la main : il vérifie la postcondition. C'est la bonne forme dès que la valeur attendue est pénible à calculer, et elle attrape les fautes qu'un jeu de constantes recopiées laisserait passer.

Sans la précondition. Les signes changent tout, et les langages ne s'accordent pas. Mesuré :

$a$	$b$	C	OCaml	Python
		`a/b`	`a%b`	`a/b`	`a mod b`	`a//b`	`a%b`
$7$	$2$	$3$	$1$	$3$	$1$	$3$	$1$
$- 7$	$2$	$- 3$	$- 1$	$- 3$	$- 1$	$- 4$	$1$
$7$	$- 2$	$- 3$	$1$	$- 3$	$1$	$- 4$	$- 1$
$- 7$	$- 2$	$3$	$- 1$	$3$	$- 1$	$3$	$- 1$

C et OCaml tronquent vers zéro : le reste porte le signe du dividende. Python arrondit vers le bas : le reste porte le signe du diviseur. L'identité $a = b q + r$ est vérifiée dans les trois — c'est la seule chose qu'ils garantissent tous.

ImportantCe que la précondition achète

Écrire « précondition : $a \geq 0$ et $b > 0$ » n'est pas une paresse : c'est un refus explicite de trancher une question dont la réponse n'est pas universelle. Si l'on veut un reste toujours positif — la convention mathématique du reste euclidien —, il faut l'écrire, et le tester :


/* Range dans *q, *r le quotient et le reste EUCLIDIENS : 0 <= *r < |b|.
   Precondition : b != 0. */
void division_euclidienne(int a, int b, int* q, int* r) {
    assert(b != 0 && q != NULL && r != NULL);
    *q = a / b; *r = a % b;
    if (*r < 0) { if (b > 0) { *q = *q - 1; *r = *r + b; }
                  else       { *q = *q + 1; *r = *r - b; } }
}

Et le jeu de tests doit alors couvrir les quatre combinaisons de signes, plus les cas $r = 0$ pour chacune : c'est le partitionnement qui l'impose, pas l'intuition. L'annexe OCaml prend la même précaution en n'exigeant mod sans rappel que « quand toutes les grandeurs sont positives » (chapitre chap:langage-ocaml).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.