3 Les booléens
3.1 Le type des booléens
Ensemble des booléens : {vrai, faux} (deux valeurs).
Opérations sur les booléens non, et, ou (il y en a d’autres) :
– non : booléen −→ booléen définie par non(vrai) = faux et non(faux) = vrai
– et : booléen × booléen −→ booléen / ou : booléen × booléen −→ booléen
notations infixées : x et y et x ou y (plutôt que et(x, y) et que ou(x, y)).
Définies par
x y x et y x ou y
faux faux faux faux
faux vrai faux vrai
vrai faux faux vrai
vrai vrai vrai vrai
Type des booléens : booléen = ({vrai, faux}, non, et, ou).
Opération si alors sinon fin-si : trois paramètres (c, a, s) où c est un booléen et a et s sont tous deux
de type T (p. ex.,
deux entiers, deux booléens, deux réels, etc.). si alors sinon fin-si(c, a, s) se note si c alors a sinon s
fin-si. Défini par :
si vrai alors a sinon s fin-si = a si faux alors a sinon s fin-si = s
Le résultat est donc aussi de type T.
Égalités importantes (notamment pour simplifier), pour x, y, z ∈ {vrai, faux} :
[1] non(vrai) = faux [2] non(faux) = vrai
[3] x et vrai = x [4] x et faux = faux [5] x ou vrai = vrai [6] x ou faux = x
[7] non(non(x)) = x [8] non(x et y) = non(x) ou non(y) [9] non(x ou y) = non(x) et non(y)
[10] x et y = y et x [11] x ou y = y ou x
[12] si x alors y sinon z fin-si = (x et y) ou(non(x) et z) [13] si x alors vrai sinon faux fin-si = x
[14] x et(y ou z) = (x et y) ou(x et z) [15] x ou(y et z) = (x ou y) et(x ou z)
[7] : involutivité de non. [8] et [9] : lois de de Morgan. [10] et [11] : commutativité de et et de ou. [13]
et [14] : distributivité
de et sur ou et de ou sur et.
[1] à [11] : à connaître absolument. [12] : à retrouver (ne s’applique que si T = booléen). [13] :
exemple d’application
de [6].
si c alors i1 sinon i2 fin-si où i1 et i2 sont des instructions, plutôt que des valeurs. Cas particulier où i2
est l’instruction
vide, s’écrit : si c alors i1 fin-si.
Exercice 1 Étant donné deux entiers naturels a et b, avec b 6= 0, « a est divisible par b » peut s’écrire
mod(a, b) = 0 (i.e.,
le reste de la division euclidienne de a par b est nul).
Le numéro d’une année bissextile est un nombre a qui est divisible par 4, à l’exception des multiples
de 100, sauf les
multiples de 400. Ainsi 2008 et 2000 sont des (numéros d’)années bissextiles, mais pas 2010 ni 1900.
Écrire l’algorithme de la fonction testant si un entier naturel donné est le numéro d’une année
bissextile, en utilisant
mod(·, ·) et si · alors · sinon · fin-si.
Écrire un autre algorithme de cette fonction, en utilisant mod(·, ·) et les opérations non, et et ou,
mais passi · alors ·sinon · fin-si.
3.2 Implantation des booléens en C
Le type booléen est défini dans la bibliothèque standard stdbool.h. Autrement dit, si on veut
manipuler des booléens,
on écrira :
#include <stdbool.h>
Cela permet de définir le nom du type (bool) et les constantes true et false (traduisant,
respectivement, vrai et faux).
Remarque 1 En fait, en C, le type booléen n’est pas implanté en tant que tel : un booléen est
représenté par un entier : si
b est une variable de type entier, b correspondra à la valeur faux si b vaut l’entier 0 et à vrai sinon.
Traditionnellement,
on prend 1 comme valeur pour vrai. Cela dit, il vaut mieux utiliser le type bool et les constantes true
et false pour
des raisons de lisibilité.
Le ou s’écrit ||. Il ne coïncide pas exactement avec le ou logique parce que calculé de façon «
progressive ». Cela signifie
que si on effectue l’instruction exp = exp1 || exp2 ;, alors, l’expression exp1 est calculée en premier
et, si elle vaut
vrai, l’expression exp2 n’est pas évaluée. En effet, on a toujours vrai ou x = vrai, quelle que soit la
valeur du booléen
x. Ce calcul progressif permet d’une part de diminuer le temps de calcul et d’autre part d’éviter que
le programme fasse
des erreurs dans certains cas. Par exemple, l’expression (a == 0. || 1. / a < 3.) ne provoquera pas
d’erreur, même
si a représente un réel nul.
Le et s’écrit && et est évalué de façon progressive. Si on a l’instruction exp = exp1 && exp2 ;, alors
exp1 sera évalué
en premier et si le résultat est faux, l’évaluation de exp2 n’est pas effectuée : faux et x = faux, quelle
que soit la valeur
de x.
Le non s’écrit par le symbole !.
si c alors a sinon s fin-si s’écrit avec la syntaxe suivante : c ? a : s. Il existe aussi un si · alors · sinon ·
fin-si dont
les parties conclusions (a ou s) sont des instructions et qui est très utilisé. Sa syntaxe est la suivante :
if (c) /* Noter que la condition est entre parenthèses */
instructions1 ; /* Noter que le `` alors '' est sous-entendu */
else
instructions2 ;
} /* Noter que le `` finsi '' est sous-entendu */
où instructions1 et instructions2 sont chacune une suite d’instructions en C. Si s est la suite
d’instructions vide,
alors, on peut se passer du else et faire :
if (c)
instructions1 ;
Exercice 2 Écrire la procédure afficheBooleen qui affiche la valeur d’un booléen (affichage de vrai ou
de faux).
Exercice 3 Écrire une fonction max qui calcule le maximum de deux entiers (int).
Comment modifier cette fonction en une fonction min qui calcule le minimum de deux entiers ?
Écrire une fonction max4 qui calcule le maximum de quatre entiers.
Écrire une fonction mediane qui prend trois entiers en paramètres et, s’ils sont différents deux à
deux retourne la valeur
qui n’est ni le minimum, ni le maximum 1
. Par exemple mediane(2, -4, 8) retourne 2. On veut deux versions de cette
fonction, l’une utilisant une conditionnelle et l’autre utilisant d’autres fonctions déjà définies
auparavant.
Exercice 4 Écrire une procédure qui résout sur IR les équations du second degré (affichage des
solutions).
Exercice 5 Écrire une fonction qui teste si une année est bissextile ou non. Les années sont
généralement non bissextiles,
à l’exception des années divisibles par 4 (dont le numéro est divisible par 4). Les années divisibles par
100 sont une
exception à cette exception, sauf celles qui sont divisibles par 400. Ainsi 2003, 1900 et 2100 sont non
bissextiles, alors
que 2004 et 2000 sont bissextiles.
Remarque : a % b est le reste de la division entière (euclidienne) de a par b.
4 Les entiers
4.1 Les entiers naturels
4.1.1 Type abstrait entier_nat
Intuition des « entiers bâtons ».
Nom du type : entier_nat.
Type abstrait importé : booléen.
Opérations primitives :
– Noms et profils :
– Constructeurs :
zéro : −→ entier_nat
succ : entier_nat −→ entier_nat
( Erreur_entier_nat :−→ entier_nat )
– Accès :
est_nul : entier_nat −→ booléen
préc : entier_nat −→ entier_nat
– Axiomes
[Ax-1] est_nul(zéro) = vrai
[Ax-2] est_nul(succ(x)) = faux
[Ax-3] préc(zéro) = Erreur_entier_nat()
[Ax-4] préc(succ(x)) = x
Opérations non primitives : il y en a une infinité.
Pour spécifier (profil et axiomes) et implanter (algorithes et programmes) une opération non
primitive, on peut s’appuyer
sur les opérations primitives ou sur les opérations non primitives déjà définies (ou introduites pour
les besoins de la cause).
Exemples d’opérations non primitives : égaux (x = y ?) plus_petit_que (x < y ?), plus (x + y), moins (x −
y),
mult (x×y), div et mod (quotion et reste de la division euclidienne), puissance (x
), fact (x!), est_premier (x est-il
premier ?), pgcd (plus grand commun diviseur de x et y), somme_diviseurs_premiers (somme des
diviseurs premiers
de x et y, comptés avec leur ordre de multiplicité ou – version 2 – sans), somme_diviseurs (somme
des diviseurs de x
et y), carré (carré de x), est_carré (x est-il un carré parfait ?), racine_carrée (partie entière de √
x), n
ème_premier
(le 0
ème étant 2, le 1
er étant 3, etc.).
4.1.2 Démarche algorithmique et exemple
Pour une opération non primitive donnée, l’exercice consiste à (1) définir le profil, (2) traiter un ou
plusieurs exemples,
(3) définir des axiomes, (4) traduire ces axiomes en un algorithme récursif, (5) donner un algorithme
itératif, (6) traduire
l’algorithme récursif en C, (7) traduire l’algorithme itératif en C, (8) tester les fonctions C.
Exemple du déroulement de la démarche sur un exemple : égaux.
(1) Profil. égaux : entier_nat × entier_nat −→ booléen .
(2) Exemples. Notation : SSS0 pour succ(succ(succ(zéro))).
égaux(SSS0, SSS0) = égaux(SS0, SS0) = égaux(S0, S0) = égaux(0, 0) = vrai
égaux(SSS0, SS0) = égaux(SS0, S0) = égaux(S0, 0) = faux
égaux(SSS0, SSSS0) = égaux(SS0, SSS0) = égaux(S0, SS0) = égaux(0, S0) = faux
(3) Axiomes (généralisés à partir des exemples).
[Ax-5] égaux(zéro, zéro) = vrai
[Ax-6] égaux(zéro, succ(x)) = faux
[Ax-7] égaux(succ(x), zéro) = faux
[Ax-8] égaux(succ(x), succ(y)) = égaux(x, y)
(4) Algorithme récursif (i.e., la fonction égaux fait appel à elle-même).
fonction égaux (x : entier_naturel, y : entier_naturel) : entier_naturel
Début
si est_nul(x) et est_nul(y)
alors retourner vrai
fin-si
si est_nul(x) /* forcément, y sera non nul */
alors retourner faux
fin-si
si est_nul(y) /* forcément, x sera non nul */
alors retourner faux
fin-si
retourner égaux (préc(x), préc(y))
Fin
On peut le simplifier (en passant éventuellement par plusieurs étapes).
fonction égaux (x : entier_naturel, y : entier_naturel) : entier_naturel
Début
si est_nul(x) ou est_nul(y)
alors retourner est_nul(x) et est_nul(y)
fin-si
retourner égaux (préc(x), préc(y))
Fin
(5) Algorithme itératif (i.e., sans appel récursif). Utilisation de variables et de structures de boucle.
Considérer à nouveau
l’exemple, en introduisant des variables. Par exemple, pour le calcul de égaux(SSS0, SSSS0) :
t0123
at SSS0 SS0 S0 0 ← stop !
bt SSSS0 SSS0 SS0 S0
On peut utiliser la boucle de structure
tant que <booléen>
<instructions>
fin-tant que
qui exécute les instructions tant que le booléen est égal à vrai.
fonction égaux (x : entier_naturel, y : entier_naturel) : entier_naturel
Début
a := x
b := y
tant que non(est_nul(a)) et non(est_nul(b))
a := prec(a) /* opération licite car a est non nul */
b := prec(b) /* idem pour b */
fin-tant que
/* à cet endroit : a est nul ou b est nul (cf. lois de de Morgan)
si ce sont les deux qui sont nuls, alors x est égal à y : */
retourner est_nul(a) et est_nul(b)
Fin
Les commentaires peuvent être utiles pour rendre le programme plus lisible. On peut aussi utiliser x
et y directement à la
place de a et b, pour gagner deux lignes.
Pour bien comprendre ce que fait l’algorithme, il faut le tester avec des exemples.
(6), (7) et (8). Le code C suivant répond aux questions (6), (7) et (8), respectivement par les fonctions
egaux_R, egaux_I et
la procedure test_egaux. Il suppose qu’existe une implantation des entiers naturels dans un fichier
entier_naturel_batons.h
(voir section 4.1.3).
/* Test d'égalité de deux entiers naturels */
#include <stdbool.h>
#include "entier_naturel_batons.h"
/* Implantation récursive de l'opération égaux */
bool egaux_R (ENTIER_NAT x, ENTIER_NAT y)
if (est_nul (x) || est_nul (y))
return est_nul (x) && est_nul (y) ;
return egaux_R (prec (x), prec (y)) ;
/* Implantation itérative de l'opération égaux */
bool egaux_I (ENTIER_NAT x, ENTIER_NAT y)
ENTIER_NAT a, b ;
a=x;
b=y;
while (!est_nul (a) && !est_nul (b)) {
a = prec (a) ;
b = prec (b) ;
return est_nul (a) && est_nul (b) ;
void affiche_egalite (ENTIER_NAT x, ENTIER_NAT y) {
printf ("égaux (%d, %d) ? Par egaux_R : %d, par egaux_I : %d\n",
x, y, egaux_R (x, y), egaux_I (x, y)) ;
void test_egaux ()
affiche_egalite (3, 4) ;
affiche_egalite (4, 2) ;
affiche_egalite (6, 6) ;
affiche_egalite (0, 0) ;
int main ()
{
test_egaux () ;
L’exécution de ce code donne :
% gcc -o egaux egaux.c
% egaux
égaux (3, 4) ? Par egaux_R : 0, par egaux_I : 0
égaux (4, 2) ? Par egaux_R : 0, par egaux_I : 0
égaux (6, 6) ? Par egaux_R : 1, par egaux_I : 1
égaux (0, 0) ? Par egaux_R : 1, par egaux_I : 1
sachant que 0 signifie faux et 1 signifie vrai, le résultat correspond aux attentes.
Remarque 2 On pourrait réécrire la fonction egaux_I sans introduire de variables, en utilisant les
paramètres comme
variables :
bool egaux_I (ENTIER_NAT x, ENTIER_NAT y)
while (!est_nul (x) && !est_nul (y)) {
x = prec (x) ;
y = prec (y) ;
return est_nul (x) && est_nul (y) ;
Cela est possible parce qu’on fait un passage de paramètre par valeurs : l’appel egaux_I (u, v) pour u
et v deux
variables de type ENTIER_NAT valant respectivement 4 et 8 revient à l’appel egaux_I (4, 8) et donc ne
modifie pas la
valeur des variables u et v.
4.1.3 Implantation en C des entiers naturels
Les entiers naturels sont représentés par plusieurs types en C dont le plus classique est le type
unsigned int (il y a aussi
unsigned short int et unsigned long int). On peut proposer l’implantation suivante du type
entier_nat :
/*******************************************/
/* entier_naturel_batons.h */
/* auteur : Jens Gustedt et Jean Lieber */
/* date : 22/09/09 */
/* version : 2 */
/*******************************************/
#include <stdio.h> /* Pour le printf */
#include <stdlib.h> /* Pour le exit */
typedef unsigned int ENTIER_NAT ;
/* Constructeurs */
#define ZERO 0
ENTIER_NAT succ (ENTIER_NAT x)
return 1 + x ;
ENTIER_NAT Erreur_entier_nat () {
printf ("Erreur de manipulation d'entier naturel.") ;
exit (EXIT_FAILURE) ;
return 0 ;
/* Accès */
ENTIER_NAT est_nul (ENTIER_NAT x)
return x == 0 ;
ENTIER_NAT prec (ENTIER_NAT x)
if (x == 0)
return Erreur_entier_nat () ;
return x - 1 ;
}
À terme, on n’utilisera directement les notations de C pour programmer les opérations sur les entiers
naturels (mais pas
avant de maîtriser l’autre façon de faire). Par exemple, la fonction egaux_R sera réécrite
/* Implantation récursive de l'opération égaux, version 2 */
bool egaux_R (unsigned int x, unsigned int y)
if (x == 0 || y == 0)
return x == 0 && y == 0 ;
return egaux_R (x - 1, y - 1) ;
Et, en fait, on utilisera directement == pour tester l’égalité de deux entiers naturels.
4.2 Les entiers relatifs
Les entiers relatifs (ou entiers signés) sont les éléments de ZZ : 0, 1, −1, 2, −2, 3, −3, etc.
4.2.1 Type abstrait
On peut définir un entier relatif par la donnée de son signe (sachant qu’il existe deux signes : + et −)
et de sa valeur
absolue. Deux entiers relatifs seront égaux soient si leurs valeurs absolues sont toutes deux nulles
(quels que soient leurs
signes : −0 = +0) soit s’ils ont même signe et même valeur absolue.
Avant d’introduire le type abstrait entier, nous allons introduire le type abstrait signe. Les
constructeurs de signe sont :
+ : −→ signe
- : −→ signe
l’accès est :
est_plus : signe −→ booléen
et les axiomes sont :
[Ax-9] est_plus(+) = vrai
[Ax-10] est_plus(-) = faux
(au passage, on voit une façon de décrire l’axiomatique d’un ensemble à deux éléments).
Le type abstrait entier correspond à l’anneau (ZZ, +, ·) : les entiers de ce type sont des entiers « signés
». Ses types
importés sont booléen, entier_nat et signe. L’idée est qu’un entier est donné par un signe et un
entier_nat : 2
est donné par + et succ(succ(zéro)), −1 est donné par - et succ(zéro) et 0 est donné par + et zéro ou -
et zéro. On
propose le constructeur :
cons : signe × entier_nat −→ entier
les accès :
valeur_absolue : entier −→ entier_nat signe_de : entier −→ signe
et les axiomes
[Ax-11] valeur_absolue(cons(x, y)) = y
[Ax-12] signe_de(cons(x, y)) = x
Afin de gérer les erreurs, on peut également proposer le constructeur
Erreur_entier : −→ entier
Exercice 7 On peut définir sur entier les opérations correspondant aux opérations zéro, succ, est_nul,
préc, égaux,
plus_petit_que, plus, moins, mult, div et mod de entier_nat. On utilisera les mêmes noms
d’opérations.
Pour chacune de ces opérations sur les entiers relatifs, donner le profil et un jeu d’axiomes.
Exercice 8 Donner un jeu d’axiomes pour l’opération testant l’égalité de deux entiers relatifs.
4.2.2 Implantation en C des entiers relatifs
Le type C le plus classique pour représenter les entiers relatifs est int. Il y a aussi short et long. Les
opérations classiques
sur les entiers non signés s’appliquent ici (==, !=, +, -, *, /, %, <, <=, >=, >).
Exercice 9 Écrire un algorithme et un programme C de la fonction abs qui à un entier associe sa
valeur absolue. Par
exemple, abs(4) et abs(-4) retournent tous deux la valeur 4.
Exercice 10 Écrire un algorithme et un programme C de la fonction signe qui à un entier n associe un
entier s tel que
n = s × abs(n).
Exercice 11 Soit la suite (un) telle que u0 = 0, u1 = 1, u2 = −1, u3 = 2, u4 = −2, u5 = 3, u6 = −3, etc.
Écrire un
algorithme et un programme C de cette suite.
