NSI 2026

# Littéral direct
a = [1, 2, 3]

# Répétition : crée n fois le même élément
b = [0] * 5          # → [0, 0, 0, 0, 0]

# range → list
c = list(range(1, 6))  # → [1, 2, 3, 4, 5]

# Compréhension : [expression for var in itérable if condition]
carres = [x**2 for x in range(6)]      # [0,1,4,9,16,25]
pairs  = [x for x in range(10) if x%2==0] # [0,2,4,6,8]

# Matrice 3×3 — TOUJOURS utiliser compréhension !
mat = [[0]*3 for _ in range(3)]  # ← CORRECT
# mat = [[0]*3] * 3            ← FAUX : 3 références au même tableau !

t = [10, 20, 30, 40, 50]
#     0    1    2    3    4   ← positifs
#    -5   -4   -3   -2   -1  ← négatifs
t[0]      # → 10
t[-1]     # → 50  (dernier)
t[1:3]   # → [20, 30]  (1 inclus, 3 exclus)
t[::-1]  # → [50, 40, 30, 20, 10]  (inversé)
t[1:4:2] # → [20, 40]  (pas de 2)

a = [3, 1, 4, 1, 5]
a.append(9)      # O(1) — ajoute en fin
a.insert(2, 7)  # O(n) ! — insère à pos 2
a.pop()         # O(1) — retire le dernier
a.pop(0)        # O(n) ! — retire le premier
a.remove(1)    # O(n) — retire 1ère occurrence de 1
len(a)          # O(1)
1 in a          # O(n) — parcours linéaire
a.sort()            # O(n log n) — en place
b = sorted(a)       # O(n log n) — nouvelle liste
a.extend([10,20])  # O(k) — ajoute k éléments

# ❌ MAUVAIS — b et a = même objet
a = [1, 2, 3]
b = a
b.append(4)
print(a)  # → [1, 2, 3, 4]  ← a a changé !

# ✅ Copie superficielle (liste 1D)
b = a[:]         # ou list(a) ou a.copy()

# ✅ Copie profonde (liste 2D)
import copy
m2 = copy.deepcopy(mat)

# ❌ NE PAS MODIFIER EN ITÉRANT — résultat imprévisible !
a = [1, 2, 3, 4]
for x in a:
    if x%2==0: a.remove(x)  # FAUX

# ✅ CORRECT — reconstruire une nouvelle liste
a = [x for x in a if x%2!=0]  # [1, 3]

t = (1, 2, 3)
t[0]   # → 1  (lecture OK)
# t[0] = 99  → TypeError !

# Déballage
x, y, z = (10, 20, 30)
a, *reste = (1, 2, 3, 4)  # a=1, reste=[2,3,4]

# Retourner plusieurs valeurs
def min_max(lst): return min(lst), max(lst)
mini, maxi = min_max([3,1,4,1,5])

# Clé de dictionnaire (impossible avec liste)
d = {(0,0): "origine"}  # ✓

d = {"nom": "Alice", "age": 17}

# Accès sécurisé
d["nom"]                  # → "Alice"  | O(1)
d["inconnu"]              # → KeyError !
d.get("inconnu", "?")   # → "?"  (jamais d'erreur)

# Modification
d["score"] = 100   # ajoute si absent, modifie sinon
del d["age"]        # supprime
v = d.pop("nom")    # supprime et renvoie

# Appartenance — teste les CLÉS
"score" in d         # O(1)
100 in d.values()    # O(n) !

# Itération
for cle in d: ...
for cle, val in d.items(): ...
for val in d.values(): ...

# Pattern classique
freq = {}
for c in "concours":
    freq[c] = freq.get(c, 0) + 1

# Ou avec collections.Counter
from collections import Counter
freq = Counter("concours")
freq.most_common(3)  # 3 plus fréquents

# Grouper des éléments
mots = ["chat", "chien", "dauphin"]
groupes = {}
for m in mots:
    groupes.setdefault(m[0], []).append(m)
# {'c': ['chat','chien'], 'd': ['dauphin']}

cache = {}
def fib(n):
    if n in cache: return cache[n]  # déjà calculé → O(1)
    if n <= 1: return n
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]
# O(n) appels au lieu de O(2^n) sans cache

# Avec décorateur @lru_cache (plus simple)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib2(n):
    if n <= 1: return n
    return fib2(n-1) + fib2(n-2)

