Aller au contenu

TP - Algorithmes de référence☘

Dans le dossier [NSI], créez le dossier [G02_Algo_Tableaux].

Téléchargez le fichier « à trous » TPG02.11.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans ce dossier.

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest : 

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Partie 1 : Trancher un tableau☘

Définir la fonction trancher() qui prend en paramètres un tableau d'entiers tab et deux entiers i et j et qui renvoie le tableau constitués des éléments de tab[i] à tab[j].

1
2
3
4
5
6
7
8
def trancher(tab, i, j):
    """
    tab - list, tableau d'éléments
    i, j - int, entiers tels que 0 <= i <= j < len(tab)
    Sortie: list, tableau tab[i..j], c'est-à-dire [tab(i], tab[i+1], .., tab[j]]
    >>> trancher([2, 6, 3, 9, 4, 42], 1, 4)
    [6, 3, 9, 4]
    """

Il faudra que le programme lève l'erreur suivante :

>>> trancher([2, 6, 3, 9, 4, 42], 4, 1)
AssertionError: Mauvaise plage d'entiers

Partie 2 : Recherche de l’indice du maximum☘

  1. Définir la fonction premier_indice_du_maxi() qui prend en paramètre un tableau d'entiers tab et qui renvoie le premier indice auquel se trouve le plus grand élément du tableau.

    1
2
3
4
5
6
7
8
9
    def premier_indice_du_maxi(tab):
    """
    tab – list, tableau non vide d'entiers
    Sortie: int – le premier indice du plus grand élément de tab
    >>> premier_indice_du_maxi([4, 6, 7, 4, 9, 4])
    4
    >>> premier_indice_du_maxi([4, 9, 7, 4, 9, 4, 2])
    1
    """
    Il faudra que le programme lève l'erreur suivante :

    >>> premier_indice_du_maxi([])
AssertionError: Le tableau est vide
    Une piste

    On considère que le premier élément du tableau est le maximum potentiel. On met sa valeur en mémoire ainsi que la valeur de son indice.
    Ensuite, on compare chacun des autres éléments du tableau avec le maximum potentiel. Lorsque l'élément est plus grand que le maximum potentiel, il devient le maximum potentiel et on met à jour la valeur de l'indice du maximum.
    Enfin, on renvoie l'indice du maximum.

  2. Définir la fonction dernier_indice_du_maxi() qui prend en paramètre un tableau d'entiers tab et qui renvoie le dernier indice auquel se trouve le plus grand élément du tableau.

    1
2
3
4
5
6
7
8
9
    def dernier_indice_du_maxi(tab):
    """
    tab – list, tableau non vide d'entiers
    Sortie: int – le dernier indice du plus grand élément de tab
    >>> dernier_indice_du_maxi([4, 9, 7, 4, 6, 4])
    1
    >>> dernier_indice_du_maxi([4, 9, 7, 4, 9, 4, 2])
    4
    """
    Il faudra que le programme lève la même erreur que la fonction précédente.

Partie 3 : Échanger les valeurs de deux éléments☘

Définir la fonction echange() qui prend en paramètre un tableau tab et deux entiers i et j puis qui échange les valeurs des éléments tab[i] et tab[j] (fonction à effet de bord - rappels sur la portée des variables).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def echange(tab, i, j):
    """
    tab – list, tableau non vide d'entiers
    i, j - int, entiers tels que 0 <= i < len(tab) et 0 <= j < len(tab)
    Sortie: None – les valeurs des éléments tab[i] et tab[j] ont été échangées
            (fonction à effet de bord, ne renvoie rien)
    >>> tab = [4, 6, 7, 4, 9, 4]
    >>> echange(tab, 1, 5)
    >>> tab
    [4, 4, 7, 4, 9, 6]
    """

Une contrainte

On vérifie par assertion que i et j sont bien compris entre 0 et len(tab)-1.

Partie 4 : Décaler les éléments d’un tableau☘

  1. La fonction decale_gauche() qui prend en argument un tableau et qui modifie ce tableau en décalant chacun de ses éléments d'un rang à gauche, le premier devenant le dernier.
    Cette fonction est à « effet de bord », c'est-à-dire qu'elle ne renvoie pas de valeur mais modifie le tableau passé en paramètre.

    Complétez le code de cette fonction en respectant ses spécifications.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def decale_gauche(tab):
    """
    tab - list, tableau d'éléments        
    Sortie : None - tab[1] prend la place de tab[0], tab[2] prend la place de tab[1], ...,
             tab[0] prend la place de tab[len(tab)-1]
             (fonction à effet de bord, ne renvoie rien)
    >>> tab = [3, 1, 7, 4]
    >>> decale_gauche(tab)
    >>> tab
    [1, 7, 4, 3]
    """
    Il faudra que le programme lève l'erreur suivante :

    >>> decale_gauche([])
AssertionError: Le tableau est vide
    Une piste

    On met en mémoire le premier élément du tableau puis on « remplace » chaque élément par la valeur de son suivant jusqu'à l'avant-dernier.
    On remplace ensuite le dernier élément par la valeur mise en mémoire.

  2. Programmer sur le même modèle la fonction decale_droite() qui prend en argument un tableau et qui modifie ce tableau en décalant chacun de ses éléments d'un rang à droite, le dernier devenant le premier.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def decale_droite(tab):
    """
    tab - list, tableau non vide d'éléments        
    Sortie : None - tab[0] prend la place de tab[1], tab[1] prend la place de tab[2], ...,
             tab[len(tab)-1] prend la place de tab[0]
             (fonction à effet de bord, ne renvoie rien)
    >>> tab = [3, 1, 7, 4]
    >>> decale_droite(tab)
    >>> tab
    [4, 3, 1, 7]
    """

Partie 5 : Un tableau est-il trié ?☘

La fonction est_trie() prend en argument un tableau d'éléments comparables. Cette fonction doit renvoyer True lorsque tous les éléments de ce tableau sont en ordre croissant, c'est-à-dire rangés du plus petit au plus grand.
Compléter le code de cette fonction.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def est_trie(tab):
    """
    tab - list, tableau d'éléments comparables    
    Sortie: bool - True si tab est trié en ordre croissant, False sinon.
    >>> est_trie([2, 6, 8, 9])
    True
    >>> est_trie([])
    True
    >>> est_trie([2, 3, 4, 1])
    False
    >>> est_trie(['a', 'b', 'g', 't'])
    True
    """
Une indication

Il suffit de visiter chaque élément de la liste de l'indice 0 à l'indice le plus grand en vérifiant, pour chaque élément, qu'il est plus petit que celui qui le suit.