Skip to content

Programmer la recherche du maximum☘

Exercice 1☘

Donner un corps possible pour la fonction suivante:

1
2
3
4
5
def max_binaire(a,b):
    """
    a et b sont de type int.
    La fonction renvoie la plus grande des deux valeurs a, b.
    """

Note

Le mot binaire utilisé ici ne signifie pas que l'on raisonne sur des nombres écrits en base 2. Il signifie que l'on travaille avec deux arguments (a et b). Une définition du mot binaire.

Un code possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def max_binaire(a, b):
    """
    a et b sont de type int.
    La fonction renvoie le plus grand des deux.
    """
    if a > b: return a
    else: return b

# tests
print(max_binaire(5, 3))
print(max_binaire(2, 3))

Python propose également une syntaxe plus brève:

1
2
3
4
5
6
def max_bin(a,b):
    return a if a > b else b

# tests
print(max_bin(5, 3))
print(max_bin(2, 3))

Exercice 2☘

Donner un corps possible pour la fonction max_ternaire ci-dessous.

Contrainte: le code de votre fonction max_ternaire ne doit contenir aucun if et fera appel aux services de la fonction max_binaire.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def max_binaire(a,b):
    """
    a et b sont de type int.
    La fonction renvoie la plus grande des deux valeurs a, b.
    """
        return a if a > b else b

def max_ternaire(a,b,c):
    """
    a, b, c sont de type int.
    La fonction renvoie la plus grande des trois valeurs.
    """
Un code possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def max_binaire(a,b):
        return a if a > b else b

def max_ternaire(a,b,c):
    """
    a, b, c sont de type int.
    La fonction renvoie la plus grande des trois valeurs.
    """
    m = max_binaire(a,b)
    m = max_binaire(m,c)
    return m

# tests

a, b, c = 3, 5, 7
print(max_ternaire(a,b,c))

a, b, c = 5, 7, 3
print(max_ternaire(a,b,c))

a, b, c = 7, 5, 3
print(max_ternaire(a,b,c))

Exercice 3☘

Question 1☘

Même consigne avec la fonction max_arité4.

1
2
3
4
5
6
7
8
def max_binaire(a,b):
        return a if a > b else b

def max_arité4(a,b,c,d):
    """
    a, b, c, d sont de type int.
    La fonction renvoie la plus grande des quatre valeurs.
    """
Un code possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def max_binaire(a,b):
        return a if a > b else b

def max_arité4(a,b,c,d):
    """
    a, b, c, d sont de type int.
    La fonction renvoie la plus grande des quatre valeurs.
    """
    m = max_binaire(a,b)
    m = max_binaire(m,c)
    m = max_binaire(m,d)
    return m

# tests
a, b, c, d = 3, 5, 7, 9
print(max_arité4(a,b,c,d))

a, b, c, d = 5, 7, 9, 3
print(max_arité4(a,b,c,d))

a, b, c, d = 9, 7, 5, 3
print(max_arité4(a,b,c,d))


a, b, c, d =  7, 9, 5, 3
print(max_arité4(a,b,c,d))

a, b, c, d =  7, 9, 5, 9
print(max_arité4(a,b,c,d))
Améliorer les tests

Il est plus sûr de définir une fonction pour vérifier à chaque fois que l'on bien le maximum (car le programmeur est susceptible de fatigue et donc de passer à côté d'un mauvais affichage):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def est_max(valeur, a,b,c,d):
    """
    int * int * int * int * int -> bool
    La fonction renvoie True si valeur = max(a,b,c,d)
    et False sinon.
    """
    for x in (a,b,c,d):
        if valeur < x:
            return False
    if valeur in (a,b,c,d): return True


def max_binaire(a,b):
    """
    int * int -> int
    La fonction renvoie le plus grand des deux entiers a et b.
    """
    return a if a > b else b

def max_arité4(a,b,c,d):
    """
    int * int * int * int -> int    
    La fonction renvoie la plus grande des quatre valeurs a, b, c, d.
    """
    m = max_binaire(a,b)
    m = max_binaire(m,c)
    m = max_binaire(m,d)
    return m

# tests
a, b, c, d = 3, 5, 7, 9
print(est_max(max_arité4(a,b,c,d), a,b,c,d))

a, b, c, d = 5, 7, 9, 3
print(est_max(max_arité4(a,b,c,d), a,b,c,d))

a, b, c, d = 9, 7, 5, 3
print(est_max(max_arité4(a,b,c,d), a,b,c,d))


a, b, c, d =  7, 9, 5, 3
print(est_max(max_arité4(a,b,c,d), a,b,c,d))

