Corrigé du DS 1 de T°NSI

Questions de cours

Pile ou File ?
1. C'est une file (les produits anciens partent en premier)
2. C'est une pile (la dernière voiture arrivée doit partir en premier)
3. C'est une file (les documents sont imprimés dans l'ordre d'arrivée)
On a implémenté une classe File de trois manières différentes :
- avec une liste python (inconvénient : le pop(0) pour défiler n'est pas efficace donc l'opération de défilage a une complexité \(O(n)\) linéaire en la taille de la file \(n\))
- avec deux piles à l'intérieur (le défilage est efficace en moyenne, mais il peut arriver qu'une opération de défilage nécessite de transvaser toute la première pile vers la deuxième donc \(O(n)\) dans le pire cas)
- avec une liste chaînée (efficace en temps constant \(O(1)\) dans tous les cas)

Exercice 1 : Mélange d'une liste

Ce code écrase valeurs[j] à la première ligne et ne permet donc pas de mettre cette valeur dans valeurs[i] à la seconde.

Solution avec une variable intermédiaire :

def echange(valeurs, i, j):
    temporaire = valeurs[j]
    valeurs[j] = valeurs[i]
    valeurs[i] = temporaire

Solution avec la double assignation de python :

def echange(valeurs, i, j):
    valeurs[j], valeurs[i] = valeurs[i], valeurs[j]

Les valeurs possibles sont 0,1,9,10 (entiers entre 0 et 10 inclus)
a. La valeur du paramètre i diminue de 1 à chaque appel récursif. Or, quand cette valeur atteint 0 il n'y a plus d'appel récursif. Donc cette fonction va se terminer.

b. Il y a n-1 appels récursifs sans compter le premier, car ce premier appel se fait avec i valant n-1, donc les appels successifs se font avec i de n-2 jusque 0 soit n-1 valeurs en tout.

c. Il faut bien simuler le code, au brouillon en notant la valeur de chaque variable à chaque appel. Les valeurs qui sont aux indices i et j sont échangées à chaque fois.
- Premier affichage : [0, 1, 2, 3, 4] (au début)
- Deuxième affichage : [0, 1, 4, 3, 2] (i = 4 et j = 2)
- Troisième affichage : [0, 3, 4, 1, 2] (i = 3 et j = 1)
- Quatrième affichage : [0, 3, 4, 1, 2] (i = 2 et j = 2)
- Cinquième affichage : [3, 0, 4, 1, 2] (i = 1 et j = 0)
d.
```
def melange2(valeurs):
    i = len(valeurs)-1 # plus besoin d'avoir i en paramètre
    while i > 0:
        print(valeurs) # pas indispensable
        j = randint(0, i)
        echange(valeurs, i, j)
        i = i - 1
```

Exercice 2 : Labyrinthe en POO

python cellule = Cellule(True, False, True, True)
python for i in range(hauteur): ligne = [] for j in range(largeur): cellule = Cellule(True, True, True, True) ligne.append(cellule)
python cellule2.murs["S"] = False
python elif i1 == i2 and j1 - j2 == 1: cellule1.murs["O"] = False cellule2.murs["E"] = False

Attention au -1 dans les deux appels à range : sinon la valeur j + k + 1 sortirait du labyrinthe (on retire un mur entre une cellule et la suivante, donc il faut s'arrêter une cellule avant la dernière).

    if hauteur == 1:  # Cas de base
        for k in range(largeur - 1):
            self.creer_passage(i, j + k, i, j + k + 1)
    elif largeur == 1:  # Cas de base
        for k in range(hauteur - 1):
            self.creer_passage(i + k, j, i + k + 1, j)

On s'appelle récursivement sur chaque moitié en coupant :
- horizontalement si largeur <= hauteur avec le passage le plus à l'ouest.
- verticalement sinon avec le passage le plus au nord
Et si on arrive sur un labyrinthe de largeur ou hauteur 1, on ouvre tous les murs internes (cas de base précédent).