Home
About

Utilisation des listes

Cours/Algorithmie/Utilisation des listes

Tableaux et listes

Matrices

  • Utilité : à connaître car exercice classique réduction de complexité spatiale.
  • Difficulté : facile

Triangle de Pascal

Tri par monotonies

Utilisation des listes pour faire grossir des tableaux.

Étant donné un tableau $T$, une monotonie est une suite croissante maximale d'éléments consécutifs de $T$. Par exemple : si $T = [2,6, 1,3, 3, 5,2,6, 4,0, 1,8,9,1,3, 2,0,1,0]$, alors $[2,6]$, $[1,3,3,5]$, $[2,6]$, $[4]$, $[0, 1,8,9]$, $[1,3]$, $[2]$, $[0,1]$ et $[0]$ sont les monotonies de $T$.

Donnez un algorithme qui, étant donné un tableau $T$ construit une liste (de listes) $L$, chaque élément de $L$ étant une monotonie de $T$ (et vice versa). À partir de notre exemple, on obtient : $L = [[2,6], [1,3,3,5],[2,6], [4], [0, 1,8,9], [1,3], [2] ,[0,1], [0]]$.

Donnez un algorithme qui fusionne deux monotonies ; par exemple, à partir de $[2,6]$ et $[1,3,3,5]$, on obtient $[1,2,3,3,5,6]$ (ceci est aussi une question de cours).

Donnez un algorithme qui, étant donnée une liste $L$ de monotonies, les fusionne deux-à-deux (en en laissant éventuellement une ``toute seule" à la fin) et met le résultat dans une liste (de listes) $L'$. Par exemple, à partir de $L = [[2,6], [1,3,3,5],[2,6], [4], [0, 1,8,9], [1,3], [2] ,[0,1], [0]]$, on obtient $L' = [[1,2,3,3,5,6], [2,4,6],[0,1,1,3,8,9], [0,1,2], [0]]$.

En déduire un algorithme de tri. Donnez sa complexité dans le cas le meilleur et dans le cas le pire.

Cet algorithme est en fait une variante d'un algorithme vu en cours. Lequel ?

Piles

  • Utilité : les piles ça sert toujours. Ces exercices vous montrerons des cas classiques d'utilisation
  • Difficulté : dur

File avec pile

On reprend l'exercice sur la création d'une file avec 2 piles.

Montrer que la complexité amortie d'ajout et de suppression d'un élément dans la structure de file créée avec 2 pile est en $\mathcal{O}(1)$

corrigé

On procède comme pour le compteur, on associe une complexité amortie de +2 lorsque l'on empile dans P1 et de 0 lorsque l'on empile dans P2.

Parenthésage

Soit $C$ une expression arithmétique avec des parenthèses et des crochets. On cherche à savoir si le parenthésage est équilibré :

On ne vérifiera pas que l'expression est arithmétiquement correcte, c'est à dire que pour nous, [3 + + 3 (1 + 3)] sera Ok.

Montrer que l'on peut utiliser une pile pour savoir si un parenthésage est équilibré entre les () et les [].

corrigé

 
algorithme parenthèse(C):
    P ← une nouvelle pile de caractères
    pour chaque c de C:
        si c == "(" ou c == "[":
            P.empile(c)
        sinon si c == ")":
            si P.vide() ou P.dépile() ≠ "(":
                rendre Faux
        sinon si c == "]":
            si P.vide() ou P.dépile() ≠ "[":
                rendre Faux
    rendre Vrai

Calcul d'une expression avec deux piles

Soit $C$ une expression arithmétique avec uniquement des parenthèses, des + et des *. On suppose qu'elle est arithmétiquement correcte, comme (3 + 3 * (1 + 3))

Montrer que l'on peut utiliser deux piles (une pour les opérateurs et les parenthèses et l'autre pour les nombres) pour calculer $C$.

corrigé

Il faut faire attention au fait que * a une priorité supérieure à + : 3 + 4 * 3 = 15.

On lit l'expression de gauche à droite :

  1. si le caractère lu est un nombre on le place dans la pile P2
  2. sinon si le caractère lu est un opérateur O :
    1. on évalue l'expression comme on la fait avec la notation polonaise inversée :
      1. pop de P1 dans op
      2. pop de p2 dans y
      3. pop de p2 dans x
      4. x op y = z
      5. push de z dans P2
    2. jusqu'à ce que :
      1. P1 est vide ou
      2. l'opérateur O a une priorité supérieure à celle sur P1
    3. place O dans P1
  3. sinon si le caractère lu est une parenthèse ouvrante : on la place dans P1
  4. sinon si le caractère lu est une parenthèse fermante :
    1. on évalue l'expression jusqu'à trouver une parenthèse ouvrante
    2. on push le résultat dans P2

Si on a fini de lire l'expression on évalue le reste des deux piles.

à 9min13 https://www.youtube.com/watch?v=2vBVvQTTdXg

Liste chaînée

TBD dire base des algos récursifs. TBD donner le type récursif associé.

TBD reprendre exercices suppression/ head, tail , rendre éléments pair et impair/ retournements

Autre structures