a, b, c, d =  7, 9, 5, 9
print(est_max(max_arité4(a,b,c,d), a,b,c,d))

On obtient:

1
2
3
4
5
True
True
True
True
True

Question 2☘

Dans le corrigé proposé pour la question 1, qu'est-ce qui a guidé nos tests? A quoi faut-il penser lorsque l'on teste une fonction?

Eléments de réponse

Les tests doivent essayer de couvrir tous les cas d'utilisation. Il est en fait en général impossible de couvrir tous les cas d'utilisation. On s'efforce donc de penser aux divers cas de figure possible.

  • Ici on peut par exemple penser que la position de la valeur maximale parmi les 4 arguments est importante (si, par exemple, on a oublié dans notre code l'une des lignes, les tests le mettront probablement en évidence.)
  • On se pose également la question du cas particulier d'un maximum plusieurs fois présent.

Exercice 4☘

On aimerait maintenant écrire le code du corps de la fonction max_tableau prenant en paramètre une liste d'entiers et renvoyant la plus grande valeur contenue dans cette liste.

Question 1☘

Une partie du code de Max se trouve ci-dessous. Compléter les pointillés.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = max_binaire(tab[0], tab[1])
    ....
    return m
Le code complété
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = max_binaire(tab[0], tab[1])
    for x in tab:
        m = max_binaire(m,x)
    return m

Question 2☘

Faites des tests en générant des listes d'entiers au hasard sur le code donné dans le corrigé de la question précédente.

Générer une liste au hasard

Pour générer une liste au hasard, on utilise le module random.

1
2
3
4
5
6
7
8
9
from random import randint

# rappel: randint(a,b) tire un entier p au hasard avec a <= p <= b.
# on crée une liste en tirant sa longueur et ses éléments au hasard:

longueur =  randint(5,17)
L = [ randint(1,20) for _ in range(longueur)]

print(L)
Des tests possibles

Avec les tests générés dans le code ci-dessous (on relance plusieurs fois le code pour avoir une série de listes distinctes), notre fonction semble fonctionner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = max_binaire(tab[0], tab[1])
    for x in tab:
        m = max_binaire(m,x)
    return m


# tests

# rappel: randint(a,b) tire un entier p au hasard avec a <= p <= b.
from random import randint

# on crée une liste en tirant sa longueur et ses éléments au hasard:
L = [ randint(1,20) for _ in range(randint(5,17))]

# on calcule le maximum avec notre fonction:
monMax =  max_tableau(L)
# on utilise la fonction prédéfinie de python pour vérifier que 
# notre fonction renvoie bien le maximum:
print( monMax == max(L))

Question 3☘

Notre fonction max_tableau fonctionne-t-elle vraiment dans tous les cas? Quelle situation avons-nous oubliée?

Un cas oublié

Testez le cas d'une liste ne comportant qu'un seul élément.

On obtient:

1
IndexError: list index out of range

Cette erreur (que vous rencontrerez sans doute souvent en travaillant avec les listes) signifie que vous avez cherché à utiliser un élément de la liste qui n'existe pas.

En général, cela signifie que le code cherche à utiliser L[p] où p est un entier supérieur ou égal à la longueur de liste. Voyez-vous ici à quel endroit du code se situe le problème?

Où se situe le problème?

Le problème se trouve dans la ligne m = max_binaire(tab[0], tab[1]). Si la liste ne contient qu'un seul élément, tab[1] n'existe pas.

Question 4☘

Proposer un code qui corrige l'oubli relevé dans la question précédente.

Une correction du code

Au lieu d'initialiser m sur le maximum des deux premiers éléments, on initialise m sur la valeur du premier élément.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = tab[0]
    for x in tab:
        m = max_binaire(m,x)
    return m


#  **** les tests ***

L = [5]
print("Cas de la liste de longueur 1: ", max(L) == max_tableau(L))

# rappel: randint(a,b) tire un entier p au hasard avec a <= p <= b.
from random import randint

# on crée une liste en tirant sa longueur et ses éléments au hasard:
L = [ randint(1,20) for _ in range(randint(5,17))]

# on calcule le maximum avec notre fonction:
monMax =  max_tableau(L)
# on utilise la fonction prédéfinie de python pour vérifier que 
# notre fonction renvoie bien le maximum:
print("Notre max est-il ok?: ", monMax == max(L))

Exercice 5☘

Et si la liste est de longueur 0?

Il serait assez logique d'exiger que l'argument donné à notre fonction max_tableau ne soit jamais vide.

Question 1☘

Est-ce le choix fait par les concepteurs du langage Python avec la fonction prédéfinie max? Faites des tests.

La réponse python
1
2
3
4
>>> max([])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: max() arg is an empty sequence

La réponse est claire: l'argument de la fonction max() ne peut pas être une séquence vide.

Question 2☘

Chercher le rôle de assert sur la toile. Lire par exemple cette page ou encore celle-ci.

Ajouter une assertion dans le code de la fonction max_tableau définie plus haut (corrigé de la question 3 de l'exercice 4) afin d'obtenir un message similaire à ce que propose la fonction prédéfinie max lorsqu'on lui donne en argument une liste vide.

Un code possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    assert L != [], "Attention, l'argument de la fonction max_tableau ne peut pas être une liste vide."
    m = tab[0]
    for x in tab:
        m = max_binaire(m,x)
    return m


#  ****  test  ***


L = [2]
print(f"Max de la liste {L}: {max_tableau(L)}")
print("*"*25)
print()

L = []
print("Cas d'une liste vide :", max_tableau(L))

On obtient l'affichage:

1
2
3
4
5
6
7
8
9
Max de la liste [2]: 2
*************************

Traceback (most recent call last):
  File "a.py", line 25, in <module>
    print("Cas d'une liste vide :", max_tableau(L))
  File "a.py", line 9, in max_tableau
    assert L != [], "Attention, l'argument de la fonction max_tableau ne peut pas être une liste vide."
AssertionError: Attention, l'argument de la fonction max_tableau ne peut pas être une liste vide.

Exercice 6☘

Plutôt que le code proposé auparavant pour la fonction max_tableau, Max propose le code suivant (modification à la ligne 10 du code):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    assert L != [], "Attention, l'argument de la fonction max_tableau ne peut pas être une liste vide."
    m = 0
    for x in tab:
        m = max_binaire(m,x)
    return m

Donner un exemple de liste d'entiers pour laquelle la fonction proposée ne renverra pas la valeur maximale.

Une réponse

Une liste d'entiers négatifs montre que la fonction est mal programmée.

On teste la fonction par exemple comme suit:

1
2
L = [-2, -3, -7]
print(f"Max de la liste {L}: {max_tableau(L)}")

on obtient l'affichage:

1
Max de la liste [-2, -3, -7]: 0

Il est donc important d'initialiser la variable m avec une valeur de la liste.

Exercice 7☘

Max étant tétu et ne voulant absolument pas initialiser m avec un élément de la liste, il propose le code suivant:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from math import inf

def max_binaire(a,b):
        return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = -inf
    for x in tab:
        m = max_binaire(m,x)
    return m

Question 1☘

Faites des tests, vérifier que ce code fonctionne. Après des recherches éventuelles sur la toile sur math.inf, expliquer pourquoi ceci fonctionne.

Une réponse

Des tests:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from math import inf

def max_binaire(a,b):
    return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de type int.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = -inf
    for x in tab:
        m = max_binaire(m,x)
    return m


#  ****  test  ***



# rappel: randint(a,b) tire un entier p au hasard avec a <= p <= b.
from random import randint

# on crée une liste en tirant sa longueur et ses éléments au hasard:
L = [ randint(-20,20) for _ in range(randint(1,5))]

# on calcule le maximum avec notre fonction:
monMax =  max_tableau(L)
# on utilise la fonction prédéfinie de python pour vérifier que 
# notre fonction renvoie bien le maximum:
print("Liste générée au hasard: ", monMax == max(L))
Après quelques recherches sur la toile et/ou quelques essais, on sait que -inf < a vaut toujours True pour n'importe quel nombre a. inf représente +\infty et -inf représente -\infty.

Dès la première instruction m = max_binaire(m,x), m est donc remplacé par tab[0] et la suite du déroulement est identique à ce qu'il se passait dans le code avec initialisation de m à tab[0].

Question 2☘

Le choix de l'initialisation m = tab[0] est plus général que le choix m = -inf fait par Max. Voyez-vous en quoi?

Une réponse

Le choix de Max m = -inf n'est pas nécessairement inintéressant, il a l'avantage de s'appliquer même a une liste vide, mais à condition que la liste soit une liste de nombres.

Si l'on cherche en effet à utiliser cette fonction à des types autres que float, à des chaînes de caractères par exemple, on déclenchera une erreur puisqu'on cherche à comparer une chaîne de caractères avec un objet de type float.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>> 'chat' < 'chien'
True
>>> 'chat' < 'animal'
False
>>> 12 < 'chat'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'int' and 'str'
>>> -inf < 'chat'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'float' and 'str'

Avec le choix m = tab[0], on peut renvoyer le maximum d'une liste de mots (au sens de l'ordre des mots dans le dictionnaire, voir cette page pour plus de détails).