Cours complet d’initiation à la programmation

État initial : tas 1 un trèfle ou un pique, les autres tas sont vides.

État final : tas 1 et 4 vides, le tas 2 contient le trèfle ou rien et le tas 3 contient le pique ou rien.

2-1-1. Algorithme▲

2-2-1. Booléens▲

2-2-2. Expressions simples▲

2-2-3. Expressions composées▲

2-2-4. Propriétés des opérateurs▲

2-3-1. Booléens▲

2-3-2. Expressions booléennes▲

Les expressions booléennes simples peuvent s'exprimer en Caml par :

• des valeurs littérales true ou false ;
• une variable booléenne (voir plus tard) ;
• une expression décrivant une relation ;
• un appel à une fonction à valeurs booléennes.

Exemple 1 :

Tous les exemples donnés par la suite s'appuient sur une configuration des tas donnée à la figure 2.1.

 

Sélectionnez

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

# true ;;
- : bool = true
# false ;;
- : bool = false
# tas_vide(1);;
- : bool = true
# tas_non_vide(1);;
- : bool = false
# couleur_sommet(2) = PIQUE;;
- : bool = false
# couleur_sommet(2) = CARREAU;;
- : bool = true
# sommet_trefle(3);;
- : bool = true

Les expressions composées se traduisent avec les opérateurs logiques &&, || et not.

Table 2.5 - Opérateurs logiques en Caml

Opérateur logique	et	ou	non
En Caml	&&	||	not

Exemple 2 :

 

Sélectionnez

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

# true && true;;
- : bool = true
# true && false;;
- : bool = false
# true || false;;
- : bool = true
# false || false;;
- : bool = false
# not (true);;
- : bool = false
# not (false);;
- : bool = true
# sommet_carreau(2) && sommet_trefle(3) ;;
- : bool = true
# sommet_carreau(2) && not (sommet_coeur(3)) ;;
- : bool = true
# tas_non_vide(1) || sommet_coeur(4);;
- : bool = true

2-3-3. Attention :▲

couleur_sommet(1) = TREFLE || CARREAU

couleur_sommet(1) = TREFLE || couleur_sommet(1) = CARREAU

2-3-4. Remarque sur les opérateurs && et ||▲

# tas_non_vide(1) && sommet_trefle(1);;
- : bool = false

# sommet_trefle(1) && tas_non_vide(1) ;;
Exception: LesExceptions.Tas_Vide 1.

Les expressions conditionnelles sont des expressions qui déterminent l'expression à évaluer en fonction de la validité d'une condition.

if < condition > then
  < expression 1 >
else
  < expression 2 >

Exemple 4 :

Dans le contexte indiqué par la figure 2.1, on a

# if sommet_carreau(2) then
    0
  else
    1 ;;
- : int = 0
# if sommet_trefle(2) then
    0
  else
    1 ;;
- : int = 1

Les instructions conditionnelles sont des expressions conditionnelles dont la valeur est du type unit. On les utilise pour agir en fonction d'un contexte.

Instruction conditionnelle complète

L'instruction conditionnelle complète (ou alternative) permet de mener une action si une condition est satisfaite, et une autre dans le cas contraire.

