420-201-RE – Formes d'alternatives

Pour les alternatives composites, on trouve deux grandes familles de formes générales, soit la forme imbriquée et la forme empilée. Les deux ont des avantages et des inconvénients.

Nous allons examiner chacune de ces formes à l'aide d'un même problème, soit trouver le plus petit de trois nombres.

Forme imbriquée

Résoudre ce problème avec une alternative de forme imbriquée signifie que nous visons à :

Séparer à chaque étape le problème en deux parties de taille semblable
S'assurer que le travail à faire soit semblable peu importe le chemin suivi par l'exécution du programme

Dans l'exemple qui suit, la première décision – l'alternative principale, comparant x et y – permet d'éliminer une des deux valeurs candidates (x ou y, selon le cas), puis l'alternative imbriquée dans chaque branche permet de choisir parmi les deux valeurs restantes.

En pseudocode En code C#

En pseudocode	En code C#
`Lire x Lire y Lire z Si x < y Alors Si x < z Alors plusPetit ← x Sinon plusPetit ← z Sinon Si y < z Alors plusPetit ← y Sinon plusPetit ← z Écrire plusPetit`	`// ... static void Main(string []args) { int x, y, z; int plusPetit; x = int.Parse(Console.ReadLine()); y = int.Parse(Console.ReadLine()); z = int.Parse(Console.ReadLine()); if (x < y) { if (x < z) { plusPetit = x; } else { plusPetit = z; } } else { if (y < z) { plusPetit = y; } else { plusPetit = z; } } Console.WriteLine(plusPetit); } // ...`

Lire x
Lire y
Lire z
Si x < y Alors
   Si x < z Alors
      plusPetit ← x
   Sinon
      plusPetit ← z
Sinon
   Si y < z Alors
      plusPetit ← y
   Sinon
      plusPetit ← z
Écrire plusPetit

// ...
static void Main(string []args)
{
   int x,
       y,
       z;
   int plusPetit;
   x = int.Parse(Console.ReadLine());
   y = int.Parse(Console.ReadLine());
   z = int.Parse(Console.ReadLine());
   if (x < y)
   {
      if (x < z)
      {
         plusPetit = x;
      }
      else
      {
         plusPetit = z;
      }
   }
   else
   {
      if (y < z)
      {
         plusPetit = y;
      }
      else
      {
         plusPetit = z;
      }
   }
   Console.WriteLine(plusPetit);
}
// ...

Cette forme a la qualité importante d'exiger le même nombre de tests de conditions peu importe le chemin suivi par l'exécution du programme. En effet, peu importe le chemin suivi ici, le programme nécessitera sept opérations (trois si on omet les entrées et les sorties).

Elle a par contre le gros défaut de se généraliser difficilement à un plus grand nombre de variables. Par exemple, avec quatre variables, on a :

En pseudocode En code C#

En pseudocode	En code C#
`Lire x Lire y Lire z Lire w Si x < y Alors Si x < z Alors Si x < w Alors plusPetit ← x Sinon plusPetit ← w Sinon Si z < w Alors plusPetit ← z Sinon plusPetit ← w Sinon Si y < z Alors Si y < w Alors plusPetit ← y Sinon plusPetit ← w Sinon Si z < w Alors plusPetit ← z Sinon plusPetit ← w Écrire plusPetit`	// ... static void Main(string []args) { int x, y, z, w; int plusPetit; x = int.Parse(Console.ReadLine()); y = int.Parse(Console.ReadLine()); z = int.Parse(Console.ReadLine()); w = int.Parse(Console.ReadLine()); if (x < y) { if (x < z) { if (x < w) { plusPetit = x; } else { plusPetit = w; } } else { if (z < w) { plusPetit = z; } else { plusPetit = w; } } } else { if (y < z) { if (y < w) { plusPetit = y; } else { plusPetit = w; } } else { if (z < w) { plusPetit = z; } else { plusPetit = w; } } } Console.WriteLine(plusPetit); } // ...

Lire x
Lire y
Lire z
Lire w
Si x < y Alors
   Si x < z Alors
      Si x < w Alors
         plusPetit ← x
      Sinon
         plusPetit ← w
   Sinon
      Si z < w Alors
         plusPetit ← z
      Sinon
         plusPetit ← w
