rudless.

2. UN EXEMPLE DE FLAG : LA RECHERCHE DANS UN TABLEAU

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) AlorsAlors
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.

Autrement dit, connaître ce type de raisonnement est indispensable, et savoir le reproduire à bon escient ne l'est pas moins.

3. TRI DE TABLEAU + FLAG = TRI À BULLES

Et maintenant, nous en arrivons à la formule magique : tri de tableau + flag = tri à bulles. L’idée de départ du tri à bulles consiste à se dire qu’un tableau trié en ordre croissant, c’est un tableau dans lequel tout élément est plus petit que celui qui le suit.

En effet, prenons chaque élément d’un tableau, et comparons-le avec l’élément qui le suit. Si l’ordre n’est pas bon, on permute ces deux éléments. Et on recommence jusqu’à ce que l’on n’ait plus aucune permutation à effectuer. Les éléments les plus grands « remontent » ainsi peu à peu vers les dernières places, ce qui explique la charmante dénomination de « tri à bulle ». Comme quoi l’algorithmique n’exclut pas un minimum syndical de sens poétique.

En quoi le tri à bulles implique-t-il l’utilisation d’un flag ? Eh bien, par ce qu’on ne sait jamais par avance combien de remontées de bulles on doit effectuer. En fait, tout ce qu’on peut dire, c’est qu’on devra effectuer le tri jusqu’à ce qu’il n’y ait plus d’éléments qui soient mal classés. Ceci est typiquement un cas de question « asymétrique » : il suffit que deux éléments soient mal classés pour qu’un tableau ne soit pas trié. En revanche, il faut que tous les éléments soient bien rangés pour que le tableau soit trié.

Nous baptiserons le flag Yapermute, car cette variable booléenne va nous indiquer si nous venons ou non de procéder à une permutation au cours du dernier balayage du tableau (dans le cas contraire, c’est signe que le tableau est trié, et donc qu’on peut arrêter la machine à bulles).
La boucle principale sera alors :

Variable Yapermute en Booléen
Début
…
TantQue Yapermute
…
FinTantQue
Fin

Que va-t-on faire à l’intérieur de la boucle ? Prendre les éléments du tableau, du premier jusqu’à l’avant-dernier, et procéder à un échange si nécessaire. C’est parti :

Variable Yapermute en Booléen
Début
…
TantQue Yapermute
Pour i ← 0 à 10
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Finsi
i suivant
Fin

Mais il ne faut pas oublier un détail capital : la gestion de notre flag. L’idée, c’est que cette variable va nous signaler le fait qu’il y a eu au moins une permutation effectuée. Il faut donc :

• lui attribuer la valeur Vrai dès qu’une seule permutation a été faite (il suffit qu’il y en ait eu une seule pour qu’on doive tout recommencer encore une fois).
• la remettre à Faux à chaque tour de la boucle principale (quand on recommence un nouveau tour général de bulles, il n’y a pas encore eu d’éléments échangés),
• dernier point, il ne faut pas oublier de lancer la boucle principale, et pour cela de donner la valeur Vrai au flag au tout départ de l’algorithme.

La solution complète donne donc :

Variable Yapermute en Booléen
Début
…
Yapermut ← Vrai
TantQue Yapermut
Yapermut ← Faux
Pour i ← 0 à 10
Si t(i) > t(i+1) alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Yapermut ← Vrai
Finsi 
i suivant
FinTantQue
Fin

Au risque de me répéter, la compréhension et la maîtrise du principe du flag font partie de l’arsenal du programmeur bien armé.

4. LA RECHERCHE DICHOTOMIQUE

Je ne sais pas si on progresse vraiment en algorithmique, mais en tout cas, qu'est-ce qu'on apprend comme vocabulaire ! Blague dans le coin, nous allons terminer ce chapitre migraineux par une technique célèbre de recherche, qui révèle toute son utilité lorsque le nombre d'éléments est très élevé.

