Aller au contenu

Sujet n°8

Sujet original

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

Exercice n°1

Écrire une fonction recherche() qui prend en paramètres elt un nombre entier et tab un tableau 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.

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
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
    """
    for i in range(len(tab)):
        if tab[i] == elt:
            return i
    return -1

if __name__ == '__main__':
    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)

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 insère la valeur a dans le tableau et renvoie le nouveau tableau. Les tableaux seront représentés sous la forme de listes python.

1
2
3
4
5
6
7
8
9
def insere(a, tab):
    lst = list(tab)     # lst contient les mêmes éléments que tab
    lst.append(a)
    i = ...
    while (i >= 0) and (a < ...) :
        lst[i+1] = ...
        lst[i] = a
        i = ...
    return lst
Commentaires sur le code original

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

  1. Une variable qui n'est désigné que par une lettre l (ici renommée en lst).
  2. En ligne 5, 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(10, [1, 2, 7, 12, 14, 25])
[1, 2, 7, 10, 12, 14, 25]
>>> insere(1, [2, 3, 4])
[1, 2, 3, 4]
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 insere(a, tab):
    # lst contient les mêmes éléments que tab
    lst = list(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__':
    tab = [1, 2, 4, 5]
    print(insere(3, tab))
    print(insere(3, tab) == [1, 2, 3, 4, 5])

    tab = [1, 2, 7, 12, 14, 25]
    print(insere(10, tab))
    print(insere(10, tab) == [1, 2, 7, 10, 12, 14, 25])

    tab = [2, 3, 4]
    print(insere(1, tab))
    print(insere(1, tab) == [1, 2, 3, 4])