Sinon
   Si y < z Alors
      Si y < w Alors
         plusPetit ← y
      Sinon
         plusPetit ← w
   Sinon
      Si z < w Alors
         plusPetit ← z
      Sinon
         plusPetit ← w
Écrire plusPetit

// ...
static void Main(string []args)
{
   int x,
       y,
       z,
       w;
   int plusPetit;
   x = int.Parse(Console.ReadLine());
   y = int.Parse(Console.ReadLine());
   z = int.Parse(Console.ReadLine());
   w = int.Parse(Console.ReadLine());
   if (x < y)
   {
      if (x < z)
      {
         if (x < w)
         {
            plusPetit = x;
         }
         else
         {
            plusPetit = w;
         }
      }
      else
      {
         if (z < w)
         {
            plusPetit = z;
         }
         else
         {
            plusPetit = w;
         }
      }
   }
   else
   {
      if (y < z)
      {
         if (y < w)
         {
            plusPetit = y;
         }
         else
         {
            plusPetit = w;
         }
      }
      else
      {
         if (z < w)
         {
            plusPetit = z;
         }
         else
         {
            plusPetit = w;
         }
      }
   }
   Console.WriteLine(plusPetit);
}
// ...

... ce qui est lourd et se prête à erreur humaine. Ici, peu importe le chemin suivi, le programme nécessitera neuf opérations (quatre si on omet les entrées et les sorties), mais il devient plus délicat de s'assurer que le programme fait correctement son travail.

La forme imbriquée tend à prendre de l'expansion « à l'horizontale », et à compliquer l'écriture du code, mais est typiquement la plus efficace des deux formes, et est donc privilégiée avec un petit nombre de valeurs candidates.

Forme imbriquée équilibrée

Une alternative est dite imbriquée si elle contient au moins une alternative dans laquelle on trouve une autre alternative. Ceci est un constat général pour lequel il existe une grande variété de cas. Par exemple :

En pseudocode En code C#

En pseudocode	En code C#
`RABAIS_BASE ← 2 RABAIS_ADDITIONNEL ← 3 PRIX_BASE ← 8 ÂGE_OR ← 65 ÂGE_OR_PLUS ← 75 prix ← PRIX_BASE Lire âge Si âge >= ÂGE_OR Alors prix ← prix - RABAIS_BASE Si âge >= ÂGE_OR_PLUS Alors prix ← prix - RABAIS_ADDITIONNEL Écrire prix`	`// ... static void Main(string []args) { const int RABAIS_BASE = 2; const int RABAIS_ADDITIONNEL = 3; const int PRIX_BASE = 8; const int ÂGE_OR = 65; const int ÂGE_OR_PLUS = 75; int âge, prix; âge = int.Parse(Console.ReadLine()); if (âge >= ÂGE_OR) { prix = prix - RABAIS_BASE; if (âge >= ÂGE_OR_PLUS) { prix = prix - RABAIS_ADDITIONNEL; } } Console.WriteLine(prix); } // ...`

RABAIS_BASE ← 2
RABAIS_ADDITIONNEL ← 3
PRIX_BASE ← 8
ÂGE_OR ← 65
ÂGE_OR_PLUS ← 75
prix ← PRIX_BASE
Lire âge
Si âge >= ÂGE_OR Alors
   prix ← prix - RABAIS_BASE
   Si âge >= ÂGE_OR_PLUS Alors
      prix ← prix - RABAIS_ADDITIONNEL
Écrire prix

// ...
static void Main(string []args)
{
   const int RABAIS_BASE = 2;
   const int RABAIS_ADDITIONNEL = 3;
   const int PRIX_BASE = 8;
   const int ÂGE_OR = 65;
   const int ÂGE_OR_PLUS = 75;
   int âge,
       prix;
   âge = int.Parse(Console.ReadLine());
   if (âge >= ÂGE_OR)
   {
      prix = prix - RABAIS_BASE;
      if (âge >= ÂGE_OR_PLUS)
      {
         prix = prix - RABAIS_ADDITIONNEL;
      }
   }
   Console.WriteLine(prix);
}
// ...

