Aller au contenu

Sujet n°28

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

Écrire une fonction qui prend en paramètre un tableau d'entiers non vide et qui renvoie la moyenne de ces entiers. La fonction est spécifiée ci-après et doit passer les assertions fournies.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def moyenne(tab):
    '''
    moyenne(list) -> float
    Entrée : un tableau non vide d'entiers
    Sortie : nombre de type float
    Correspondant à la moyenne des valeurs présentes dans le tableau
    '''


assert moyenne([1]) == 1.0
assert moyenne([1, 2, 3, 4, 5, 6, 7]) == 4.0
assert moyenne([1, 2]) == 1.5
Commentaires sur le code original
  1. Les assertions sont en dehors de la fonction : elles correspondent à des tests de la fonction comme vous pourriez les faire à l'aide du module doctest par exemple. Cette façon de faire n'est pas conventionnelle...

  2. La fonction moyenne() renvoie un flottant.
    a. D'une part, effectuer des tests d'égalités sur des flottants ne semble pas avisé (cf. le cours de 1ère NSI sur ce type de données).
    b. D'autre part, les deux premiers tests concernaient une égalité entre un flottant et un entier (cf. code original) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def moyenne(tab):
    '''
    moyenne(list) -> float
    Entrée : un tableau non vide d'entiers
    Sortie : nombre de type float
    Correspondant à la moyenne des valeurs présentes dans le tableau
    '''


assert moyenne([1]) == 1
assert moyenne([1, 2, 3, 4, 5, 6, 7]) == 4
assert moyenne([1, 2]) == 1.5
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def moyenne (tab):
    '''
    moyenne(list) -> float
    Entrée : un tableau non vide d'entiers
    Sortie : nombre de type float
    Correspondant à la moyenne des valeurs présentes dans le tableau
    '''
    somme = 0
    for elt in tab:
        somme = somme + elt
    return somme/len(tab)


if __name__ == '__main__':
    # Exemples de l'énoncé
    assert moyenne([1]) == 1.0
    assert moyenne([1, 2, 3, 4, 5, 6, 7]) == 4.0
    assert moyenne([1, 2]) == 1.5


    # Exemples supplémentaires
    print(moyenne([1, 2, 3]) == 2.0)
    print(moyenne([1, 2, 3, 4]) == 2.5)

Exercice n°2

Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant.

L'algorithme traite le cas du tableau vide et il est écrit pour que la recherche dichotomique ne se fasse que dans le cas où la valeur est comprise entre les valeurs extrêmes du tableau.

On distingue les trois cas qui renvoient False en renvoyant (False, 1), (False, 2) et (False, 3).

Compléter l'algorithme de dichotomie donné ci-après.

 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 dichotomie(tab, x):
    """
        tab : tableau trié dans l’ordre croissant
        x : nombre entier
        La fonction renvoie True si tab contient x et False sinon
    """
    # cas du tableau vide
    if ...:
        return False, 1

    # cas où x n'est pas compris entre les valeurs extrêmes
    if (x < tab[0]) or ...:
        return False, 2

    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = m + 1
        else:
            fin = ...
    return ...
Commentaire sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. L'algorithme de recherche par dichotomie est un grand classique étudié en classe de 1ère. Il est indispensable de le travailler et de savoir le programmer.

Exemples

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
(False, 3)

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 1)
(False, 2)

>>> dichotomie([], 28)
(False, 1)
Une réponse

Dans cet exercice, il faut reprogrammer un algorithme usuel, à savoir.

 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
def dichotomie(tab, x):
    """
    tab : tableau trié dans l’ordre croissant
    x : nombre entier
    La fonction renvoie True si tab contient x et False sinon
    """
    # cas du tableau vide
    if len(tab) == 0:
        return False, 1

    # cas où x n'est pas compris entre les valeurs extrêmes
    if (x < tab[0]) or (x > tab[len(tab)-1]):
        return False, 2

    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut+fin)//2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m + 1
        else:
            fin = m - 1
    return False, 3



if __name__ == '__main__':
    # Exemples de l'énoncé
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28) == True)
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27) == (False, 3))
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 1) == (False, 2))
    print(dichotomie([], 28) == (False, 1))

    # Exemples supplémentaires
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 15) == True)
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 33) == True)
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 14) == (False, 2))
    print(dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 34) == (False, 2))