Sujet n°14

Sujet original

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

Exercice n°1

Écrire une fonction recherche() qui prend en paramètres un nombre entier elt et un tableau tab de nombres entiers, et qui renvoie l’indice de la première occurrence de elt dans tab si elt est dans tab et -1 sinon.

Ne pas oublier d’ajouter au corps de la fonction une documentation et une ou plusieurs assertions pour vérifier les pré-conditions.

Exemples

>>> recherche(1, [2, 3, 4])
-1

>>> recherche(1, [10, 12, 1, 56])
2

>>> recherche(50, [1, 50, 1])
1

>>> recherche(15, [8, 9, 10, 15])
3

>>> recherche(50, []) 
-1

>>> recherche(4, [2, 4, 4, 3, 4]) 
1

Une solution

def recherche(elt, tab):
    """
    elt - int
    tab - list, tableau d'entiers
    Sortie: int, indice de la première occurrence de elt dans tab
            Si elt n'est pas dans tab, renvoie -1
    """
    assert isinstance(elt, int), "Le premier paramètre doit être entier"
    assert isinstance(tab, list), "Le seconde paramètre doit être un tableau"
    for valeur in tab:
        assert isinstance(valeur, int), "Le tableau doit contenir des entiers"
    for i in range(len(tab)):
        if tab[i] == elt:
            return i
    return -1

if __name__ == '__main__':
    # Exemples de l'énoncé
    print(recherche(1, [2, 3, 4]) == -1)
    print(recherche(1, [10, 12, 1, 56]) == 2)
    print(recherche(50, [1, 50, 1]) == 1)
    print(recherche(15, [8, 9, 10, 15]) == 3)
    print(recherche(50, []) == -1)
    print(recherche(4, [2, 4, 4, 3, 4]) == 1)

    # Exemples supplémentaires
    print(recherche(5, [1, 2, 3, 4]) == -1)
    print(recherche(7, [7, 7, 7]) == 0)

Exercice n°2

On considère la fonction insere() ci-dessous qui prend en argument un entier a et un tableau tab d'entiers triés par ordre croissant. Cette fonction crée et renvoie un nouveau tableau à partir de celui fourni en paramètre en y insérant la valeur a de sorte que le tableau renvoyé soit encore trié par ordre croissant. Les tableaux seront représentés sous la forme de listes Python.

def insere(a, tab):
    """ Insère l'élément a (int) dans le tableau tab (list)
        trié par ordre croissant à sa place et renvoie le
        nouveau tableau. """
    l = list(tab) #l contient les memes elements que tab
    l.append(a)
    i = ...
    while a < ... and i >= 0: 
        l[i+1] = ...
        l[i] = a
        i = ...
    return l

Commentaires sur le code original

1. Pour télécharger l'original du fichier à compléter, cliquer ici, mais vous aurez des surprises.

2. Une variable qui n'est désigné que par une lettre l (il faudrait la renommer en lst).

3. En ligne 8, une boucle while qui teste la validité de l'indice après avoir fait appel à cet indice n'est clairement pas correct d'un point de vue algorithmique...

Compléter la fonction insere() ci-dessus.

Exemples

>>> insere(3, [1, 2, 4, 5])
[1, 2, 3, 4, 5] 
>>> insere(30, [1, 2, 7, 12, 14, 25]) 
[1, 2, 7, 12, 14, 25, 30]
>>> insere(1, [2, 3, 4])
[1, 2, 3, 4] 
>>> insere(1, []) 
[1]

Une solution

Dans cette solution, l est renommée en lst et les conditions de la boucle while ont été échangées.

def insere(a, tab):
    """ Insère l'élément a (int) dans le tableau tab (list)
        trié par ordre croissant à sa place et renvoie le
        nouveau tableau. """
    lst = list(tab) # lst contient les mêmes éléments que tab
    lst.append(a)
    i = len(lst)-2
    while i >= 0 and a < lst[i] :
        lst[i+1] = lst[i]
        lst[i] = a
        i = i-1
    return lst


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(insere(3, [1, 2, 4, 5]) == [1, 2, 3, 4, 5])
    print(insere(30, [1, 2, 7, 12, 14, 25]) == [1, 2, 7, 12, 14, 25, 30])
    print(insere(1, [2, 3, 4]) == [1, 2, 3, 4])
    print(insere(1, []) == [1])

    # Exemples supplémentaires
    print(insere(10, [1, 2, 7, 12, 14, 25]) == [1, 2, 7, 10, 12, 14, 25])
    print(insere(3, [1, 2, 7, 12, 14, 25]) == [1, 2, 3, 7, 12, 14, 25])