class Pile:
    """Pile LIFO — Last In, First Out."""
    def __init__(self):       # constructeur
        self._data = []        # attribut "privé" (convention _)
        self._n = 0

    def push(self, x):
        self._data.append(x); self._n += 1

    def pop(self):
        if self.est_vide():
            raise IndexError("Pile vide")
        self._n -= 1
        return self._data.pop()

    def peek(self):
        return self._data[-1] if not self.est_vide() else None

    def est_vide(self): return self._n == 0
    def __len__(self): return self._n       # permet len(p)
    def __repr__(self): return f"Pile({self._data})"

p = Pile()
p.push(10); p.push(20)
print(p.pop())  # → 20

class Animal:
    def __init__(self, nom): self.nom = nom
    def parler(self): return "..."
    def __repr__(self): return f"{self.nom}: {self.parler()}"

class Chien(Animal):          # hérite de Animal
    def parler(self): return "Woof"  # surcharge

class Chat(Animal):
    def __init__(self, nom, couleur):
        super().__init__(nom)    # appel parent
        self.couleur = couleur
    def parler(self): return "Miaou"

print(Chien("Rex"))   # Rex: Woof
print(Chat("Mimi","roux"))  # Mimi: Miaou

class Sommet:
    def __init__(self, x, y, z):
        self.x, self.y, self.z = x, y, z
        self.darete = None   # rempli plus tard

class Face:
    def __init__(self): self.darete = None

class DArete:
    def __init__(self, source, but, face):
        self.source = source; self.but = but; self.face = face
        self.suivant = None   # prochaine DA autour de face
        self.miroir  = None   # DA opposée (sens inverse)
        if face.darete is None: face.darete = self
        if source.darete is None: source.darete = self

# Tour d'une face = liste chaînée circulaire
def tour_face(face):
    res = []; da = face.darete
    while True:
        res.append(da.source); da = da.suivant
        if da is face.darete: break
    return res

# Factorielle — variant : n (décroît vers 0)
def fact(n):
    if n == 0: return 1        # cas de base
    return n * fact(n - 1)    # n décroît strictement
# fact(4) = 4×fact(3) = 4×3×2×1×1 = 24

# Dichotomie récursive — variant : haut-bas
def dicho(t, x, bas=0, haut=None):
    if haut is None: haut = len(t) - 1
    if bas > haut: return -1      # absent
    mid = (bas + haut) // 2
    if t[mid] == x: return mid
    if t[mid] < x: return dicho(t, x, mid+1, haut)
    return dicho(t, x, bas, mid-1)
    # Variant: haut-bas décroît strictement à chaque appel

# Hanoi — 2^n - 1 déplacements
def hanoi(n, A, B, C):
    if n == 0: return
    hanoi(n-1, A, C, B)
    print(f"Disque {n}: {A} → {C}")
    hanoi(n-1, B, A, C)

# enumerate : indice + valeur en même temps
for i, v in enumerate(["a","b","c"], start=1):
    print(i, v)  # 1 a, 2 b, 3 c

# zip : plusieurs listes en parallèle
for n, s in zip(["Alice","Bob"], [18,14]):
    print(f"{n}: {s}/20")

# any / all : conditions globales
t = [2, 4, 6, 8]
all(x%2==0 for x in t)  # → True
any(x > 5 for x in t)   # → True

# sorted avec clé personnalisée
mots = ["banane", "kiwi", "ananas"]
sorted(mots, key=len)           # par longueur
sorted(mots, key=lambda m: m[-1]) # par dernière lettre

# next() avec valeur par défaut — très utile CGL 2025
u = next((cl[0] for cl in F if len(cl)==1), None)
# Renvoie le 1er élément vérifiant la condition, ou None

def fib_gen():
    a, b = 0, 1
    while True:
        yield a        # suspend et retourne
        a, b = b, a+b

gen = fib_gen()
print(next(gen), next(gen), next(gen))  # 0 1 1

# Expression génératrice (lazy, économise mémoire)
total = sum(x**2 for x in range(1000000))

# None = indéterminé. Nécessite une logique spéciale.
def val_clause(clause, V):
    res = False
    for lit in clause:
        x = abs(lit)
        v = V[x]
        if v is True  and lit > 0: return True
        if v is False and lit < 0: return True
        if v is None: res = None   # indéterminé
    return res  # False ou None

# Table: None∨True=True, None∨False=None
#        None∧False=False, None∧True=None

