Chapitre 4 : Les entiers
I. Les entiers naturels
A. Type abstrait entier naturel
Intuition des entiers bâtons.
Nom : entier_naturel
Type abstrait importé : booléen
Opérations primitives
• constructeurs
zéro : entier muet
successeur : entier_naturel → entier_nat
• Accès
est_nul : entier_nat → booléen
préc : entier_nat → entier_nat
Axiomes
[1] est_nul (zéro) = vrai
[2]est_nul [ succ (x)]= faux
[3] préc (zéro)=erreur
[4]préc [succes(x)]=x
La règle est de définir des opérations (fonctions) sur les entiers. Pour en
construire de nouvelles, on peut utiliser celles déjà écrites.
Ex : On va pouvoir définir égaux (x,y) x=y
plus petit que (x,y) x<y
plus (x,y) x+y
moins (x,y) x-y
multiplier (x,y) x*y
diviser (x,y) x/y → quotient de la division
mod (x,y x/y → reste de la division
puissance (x,y) x^y
factorielle x !
est_premier : rai si l'entier est premier sinon faux
et beaucoup d'autres...
,B. Mode d'emploi (= démarche algorithmique)
La démarche algorithmique suit un schéma bien précis. On va prendre comme
exemple la fonction égaux. (Notation : zéro=o et succ() =S)
1. Définir le profil
entier_nat x entier_nat → booléen
2. Traiter un/pls exemples
égaux (0,0)= vrai
égaux (0,S 0)= faux
égaux (SSS0, SSS0)= égaux (SS0,SS0)= égaux(S0,S0)= égaux(0,0)=vrai
3. Écrire des axiomes
Généralisés à partir des exemples. On veut :
-qu'ils couvrent tous les cas
-qu'il y en ait le moins possible
* égaux (zéro, zéro)=vrai
*égaux (zéro, succ(x))=faux
*égaux (succ(x), zéro)= faux
* égaux (succ(x), succ(y))=égaux(x,y)
4. En déduire un algorithme récursif
(= la fonction fait appel à elle-même pour d'autre valeur des paramètres)
fonction egaux (x:entier,y:entier):booléen
|Début|
Si est_nul(x) et est_nul(y) alors
| retourner vrai
Sinon /* pas les deux nuls */
Si est_nul(x) alors
| retourner faux
Sinon
Si est_nul (y) alors
| retourner faux
Sinon
| retourner égaux (préc(x), préc(y))
Finsi
Finsi
Finsi
, |Fin|
ou
fonction egaux bis(x : entier_nat;y:entier_nat):booléen
|Début|
Si (est_nul(x) ou est_nul(y)) alors
| retourner (est_nul(x) et est_nul (y)
Finsi
retourner egaux bis(préc(x), préc(y))
|Fin|
5. Écrire un algorithme itératif (=pas récursif) pour la même fonction
On prend un exemple, en utilisant des variables
t 0 1 2 3
a SSS0 → préc SS0 → préc S0 → préc 0 STOP !
b SSSS0 → préc SSS0 → préc SS0 → préc S0
Deux variables a et b,
Au début a prend la valeur de x et b celle de y.
A chaque étape
a prend la valeur préc (a)
b prend la valeur préc (b)
On continue tant que ni a ni b n'est nul, ensuite si les deux sont nuls alors
retourner vrai sinon retourner faux.
Une nouvelle boucle :
Tant que (condition)
* actions *
Fin tant que
-teste la condition
→ si faux, va après le fin tant que
→ si vrai, fais les actions puis remonte en haut de la boucle
Fonction egaux. I(diminutif pour interatif) (x : entier_nat,y:entier_nat):booléen
var a,b : entier_nat
|Début|
a:=x
b:=y
Tant que (non( est_nul(a) ou est_nul(b)))
I. Les entiers naturels
A. Type abstrait entier naturel
Intuition des entiers bâtons.
Nom : entier_naturel
Type abstrait importé : booléen
Opérations primitives
• constructeurs
zéro : entier muet
successeur : entier_naturel → entier_nat
• Accès
est_nul : entier_nat → booléen
préc : entier_nat → entier_nat
Axiomes
[1] est_nul (zéro) = vrai
[2]est_nul [ succ (x)]= faux
[3] préc (zéro)=erreur
[4]préc [succes(x)]=x
La règle est de définir des opérations (fonctions) sur les entiers. Pour en
construire de nouvelles, on peut utiliser celles déjà écrites.
Ex : On va pouvoir définir égaux (x,y) x=y
plus petit que (x,y) x<y
plus (x,y) x+y
moins (x,y) x-y
multiplier (x,y) x*y
diviser (x,y) x/y → quotient de la division
mod (x,y x/y → reste de la division
puissance (x,y) x^y
factorielle x !
est_premier : rai si l'entier est premier sinon faux
et beaucoup d'autres...
,B. Mode d'emploi (= démarche algorithmique)
La démarche algorithmique suit un schéma bien précis. On va prendre comme
exemple la fonction égaux. (Notation : zéro=o et succ() =S)
1. Définir le profil
entier_nat x entier_nat → booléen
2. Traiter un/pls exemples
égaux (0,0)= vrai
égaux (0,S 0)= faux
égaux (SSS0, SSS0)= égaux (SS0,SS0)= égaux(S0,S0)= égaux(0,0)=vrai
3. Écrire des axiomes
Généralisés à partir des exemples. On veut :
-qu'ils couvrent tous les cas
-qu'il y en ait le moins possible
* égaux (zéro, zéro)=vrai
*égaux (zéro, succ(x))=faux
*égaux (succ(x), zéro)= faux
* égaux (succ(x), succ(y))=égaux(x,y)
4. En déduire un algorithme récursif
(= la fonction fait appel à elle-même pour d'autre valeur des paramètres)
fonction egaux (x:entier,y:entier):booléen
|Début|
Si est_nul(x) et est_nul(y) alors
| retourner vrai
Sinon /* pas les deux nuls */
Si est_nul(x) alors
| retourner faux
Sinon
Si est_nul (y) alors
| retourner faux
Sinon
| retourner égaux (préc(x), préc(y))
Finsi
Finsi
Finsi
, |Fin|
ou
fonction egaux bis(x : entier_nat;y:entier_nat):booléen
|Début|
Si (est_nul(x) ou est_nul(y)) alors
| retourner (est_nul(x) et est_nul (y)
Finsi
retourner egaux bis(préc(x), préc(y))
|Fin|
5. Écrire un algorithme itératif (=pas récursif) pour la même fonction
On prend un exemple, en utilisant des variables
t 0 1 2 3
a SSS0 → préc SS0 → préc S0 → préc 0 STOP !
b SSSS0 → préc SSS0 → préc SS0 → préc S0
Deux variables a et b,
Au début a prend la valeur de x et b celle de y.
A chaque étape
a prend la valeur préc (a)
b prend la valeur préc (b)
On continue tant que ni a ni b n'est nul, ensuite si les deux sont nuls alors
retourner vrai sinon retourner faux.
Une nouvelle boucle :
Tant que (condition)
* actions *
Fin tant que
-teste la condition
→ si faux, va après le fin tant que
→ si vrai, fais les actions puis remonte en haut de la boucle
Fonction egaux. I(diminutif pour interatif) (x : entier_nat,y:entier_nat):booléen
var a,b : entier_nat
|Début|
a:=x
b:=y
Tant que (non( est_nul(a) ou est_nul(b)))