Par exemple, imaginons que nous ayons un programme qui doive vérifier si un mot existe dans le dictionnaire. Nous pouvons supposer que le dictionnaire a été préalablement entré dans un tableau (à raison d'un mot par emplacement). Ceci peut nous mener à, disons à la louche, 40 000 mots.

Une première manière de vérifier si un mot se trouve dans le dictionnaire consiste à examiner successivement tous les mots du dictionnaire, du premier au dernier, et à les comparer avec le mot à vérifier.

Ca marche, mais cela risque d'être long : si le mot ne se trouve pas dans le dictionnaire, le programme ne le saura qu'après 40 000 tours de boucle ! Et même si le mot figure dans le dictionnaire, la réponse exigera tout de même en moyenne 20 000 tours de boucle. C'est beaucoup, même pour un ordinateur.

Or, il y a une autre manière de chercher, bien plus intelligente pourrait-on dire, et qui met à profit le fait que dans un dictionnaire, les mots sont triés par ordre alphabétique. D'ailleurs, un être humain qui cherche un mot dans le dictionnaire ne lit jamais tous les mots, du premier au dernier : il utilise lui aussi le fait que les mots sont triés.

Pour une machine, quelle est la manière la plus rationnelle de chercher dans un dictionnaire ? C'est de comparer le mot à vérifier avec le mot qui se trouve pile poil au milieu du dictionnaire. Si le mot à vérifier est antérieur dans l'ordre alphabétique, on sait qu'on devra le chercher dorénavant dans le première moitié du dico. Sinon, on sait maintenant qu'on devra le chercher dans la deuxième moitié.

A partir de là, on prend la moitié de dictionnaire qui nous reste, et on recommence : on compare le mot à chercher avec celui qui se trouve au milieu du morceau de dictionnaire restant. On écarte la mauvaise moitié, et on recommence, et ainsi de suite.

A force de couper notre dictionnaire en deux, puis encore en deux, etc. on va finir par se retrouver avec des morceaux qui ne contiennent plus qu'un seul mot. Et si on n'est pas tombé sur le bon mot à un moment ou à un autre, c'est que le mot à vérifier ne fait pas partie du dictionnaire. Regardons ce que cela donne en terme de nombre d'opérations à effectuer, en choisissant le pire cas : celui où le mot est absent du dictionnaire.

• Au départ, on cherche le mot parmi 40 000.
• Après le test n°1, on ne le cherche plus que parmi 20 000.
• Après le test n°2, on ne le cherche plus que parmi 10 000.
• Après le test n°3, on ne le cherche plus que parmi 5 000.
• etc.
• Après le test n°15, on ne le cherche plus que parmi 2.
• Après le test n°16, on ne le cherche plus que parmi 1.

Et là, on sait que le mot n'existe pas. Moralité : on a obtenu notre réponse en 16 opérations contre 40 000 précédemment ! Il n'y a pas photo sur l'écart de performances entre la technique barbare et la technique futée. Attention, toutefois, même si c'est évident, je le répète avec force : la recherche dichotomique ne peut s'effectuer que sur des éléments préalablement triés. Eh bien maintenant que je vous ai expliqué comment faire, vous n'avez plus qu'à traduire ! Au risque de me répéter, la compréhension et la maîtrise du principe du flag font partie du bagage du programmeur bien outillé.

ENONCE DES EXERCICES

Exercice 7.1

Ecrivez un algorithme qui permette de saisir un nombre quelconque de valeurs, et qui les range au fur et à mesure dans un tableau. Le programme, une fois la saisie terminée, doit dire si les éléments du tableau sont tous consécutifs ou non. Par exemple, si le tableau est :
12 13 14 15 16 17 18
ses éléments sont tous consécutifs. En revanche, si le tableau est :
9 10 11 15 16 17 18
ses éléments ne sont pas tous consécutifs.

Ecrivez un algorithme qui trie un tableau dans l’ordre décroissant. Vous écrirez bien entendu deux versions de cet algorithme, l'une employant le tri par insertion, l'autre le tri à bulles.

Exercice 7.3

Ecrivez un algorithme qui inverse l’ordre des éléments d’un tableau dont on suppose qu'il a été préalablement saisi (« les premiers seront les derniers… »)

Exercice 7.4

Ecrivez un algorithme qui permette à l’utilisateur de supprimer une valeur d’un tableau préalablement saisi. L’utilisateur donnera l’indice de la valeur qu’il souhaite supprimer. Attention, il ne s’agit pas de remettre une valeur à zéro, mais bel et bien de la supprimer du tableau lui-même ! Si le tableau de départ était :
12 8 4 45 64 9 2
Et que l’utilisateur souhaite supprimer la valeur d’indice 4, le nouveau tableau sera :
12 8 4 45 9 2

Exercice 7.5

Ecrivez l'algorithme qui recherche un mot saisi au clavier dans un dictionnaire. Le dictionnaire est supposé être codé dans un tableau préalablement rempli et trié.

CORRIGÉS DES EXERCICES

Exercice 7.1

Variables Nb, i en Entier
Variable Flag en Booleen
Tableau T() en Entier
Debut
Ecrire "Entrez le nombre de valeurs :"
Lire Nb
Redim T(Nb-1)
Pour i ← 0 à Nb - 1
 Ecrire "Entrez le nombre n° ", i + 1
 Lire T(i)
i Suivant
Flag ← Vrai
Pour i ← 1 à Nb - 1
 Si T(i) <> T(i – 1) + 1 Alors
 Flag ← Faux
 FinSi
i Suivant
Si Flag Alors
 Ecrire "Les nombres sont consécutifs"
Sinon
 Ecrire "Les nombres ne sont pas consécutifs"
FinSi
Fin

Cette programmation est sans doute la plus spontanée, mais elle présente le défaut d'examiner la totalité du tableau, même lorsqu'on découvre dès le départ deux éléments non consécutifs. Aussi, dans le cas d'un grand tableau, est-elle dispendieuse en temps de traitement. Une autre manière de procéder serait de sortir de la boucle dès que deux éléments non consécutifs sont détectés. La deuxième partie de l'algorithme deviendrait donc :

i ← 1
TantQue T(i) = T(i – 1) + 1 et i < Nb - 1
 i ← i + 1
FinTantQue
Si T(i) = T(i – 1) + 1 Alors
 Ecrire "Les nombres sont consécutifs"
Sinon
 Ecrire "Les nombres ne sont pas consécutifs"
FinSi

Exercice 7.2

On suppose que N est le nombre d’éléments du tableau. Tri par insertion :

…
Pour i ← 0 à N - 2
 posmaxi = i
 Pour j ← i + 1 à N - 1
 Si t(j) > t(posmaxi) alors
 posmaxi ← j
 Finsi
 j suivant
 temp ← t(posmaxi)
 t(posmaxi) ← t(i)
 t(i) ← temp 
i suivant
Fin

Tri à bulles :

…
Yapermut ← Vrai
TantQue Yapermut
 Yapermut ← Faux
 Pour i ← 0 à N - 2
 Si t(i) < t(i + 1) Alors
 temp ← t(i)
 t(i) ← t(i + 1)
 t(i + 1) ← temp
 Yapermut ← Vrai
 Finsi
 i suivant
FinTantQue
Fin

Exercice 7.3

On suppose que n est le nombre d’éléments du tableau préalablement saisi

…
Pour i ← 0 à (N-1)/2
 Temp ← T(i)
 T(i) ← T(N-1-i)
 T(N-1-i) ← Temp
i suivant
Fin

Exercice 7.4

…
Ecrire "Rang de la valeur à supprimer ?"
Lire S
Pour i ← S à N-2
 T(i) ← T(i+1)
i suivant
Redim T(N–1)
Fin

Exercice 7.5

N est le nombre d'éléments du tableau Dico(), contenant les mots du dictionnaire, tableau préalablement rempli.

Variables Sup, Inf, Comp en Entier
Variables Fini en Booléen
Début
Ecrire "Entrez le mot à vérifier"
Lire Mot
On définit les bornes de la partie du tableau à considérer
Sup ← N - 1
Inf ← 0
Fini ← Faux
TantQue Non Fini

Comp désigne l'indice de l'élément à comparer. En bonne rigueur, il faudra veiller à ce que Comp soit bien un nombre entier, ce qui pourra s'effectuer de différentes manières selon les langages.
Comp ← (Sup + Inf)/2

Si le mot se situe avant le point de comparaison, alors la borne supérieure change, la borne inférieure ne bouge pas.

 Si Mot < Dico(Comp) Alors
 Sup ← Comp - 1
Sinon, c'est l'inverse
 Sinon
 Inf ← Comp + 1
 FinSi
 Fini ← Mot = Dico(Comp) ou Sup < Inf
FinTantQue
Si Mot = Dico(Comp) Alors
 Ecrire "le mot existe"
Sinon
 Ecrire "Il n'existe pas"
Finsi
Fin