def tri_insertion(t):
    for i in range(1, len(t)):
        cle = t[i]; j = i-1
        while j >= 0 and t[j] > cle:
            t[j+1] = t[j]; j -= 1
        t[j+1] = cle
    return t

def fusionner(g, d):
    res=[]; i=j=0
    while i<len(g) and j<len(d):
        if g[i]<=d[j]: res.append(g[i]); i+=1
        else: res.append(d[j]); j+=1
    return res+g[i:]+d[j:]

def tri_fusion(t):
    if len(t)<=1: return t
    m=len(t)//2
    return fusionner(tri_fusion(t[:m]),tri_fusion(t[m:]))

def dicho(t, x):
    bas, haut = 0, len(t)-1
    while bas <= haut:
        mid = (bas+haut)//2
        if   t[mid]==x: return mid
        elif t[mid]1
        else:           haut = mid-1
    return -1
# Variant: haut-bas ≥ 0, décroît strictement → terminaison

from collections import deque
import heapq

def bfs(g, src):
    dist={src:0}; q=deque([src])
    while q:
        s=q.popleft()
        for v in g.get(s,[]):
            if v not in dist: dist[v]=dist[s]+1; q.append(v)
    return dist

def dfs(g, src, vus=None):
    if vus is None: vus=set()
    vus.add(src)
    for v in g.get(src,[]): 
        if v not in vus: dfs(g,v,vus)
    return vus

# Dijkstra — plus court chemin pondéré
def dijkstra(g, src):
    dist={src:0}; tas=[(0,src)]
    while tas:
        d,s=heapq.heappop(tas)
        if d>dist.get(s,float('inf')): continue
        for v,w in g.get(s,[]):
            nd=d+w
            if ndget(v,float('inf')):
                dist[v]=nd; heapq.heappush(tas,(nd,v))
    return dist

def n_reines(n):
    solutions=[]
    def placer(ligne, cols):
        if ligne==n: solutions.append(cols[:]); return
        for col in range(n):
            ok=all(c!=col and abs(c-col)!=abs(r-ligne)
                     for r,c in enumerate(cols))
            if ok:
                cols.append(col)       # choisir
                placer(ligne+1, cols)  # explorer
                cols.pop()             # défaire
    placer(0, []); return len(solutions)
print(n_reines(8))  # → 92

# Solveur SAT avec clauses unitaires (CGL 2025)
def simplifie(F,lit):
    return [[l for l in cl if l!=-lit] for cl in F if lit not in cl]
def sat(F,sol=[]):
    if F==[]: return sol
    if [] in F: return None
    lit=F[0][0]
    r=sat(simplifie(F,lit),sol+[lit])
    return r if r else sat(simplifie(F,-lit),sol+[-lit])

def simplifie(F, lit):
    return [[l for l in cl if l!=-lit] for cl in F if lit not in cl]

def clauses_unit(F):
    forcés=[]; vus=set()
    while True:
        u=next((cl[0] for cl in F if len(cl)==1 and cl[0] not in vus),None)
        if u is None: break
        forcés.append(u); vus.add(u); F=simplifie(F,u)
    return F, forcés

def sat(F, sol=[]):
    F,f=clauses_unit(F); sol=sol+f
    if F==[]: return sol
    if [] in F: return None
    lit=F[0][0]
    r=sat(simplifie(F,lit),sol+[lit])
    return r if r is not None else sat(simplifie(F,-lit),sol+[-lit])

print(sat([[1,2],[-1,3],[-2,-3]]))  # [1, 3, -2]
print(sat([[1],[-1]]))                # None (insatisfaisable)

def dichotomie(n):
    """Œufs illimités — O(log n) lâchers. Invariant: critique ∈ [bas,haut]"""
    bas, haut = 1, n
    while bas < haut:
        mid=(bas+haut)//2
        if lacher(mid): haut=mid   # critique ≤ mid
        else: bas=mid+1            # critique > mid
    return bas

from collections import deque

def gare_triage(m, entree):
    voies=[deque() for _ in range(m)]
    sortie=deque(); prochain=0
    for wagon in entree:
        placé=False
        for v in voies:
            if not v or v[-1]>wagon:
                v.append(wagon); placé=True; break
        if not placé: return False,[]
    n=sum(len(v) for v in voies)
    for _ in range(n):
        for v in voies:
            if v and v[0]==prochain:
                sortie.append(v.popleft()); prochain+=1; break
    return True, list(sortie)

ok, res=gare_triage(3,[3,1,4,0,2])
print(ok, res)  # True [0,1,2,3,4]