Une alternative imbriquée est équilibrée si le nombre d'opérations à faire entre la plus longue branche et la plus courte branche est d'au plus une étape. Le cas du programme trouvant le plus petit de trois nombres dans la forme proposée plus haut contient de telles alternatives.

Forme empilée

Résoudre ce problème avec une alternative de forme empilée signifie que nous visons à :

Prendre la première valeur candidate et supposer qu'elle est la meilleure d'entre elles
Considérer la prochaine valeur candidate avec la meilleure jusqu'ici, et retenir la meilleure des deux
Répéter le tout jusqu'à ce que toutes les valeurs candidates aient été examinées

L'exemple qui suit illustre bien cette mécanique.

En pseudocode En code C#

En pseudocode	En code C#
`Lire x Lire y Lire z plusPetit ← x Si y < plusPetit Alors plusPetit ← y Si z < plusPetit Alors plusPetit ← z Écrire plusPetit`	`// ... static void Main(string []args) { int x, y, z; int plusPetit; x = int.Parse(Console.ReadLine()); y = int.Parse(Console.ReadLine()); z = int.Parse(Console.ReadLine()); plusPetit = x; if (y < plusPetit) { plusPetit = y; } if (z < plusPetit) { plusPetit = z; } Console.WriteLine(plusPetit); } // ...`

Lire x
Lire y
Lire z
plusPetit ← x
Si y < plusPetit Alors
   plusPetit ← y
Si z < plusPetit Alors
   plusPetit ← z
Écrire plusPetit

// ...
static void Main(string []args)
{
   int x,
       y,
       z;
   int plusPetit;
   x = int.Parse(Console.ReadLine());
   y = int.Parse(Console.ReadLine());
   z = int.Parse(Console.ReadLine());
   plusPetit = x;
   if (y < plusPetit)
   {
      plusPetit = y;
   }
   if (z < plusPetit)
   {
      plusPetit = z;
   }
   Console.WriteLine(plusPetit);
}
// ...

Cette forme a la qualité importante de demeurer à toutes fins pratiques aussi simple peu importe le nombre de variables impliquées. Elle est par contre un peu moins équitable (et rapide) que la forme imbriquée : ici, on aura neuf opérations dans le pire cas (cinq si on omet les entrées/ sorties) et sept dans le meilleur cas (trois si on ne considère pas les entrées/ sorties).

Avec quatre variables, on a :

En pseudocode En code C#

En pseudocode	En code C#
`Lire x Lire y Lire z Lire w plusPetit ← x Si y < plusPetit Alors plusPetit ← y Si z < plusPetit Alors plusPetit ← z Si w < plusPetit Alors plusPetit ← w Écrire plusPetit`	`// ... static void Main(string []args) { int x, y, z, w; int plusPetit; x = int.Parse(Console.ReadLine()); y = int.Parse(Console.ReadLine()); z = int.Parse(Console.ReadLine()); w = int.Parse(Console.ReadLine()); plusPetit = x; if (y < plusPetit) { plusPetit = y; } if (z < plusPetit) { plusPetit = z; } if (w < plusPetit) { plusPetit = w; } Console.WriteLine(plusPetit); } // ...`

Lire x
Lire y
Lire z
Lire w
plusPetit ← x
Si y < plusPetit Alors
   plusPetit ← y
Si z < plusPetit Alors
   plusPetit ← z
Si w < plusPetit Alors
   plusPetit ← w
Écrire plusPetit

// ...
static void Main(string []args)
{
   int x,
       y,
       z,
       w;
   int plusPetit;
   x = int.Parse(Console.ReadLine());
   y = int.Parse(Console.ReadLine());
   z = int.Parse(Console.ReadLine());
   w = int.Parse(Console.ReadLine());
   plusPetit = x;
   if (y < plusPetit)
   {
      plusPetit = y;
   }
   if (z < plusPetit)
   {
      plusPetit = z;
   }
   if (w < plusPetit)
   {
      plusPetit = w;
   }
   Console.WriteLine(plusPetit);
}
// ...

... ce qui est nettement plus simple que la forme imbriquée avec le même nombre de variables; la difficulté est essentiellement la même, peu importe le nombre de variables.