if < condition > then
  (* bloc d'instructions *)
else
  (* bloc d'instructions *)

Exemple 5 :

Traduction en Caml de l'algorithme décrit à la section 2.1.1Algorithme.

if sommet_trefle(1) then begin
  deplacer_sommet(1,2)
end else begin
  deplacer_sommet(1,3)
end

La condition est ici exprimée par l'expression booléenne (simple) sommet_trefle(1), le premier bloc d'instructions (celui qui suit le mot réservé then) est

begin
  deplacer_sommet(1,2)
end

et le second bloc (qui suit le mot réservé else).

begin
  deplacer_sommet(1,3)
end

Notez qu'il n'y a pas de ; après le end qui précède le else. En revanche, si cette instruction conditionnelle est suivie d'une autre, il faudra ajouter un ; après le end du second bloc (end {if};).

Instruction conditionnelle simple

Il arrive qu'une action ait besoin d'être menée si une condition est satisfaite, mais qu'aucune ne soit nécessaire sinon. C'est alors une instruction conditionnelle simple. En Caml, elle s'écrit sans la partie else.

if < condition > then
  (* bloc d'instructions *)

Exemple 6 :

Déplacer la carte située au sommet du tas 1 si c'est un trèfle sinon ne rien faire.

if sommet_trefle(1) then begin
  deplacer_sommet(1,2)
end

2-5-1. Remarque sur le parenthésage▲

if sommet_trefle(1) then
  deplacer_sommet(1,2)
else
  deplacer_sommet(1,3)

if sommet_trefle(1) then begin
  deplacer_sommet(1,2);
  deplacer_sommet(2,3)
end

if sommet_trefle(1) then
  deplacer_sommet(1,2);
  deplacer_sommet(2,3)

Voici quelques principes méthodologiques concernant la conception d'instructions conditionnelles :

1. Étude des cas intervenant dans le problème :

   • commencer par distinguer les différents cas ;
   • vérifier que ces cas sont bien exhaustifs (on n'oublie aucune situation) ;
   • vérifier que ces cas ne sont pas redondants (cas exclusifs) ;
   • donner un exemple de comportement attendu de l'instruction pour chacun des cas.

2. Pour chacun des cas :

   • établir un test (expression booléenne) permettant de distinguer le cas ;
   • déterminer la séquence d'instructions à exécuter dans ce cas.

3. Construire un jeu de tests qui permet de s'assurer de la validité du programme : ce jeu doit comprendre au moins un test pour chacun des cas envisagés.

Exemple

Considérons une situation initiale où les tas numérotés de 1 à 3 contiennent un nombre quelconque non nul de cartes, et le tas 4 est vide.

init_tas(1,"(T+K+C+P)[T+K+C+P]");
init_tas(2,"(T+K+C+P)[T+K+C+P]");
init_tas(3,"(T+K+C+P)[T+K+C+P]");
init_tas(4,"");

L'objectif à atteindre est de déplacer la carte de plus grande valeur au sommet d'un des trois tas vers le tas 4.

Résoudre ce problème revient à repérer quel tas possède en son sommet la carte de plus grande valeur.

Étude des cas

Il y a évidemment trois possibilités : c'est le tas 1 ou le tas 2 ou le tas 3. Comment les distinguer ?

• c'est le tas 1, si la carte au sommet du tas 1 est supérieure ou égale à celle du tas 2, et est supérieure ou égale à celle du tas 3 ;
• c'est le tas 2, si la carte au sommet du tas 2 est supérieure ou égale à celle du tas 1, et est supérieure ou égale à celle du tas 3 ;
• c'est le tas 3, si la carte au sommet du tas 3 est supérieure ou égale à celle du tas 1, et est supérieure ou égale à celle du tas 2.

Autrement dit c'est le tas i si la condition superieur(i,j) && superieur(i,k) (dans laquelle j et k désignent les deux numéros de tas autres que i) est satisfaite. Les conditions distinguant les trois cas ne sont pas exclusives (pensez aux cas d'égalité).

Exercice 2-1

En utilisant les tables de vérité, prouvez quelques propriétés des opérateurs logiques et, ou et non.

Exercice 2-2 Ou exclusif

Si a et b sont deux expressions booléennes, le ou-exclusif de ces deux expressions, noté a⊕b, est une nouvelle expression booléenne qui est vraie si et seulement si une seule des deux expressions a ou b est vraie. La table de vérité du ou-exclusif est donnée

Écrivez l'expression a ⊕ b à l'aide des opérateurs et, ou et non.

Exercice 2-3

Question 1 : Exprimez le fait que [a,b] et [c,d] sont des intervalles disjoints, attention au cas des intervalles vides, par exemple si a = 15 et b = -5.

Question 2 : Exprimez le fait que [a,b] et [c,d] sont des intervalles qui se recouvrent partiellement de deux manières :

• en utilisant la solution de la question précédente (c'est très simple) ;
• directement (c'est compliqué !).

Exercice 2-4 Égalité et valeur booléenne

Question 1 : Soit a une expression booléenne. Réalisez la table de vérité des expressions :

1. a = V ;
2. a = F.

Exercice 2-5

Question 1

Écrivez l'instruction ci-dessous sans utiliser l'opérateur non ni d'opérateurs de comparaison.

si non a alors

  instr1

sinon

  instr2

fin si

Question 2

Écrivez l'instruction ci-dessous sans utiliser l'opérateur et

si a et b alors

  instr1

fin si

Question 3

Écrivez l'instruction ci-dessous sans utiliser l'opérateur ou

si a ou b alors

  instr1

fin si

Exercice 2-6

Expliquez pourquoi le programme

if superieur(1,2) && superieur(1,3) then begin
  deplacer_sommet(1,4)
end;
if superieur(2,1) && superieur(2,3) then begin
  deplacer_sommet(2,4)
end;
if superieur(3,1) && superieur(3,2) then begin
  deplacer_sommet(3,4)
end ;;

n'est pas correct pour le problème posé dans la section 2.6Méthodologie.

Exercice 2-7

Reprenez le problème de la section 2.6Méthodologie en admettant qu'un ou plusieurs des trois premiers tas peut être vide. Si les trois tas sont vides, on ne déplace aucune carte.