Aller au contenu

Sujet n°27

Sujet original

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

Exercice n°1

Écrire une fonction indice_du_min() qui prend en paramètre un tableau, non vide, de nombres non triés tab, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de listes Python.

Commentaires

Dans le sujet original, la fonction se nomme recherche_min(), ce qui pourrait faire croire que c'est la valeur du minimum qui est recherchée, plutôt que la valeur de son indice.

Exemples

>>> indice_du_min([5])
0

>>> indice_du_min([2, 4, 1])
2

>>> indice_du_min([5, 3, 1, 1, 4])
2
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def indice_du_min(tab):
    """
    tab - list, tableau non vide d'entiers
    Sortie: int, indice de la première occurrence du minimum dans tab
    """
    assert isinstance(tab, list), "Le paramètre doit être un tableau"
    assert tab != [], "Tableau vide !"
    indice_du_min = 0
    for i in range(len(tab)):
        if tab[i] < tab[indice_du_min]:
            indice_du_min = i
    return indice_du_min

if __name__ == '__main__':
    # Exemples de l'énoncé
    print(indice_du_min([5]) == 0)
    print(indice_du_min([2, 4, 1]) == 2)
    print(indice_du_min([5, 3, 1, 1, 4]) == 2)

    # Exemples supplémentaires
    print(indice_du_min([12, 23, 17, 10, 20, 19]) == 3)
    print(indice_du_min([9, 9, 9, 9, 9]) == 0)

Exercice n°2

On considère la fonction separe qui prend en argument un tableau tab dont les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de tableau et les 1 à la suite.

1
2
3
4
5
6
7
8
def separe(tab):
    result = []
    for ... in ...:
        if elt == 0:
            ...
        else:
            ...
    ...

Compléter le code de cette fonction.

Commentaires sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

Dans le code original, on raisonne par effet de bord tout en renvoyant le tableau d'origine, ce qui peut conduire à des comportements indésirables.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def separe(tab):
    gauche = 0 
    droite = ... 
    while gauche < droite: 
        if tab[gauche] == 0: 
            gauche = ... 
        else: 
            tab[gauche], tab[droite] = ... 
            droite = ... 
    return tab 

Le code modifié propose plutôt un parcours de tableau construisant un nouveau tableau qui, lui, sera renvoyé.

Exemples

>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]

>>> separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1])
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
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
24
def separe(tab):
    result = []
    for elt in tab:
        if elt == 0:
            result = [0]+result
        else:
            result.append(1)
    return result


if __name__ == '__main__':
    # Exemples de l'énoncé
    tab = [1, 0, 1, 0, 1, 0, 1, 0]
    print(separe(tab) == [0, 0, 0, 0, 1, 1, 1, 1])

    tab = [1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
    print(separe(tab) == [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1])

    # Exemples supplémentaires
    tab = [0, 1]
    print(separe(tab) == [0, 1])

    tab = [1, 0]
    print(separe(tab) == [0, 1])
Une solution du code original
 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
def separe(tab):
    gauche = 0
    droite = len(tab)-1
    while gauche < droite :
        if tab[gauche] == 0 :
            gauche = gauche+1
        else :
            tab[gauche], tab[droite] = tab[droite], tab[gauche]
            droite = droite-1
    return tab


if __name__ == '__main__':
    # Exemples de l'énoncé
    tab = [1, 0, 1, 0, 1, 0, 1, 0]
    print(separe(tab) == [0, 0, 0, 0, 1, 1, 1, 1])

    tab = [1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
    print(separe(tab) == [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1])

    # Exemples supplémentaires
    tab = [0, 1]
    print(separe(tab) == [0, 1])

    tab = [1, 0]
    print(separe(tab) == [0, 1])