Nous allons maintenant nous intéresser au maniement habile d’une variable booléenne : la technique dite du « flag ».
Le flag, en anglais, est un petit drapeau, qui va rester baissé aussi longtemps que l’événement attendu ne se produit pas. Et, aussitôt que cet événement a lieu, le petit drapeau se lève (la variable booléenne change de valeur). Ainsi, la valeur finale de la variable booléenne permet au programmeur de savoir si l’événement a eu lieu ou non.
Tout ceci peut vous sembler un peu fumeux, mais cela devrait s’éclairer à l’aide d’un exemple extrêmement fréquent : la recherche de l’occurrence d’une valeur dans un tableau. On en profitera au passage pour corriger une erreur particulièrement fréquente chez le programmeur débutant.
Soit un tableau comportant, disons, 20 valeurs. L’on doit écrire un algorithme saisissant un nombre au clavier, et qui informe l’utilisateur de la présence ou de l’absence de la valeur saisie dans le tableau.
La première étape, évidente, consiste à écrire les instructions de lecture / écriture, et la boucle – car il y en a manifestement une – de parcours du tableau :
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Fin
Il nous reste à combler les points d'interrogation de la boucle Pour. Évidemment, il va falloir comparer N à chaque élément du tableau : si les deux valeurs sont égales, alors bingo, N fait partie du tableau. Cela va se traduire, bien entendu, par un Si … Alors … Sinon. Et voilà le programmeur raisonnant hâtivement qui se vautre en écrivant :
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
Si N = Tab(i) Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
i suivant
Fin
Et patatras, cet algorithme est une véritable catastrophe.
Il suffit d'ailleurs de le faire tourner mentalement pour s'en rendre compte. De deux choses l'une : ou bien la valeur N figure dans le tableau, ou bien elle n'y figure pas. Mais dans tous les cas, l'algorithme ne doit produire qu'une seule réponse, quel que soit le nombre d'éléments que compte le tableau. Or, l'algorithme ci-dessus envoie à l'écran autant de messages qu'il y a de valeurs dans le tableau, en l'occurrence pas moins de 20 !
Il y a donc une erreur manifeste de conception : l'écriture du message ne peut se trouver à l'intérieur de la boucle : elle doit figurer à l'extérieur. On sait si la valeur était dans le tableau ou non uniquement lorsque le balayage du tableau est entièrement accompli.
Nous réécrivons donc cet algorithme en plaçant le test après la boucle. Faute de mieux, on se contentera de faire dépendre pour le moment la réponse d'une variable booléenne que nous appellerons Trouvé.
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
Il ne nous reste plus qu'à gérer la variable Trouvé. Ceci se fait en deux étapes.
un test figurant dans la boucle, indiquant lorsque la variable Trouvé doit devenir vraie (à savoir, lorsque la valeur N est rencontrée dans le tableau). Et attention : le test est asymétrique. Il ne comporte pas de "sinon". On reviendra là dessus dans un instant.
last, but not least, l'affectation par défaut de la variable Trouvé, dont la valeur de départ doit être évidemment Faux.
Au total, l'algorithme complet – et juste ! – donne :
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Trouvé ← Faux
Pour i ← 0 à 19
Si N = Tab(i) Alors
Trouvé ← Vrai
FinSi
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
Méditons un peu sur cette affaire.
La difficulté est de comprendre que dans une recherche, le problème ne se formule pas de la même manière selon qu'on le prend par un bout ou par un autre. On peut résumer l'affaire ainsi : il suffit que N soit égal à une seule valeur de Tab pour qu'elle fasse partie du tableau. En revanche, il faut qu'elle soit différente de toutes les valeurs de Tab pour qu'elle n'en fasse pas partie.
Voilà la raison qui nous oblige à passer par une variable booléenne , un « drapeau » qui peut se lever, mais jamais se rabaisser. Et cette technique de flag (que nous pourrions élégamment surnommer « gestion asymétrique de variable booléenne ») doit être mise en œuvre chaque fois que l’on se trouve devant pareille situation.
Autrement dit, connaître ce type de raisonnement est indispensable, et savoir le reproduire à bon escient ne l'est pas moins.
Mer 13 Fév - 9:48