\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\)

Vidéo 26 : Technique du drapeau¶

La technique du drapeau dans une boucle for¶

Soit à définir un code Python qui partant d’une liste L d’entiers détermine si L ne contient que des entiers positifs. Plus précisément, le code doit définir un booléen nommé tousPositifs qui vaut True si L ne contient que des entiers positifs et False sinon.

Le code suivant réalise cette tâche sur deux exemples de liste :

# 1er exemple
L= [31, 82, -42, 32, -81]

tousPositifs = True
for z in L:
    if z < 0:
        tousPositifs = False
print(L, '->', tousPositifs)

print("---------------------")

# 2e exemple
L= [31, 82, 421, 32, 81]

tousPositifs = True
for z in L:
    if z < 0:
        tousPositifs = False
print(L, '->', tousPositifs)

[31, 82, -42, 32, -81] -> False
---------------------
[31, 82, 421, 32, 81] -> True

Le même code (lignes 4-8 et lignes 15-19) est testé avec deux listes différentes (lignes 2 et 13). Ci-dessous, les commentaires ne portent que sur le premier groupe de code.
Dans chaque cas, on affiche la liste L (lignes 8) et le booléen tousPositifs.
Lignes 4 : on définit au début du code un « drapeau », ici le booléen tousPositifs ; ce drapeau témoigne d’un état, l’état étant que la liste L contienne uniquement des nombres positifs (True) ou non (False). Au départ, le drapeau tousPositifs est placé sur True.
lignes 6-7 : La liste L est parcourue et si au cours du parcours de L, la présence dans la liste d’un entier strictement négatif est détectée (ligne 6), le drapeau change de couleur, ici il passe à False (ligne 7). Le drapeau ne change que si un entier négatif est détecté, autrement dit le if n’est pas couplé à un else.
Ligne 5-8 : si le drapeau change par rapport à son état initial, c’est qu’un entier négatif a été détecté dans la liste L et donc il est attendu que le drapeau tousPositifs vaille False, ce qui est bien le cas, cf. ligne 20.
Lignes 15-18 : si au contraire, la liste L est parcourue sans que le drapeau ait changé, c’est qu’aucun entier négatif n’est jamais rencontré et donc il est attendu que le drapeau tousPositifs vaille True, ce qui est bien le cas, cf. ligne 22.

Ainsi le code ci-dessus réalise bien la tâche attendue.

Initialisation du drapeau¶

Comment est déterminée la valeur initiale du drapeau ? Réponse : en fonction de ce que représente le booléen une fois toute la liste parcourue. Si le booléen True doit correspondre au fait que tous les entiers sont positifs, c’est que le booléen doit changer en False dans la boucle quand un entier négatif est détecté et donc, le booléen doit être initialisé à True. Il serait possible de réaliser le même objectif en utilisant un autre drapeau initialisé à False :

L= [31, 82, -42, 32, -81]

contientNegatif = False
for z in L:
    if z < 0:
        contientNegatif = True
print(L, '->', contientNegatif)

print("=========================")

L= [31, 82, 421, 32, 81]

contientNegatif = False
for z in L:
    if z < 0:
        contientNegatif = True
print(L, '->', contientNegatif)

[31, 82, -42, 32, -81] -> True
=========================
[31, 82, 421, 32, 81] -> False

Ligne 3 : on définit un drapeau contientNegatif qui vaudra True si L contient au moins un entier strictement négatif et False sinon.
Lignes 5-6 : lorsqu’on parcourt la liste, le drapeau doit passer à True si un entier strictement négatif apparaît, donc le drapeau doit être initialisé à False.

Alternance de parité¶

On donne une liste L d’entiers et on demande de créer un booléen alterneParite valant True si les éléments de L se suivent en alternant de parité et False sinon. Voici des exemples de comportements attendus :

`L`	Alternance de parité
`[81, 32, 9, 12]`	`True`
`[32, 9, 32, 65]`	`True`
`[32, 9, 31, 82]`	`False`
`[81]`	`True`

Solution

Il s’agit d’appliquer la technique du drapeau. Il faut parcourir la liste de L. Mais comme il faut à chaque étape comparer les parités de deux éléments consécutifs, la boucle de parcours a la forme avec indice suivante :

n=len(L)

for i in range(n-1):
    # Code à compléter

La parité d’un entier a est donnée par le reste a % 2. Donc, deux éléments consécutifs de L ont des parités différentes si L[i] % 2 != L[i+1] % 2. Dans le cas contraire, le drapeau de surveillance de parité doit changer. D’où le code suivant :

L = [81, 32, 9, 12]
alterneParite = True

for i in range(0,len(L)-1):
    if L[i] % 2 == L[i+1] % 2:
        alterneParite = False

print(alterneParite)

True

Testons plusieurs listes placées dans une liste tests :

tests = [[81, 32, 9, 12],[32, 9, 32, 65], [32, 9, 31, 82],[81]]

for L in tests:

    alterneParite = True

    for i in range(0,len(L)-1):
        if L[i] % 2 == L[i+1] % 2:
            alterneParite = False

    print(L, "->", alterneParite)

[81, 32, 9, 12] -> True
[32, 9, 32, 65] -> True
[32, 9, 31, 82] -> False
[81] -> True

On pourra remarquer que le code

L = [81, 32, 9, 12]
alterneParite = True

for i in range(0,len(L)-1):
    if L[i] % 2 == L[i+1] % 2:
        alterneParite = False

print(alterneParite)

n’est pas parfaitement optimal, déjà parce que la technique du drapeau n’est pas optimale et aussi parce que la parité de chaque élément de la liste ayant un voisin est évaluée deux fois (cf. ligne 5).