Structures de données

On considère la classe Maillon définie dans le cours. Écrire une fonction taille(maillon) qui renvoie le nombre d'éléments d'une liste chaînée (0 si elle est vide, c'est-à-dire si maillon vaut None).

Exercice tiré du sujet zéro 0.A du bac NSI (2024), sur les listes, dictionnaires et la correction automatisée de QCM.

corr est une liste de 20 bonnes réponses (entiers 1 à 5) ; cop une copie candidate de même structure.

1. Écrire corrige(cop, corr), qui renvoie la liste des booléens (bonne/mauvaise réponse question par question).

2. Écrire note(cop, corr), qui renvoie directement le nombre de bonnes réponses, sans construire de liste intermédiaire.

Un paquet de copies est {nom_candidat: liste_reponses}.

3. Écrire notes_paquet(p, corr), qui renvoie {nom_candidat: note} (en réutilisant note).

4. Peut-on utiliser une liste [nom, prenom] comme clé de dictionnaire plutôt qu'un couple (nom, prenom) ? Justifier.

5. Proposer une autre solution pour distinguer des candidats homonymes en tenant compte de la sensibilité des données.

On donne enigme(notes), qui maintient trois variables a, b, c (les meilleures notes trouvées jusqu'ici) et un dictionnaire d recevant les candidats moins bien classés.

6. Calculer enigme sur {Tom:6, Lambert:4, Carl:2, Kurt:4, Ayet:3} (dans cet ordre d'insertion).

7. En déduire ce que calcule enigme en général.

8. Que renvoie enigme avec strictement moins de 3 candidats ?

9. En utilisant enigme, écrire classement(notes) qui renvoie tous les (nom, note) triés par notes décroissantes.

10-12. Pour un QCM où une seule réponse fausse invalide toutes les suivantes (liste de booléens [True,...,True,False,...,False]), on dispose de renote_express (linéaire) qu'il faut réécrire par dichotomie en renote_express2. Compléter cette version, donner les coûts en temps des deux versions, et expliquer comment l'adapter pour calculer directement une note sans construire de liste de booléens.

Exercice tiré du bac NSI 2022 (Asie/Pacifique, Jour 2), sur le « jeu de la vie » (grille modélisée par une liste de listes).

Grille 8×8, cellule vivante=1, morte=0, 8 voisines. Règles : une cellule morte avec exactement 3 voisines vivantes naît ; une cellule vivante avec 2 ou 3 voisines vivantes survit, sinon meurt.

1. Entre les deux scripts suivants pour initialiser un tableau de 0, lequel est correct et pourquoi ?

# Choix 1
ligne = [0,0,0,0,0,0,0,0]
jeu = []
for i in range(8):
    jeu.append(ligne)

# Choix 2
jeu = []
for i in range(8):
    ligne = [0,0,0,0,0,0,0,0]
    jeu.append(ligne)

Donner l'instruction plaçant une cellule vivante en jeu[5][2].

2. Écrire remplissage(n, jeu), plaçant aléatoirement n cellules vivantes dans jeu. Quelles préconditions sur n ?

3. Compléter nombre_de_vivants(i, j, jeu), qui compte les voisines vivantes de jeu[i][j] en restant dans les bornes de la grille.

4. En utilisant nombre_de_vivants, écrire transfo_cellule(i, j, jeu), renvoyant le nouvel état de jeu[i][j].

Exercice tiré du bac NSI Centres étrangers 2021 (Jour 1), sur les dictionnaires Python (vélos en libre-service).

flotte = {
    12: {"type": "electrique", "etat": 1, "station": "Prefecture"},
    80: {"type": "classique", "etat": 0, "station": "Saint-Leu"},
    45: {"type": "classique", "etat": 1, "station": "Baraban"},
    41: {"type": "classique", "etat": -1, "station": "Citadelle"},
    26: {"type": "classique", "etat": 1, "station": "Coliseum"},
    28: {"type": "electrique", "etat": 0, "station": "Coliseum"},
    74: {"type": "electrique", "etat": 1, "station": "Jacobins"},
    13: {"type": "classique", "etat": 0, "station": "Citadelle"},
    83: {"type": "classique", "etat": -1, "station": "Saint-Leu"},
    22: {"type": "electrique", "etat": -1, "station": "Joffre"},
}

("etat" : 1=disponible, 0=en déplacement, -1=en panne.)

1.a. Que renvoie flotte[26] ? 1.b. Que renvoie flotte[80]["etat"] ? 1.c. Que renvoie flotte[99]["etat"] ?

2.

def proposition(choix):
    for v in flotte:
        if flotte[v]["type"] == choix and flotte[v]["etat"] == 1:
            return flotte[v]["station"]

2.a. Valeurs possibles de choix ? 2.b. Que renvoie la fonction pour une valeur valide ?

3.a. Script affichant les identifiants des vélos disponibles à "Citadelle". 3.b. Script affichant identifiant et station des vélos électriques non en panne.

4.

stations = {
    'Prefecture': (49.8905, 2.2967),
    'Saint-Leu': (49.8982, 2.3017),
    'Coliseum': (49.8942, 2.2874),
    'Jacobins': (49.8912, 2.3016),
}

Avec distance(p1, p2) (mètres), écrire une fonction qui, pour chaque station à moins de 800 m de l'utilisateur, affiche son nom, la distance, et les vélos disponibles (station omise si aucun vélo disponible).

D'après une fiche d'exercices de NSI Terminale.

On reprend la classe Maillon du cours :

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

1. Écrire une classe ListeChainee, dont l'unique attribut tete désigne le premier maillon (None pour une liste vide), avec les méthodes ajouter_tete(v), ajouter_queue(v), supprimer(v) (qui retire la première occurrence de v, si elle existe) et __str__ (qui renvoie par exemple '2 -> 4 -> None'). Quel est le coût de chaque méthode ?
2. Implémenter le type abstrait pile par une classe Pile utilisant des maillons, avec les méthodes est_vide, empiler et depiler. Où faut-il placer le sommet ?
3. Implémenter le type abstrait file par une classe File utilisant des maillons, avec est_vide, enfiler et defiler, de sorte que enfiler et defiler se fassent en temps constant.

La notation polonaise inverse (RPN) écrit les opérateurs après leurs opérandes : par exemple 8 3 + 5 * représente $(8+3)\times 5$. On représente une telle expression par une liste, comme [8, 3, '+', 5, '*']. Pour l'évaluer avec une pile : pour chaque élément de la liste, si c'est un nombre on l'empile ; si c'est un opérateur, on dépile deux opérandes, on effectue l'opération, et on empile le résultat.

Écrire une fonction calcule(expression) qui renvoie la valeur d'une expression en RPN (les opérateurs possibles sont '+', '-', '*', '/'). Vérifier que calcule([8, 3, '+', 5, '*']) renvoie bien 55.

Exercice tiré du sujet zéro officiel du bac NSI (2021), sur la structure de pile (LIFO).

On munit la structure Pile de quatre primitives : creer_pile_vide(), est_vide(pile), empiler(pile, element), depiler(pile) (renvoie et retire le sommet).

1. La pile P contient, du sommet vers le fond : 4, 2, 5, 8. Que contient Q après :

Q = creer_pile_vide()
while not est_vide(P):
    empiler(Q, depiler(P))

2. Écrire hauteur_pile(P), qui renvoie le nombre d'éléments de P en la restituant dans son état initial. Écrire max_pile(P, i), qui renvoie la position (sommet = 1) du plus grand élément parmi les i derniers empilés, sans modifier durablement P.

3. Écrire retourner(P, j), qui inverse l'ordre des j derniers éléments empilés de P (à l'aide de deux piles auxiliaires).

4. En réutilisant les fonctions précédentes, écrire tri_crepes(P) qui trie P (plus grande valeur en bas) par la méthode : chercher le maximum non trié, le retourner en haut, puis retourner tout le paquet non trié pour l'envoyer à sa place. Exemple : 7, 14, 12, 5, 8 (sommet → fond) devient 5, 7, 8, 12, 14.

Exercice tiré du sujet NSI 2021 dit « 2 annulé », sur l'implémentation d'une file par deux piles.

On implémente une file file par un couple de piles (p1, p2). Enfiler = empiler dans p1. Défiler : si p2 non vide, dépiler p2 ; sinon transférer tout p1 vers p2 (en empilant, ce qui inverse l'ordre) puis dépiler p2.

1. Quelle structure (liste, dictionnaire, pile, file) met en œuvre nativement le FIFO ?

2. Avec retirer(lst) (renvoie et retire lst[0]), écrire ajouter(lst, proc) (ajout en fin de liste).

3. En partant de p1 = [ps3, ps4, ps5] (sommet ps5) et p2 = [ps2, ps1] (sommet ps1), exécuter enfiler(file, ps6), defiler(file) ×3, enfiler(file, ps7). Donner l'état final des deux piles.

4. Avec empiler(p, elt), depiler(p), pile_vide(p), écrire est_vide(f), enfiler(f, elt), defiler(f) pour cette file à deux piles.

Exercice tiré du bac NSI La Réunion 2022 (Jour 1), sur les piles et les files.

On munit Pile de creer_pile_vide(), est_pile_vide(p), empiler(p, element), depiler(p), sommet(p) ; File de creer_file_vide(), est_file_vide(f), enfiler(f, element), defiler(f), taille_file(f).

Convention : dans une file écrite « queue, ..., tête », enfiler ajoute en queue (à gauche), defiler retire la tête (à droite, premier servi). Pile p = 5,8,6,2 (sommet→fond). File f = 4,3,8,2,1 (queue→tête).

1. Depuis les valeurs initiales de p et f : a. Représenter f après enfiler(f, defiler(f)). b. Représenter p après empiler(p, depiler(p)). c. Représenter p et f après : for i in range(2): enfiler(f, depiler(p)). d. Représenter p et f après : for i in range(2): empiler(p, defiler(f)).

2. Fonction mystere :

def mystere(f):
    p = creer_pile_vide()
    while not est_file_vide(f):
        empiler(p, defiler(f))
    while not est_pile_vide(p):
        enfiler(f, depiler(p))
    return p

Appliquée à f = 1,2,3,4 (queue→tête) : préciser l'état de f après chaque boucle, et le contenu de la pile renvoyée.

3. Algorithme knuth(f) :

def knuth(f):
    p = creer_pile_vide()
    N = taille_file(f)
    for i in range(N):
        if est_pile_vide(p):
            empiler(p, defiler(f))
        else:
            e = defiler(f)
            if e >= sommet(p):
                empiler(p, e)
            else:
                while not est_pile_vide(p) and e < sommet(p):
                    enfiler(f, depiler(p))
                empiler(p, e)
    while not est_pile_vide(p):
        enfiler(f, depiler(p))

a. Dérouler pas à pas pour f = 2,1,3 (le premier passage donne f=2,1 et p=3). b. Que fait cet algorithme ?

Exercice tiré du bac NSI Métropole 2022 (Jour 1), sur les piles : parenthésage et balisage HTML.

Partie A. On enregistre, dans l'ordre, uniquement les parenthèses d'une expression. Ex : "(2+3)×(18/(4+2))" → ( ) ( ( ) ).

1. « Les éléments sont retirés dans le même ordre qu'ils ont été ajoutés » : file ou pile ? Justifier.

Variable controleur : 0 au départ, +1 sur (, -1 sur ). Pour ( ) ( ( ) ), elle prend 1,0,1,2,1,0 (correct).

2. Donner les valeurs de controleur pour B = ((( )( ) et C = (( )))(.

3. Compléter (test1 : fermante sans ouvrante ; test2 : parenthésage correct en fin d'analyse) :

controleur = 0
for parenthese in expression:
    if parenthese == '(':
        controleur = controleur + 1
    else:
        controleur = controleur - 1
        if controleur ... :   # test 1
            return False
if controleur ... :   # test 2
    return True
else:
    return False

Partie B. Analogie HTML : balise ouvrante → empiler ; fermante → dépiler et vérifier la correspondance (sinon, ou pile vide, incorrect).

4.a. Représenter la pile à chaque étape pour "<p><em></em></p>". 4.b. Condition sur la pile signalant un balisage correct en fin de parcours ?

5. Une expression correctement balisée contient 12 balises. Nombre maximal d'éléments dans la pile ?

Exercice tiré du bac NSI Métropole (session de remplacement) 2022, sur les files (file d'attente prioritaire).

Une file suit « premier arrivé, premier servi ». Opérations : creer_file_vide(), est_vide(File), enfiler(File, element), defiler(File).

1. Laquelle correspond à une file ? Situation 1 : crêpes empilées, on mange celle du dessus. Situation 2 : impression réseau, documents traités dans l'ordre d'arrivée.

On modélise une caisse de supermarché : les clients sont dans une File. Un client prioritaire passe directement en position 1 (les autres reculent d'une place) ; entre prioritaires, l'ordre d'arrivée est conservé.

File F (queue → tête) : Client4, Prioritaire, Client3, Client2, Client1.

2.a. Que valent V, F, val après :

V = creer_file_vide()
val = defiler(F)
while not est_vide(F) and val != 'Prioritaire':
    enfiler(V, val)
    val = defiler(F)

2.b. Compléter longueur_file(F) (doit restituer F intact) :

def longueur_file(F):
    V = creer_file_vide()
    n = 0
    while not est_vide(F):
        n = ...
        val = defiler(F)
        enfiler(V, val)
    while not est_vide(V):
        ...
        ...
    return n

2.c. Écrire compter_prio(F), renvoyant le nombre de personnes prioritaires, F restituée intacte.

Exercice tiré du bac NSI Centres étrangers 2021 (Jour 1), sur les piles.

Fonctions : empiler(P, e), depiler(P), est_vide(P), creer_pile().

Pile P d'origine (sommet → fond) : 4, 7, 1, 5.

1. En appliquant successivement empiler(P,8), puis depiler(P), puis est_vide(P), indiquer le contenu de P et la valeur renvoyée à chaque étape.

2.

def transforme(P):
    Q = creer_pile()
    while not est_vide(P):
        v = depiler(P)
        empiler(Q, v)
    return (P, Q)

Que renvoie transforme(P) pour P = 4,7,1,5 (sommet→fond) ? Que devient P ?

3. Écrire maximum(P), renvoyant la valeur maximale de P (on autorise que P soit vide après exécution).

4.a. Décrire une stratégie pour taille(P), renvoyant le nombre d'éléments de P. 4.b. Donner le code Python de taille(P).

Exercice tiré du bac NSI Amérique du Nord 2024 (jour 1), exercice 1, sur la structure de file (FIFO) appliquée à l'ordonnancement de processus par la méthode du tourniquet.

1. Citer les trois états dans lesquels un processus peut se trouver.

Une classe Processus fournit p.execute_un_cycle() et p.est_fini(). On ne s'intéresse pas ici aux ressources.

2. Citer les deux seuls états possibles pour un processus dans ce contexte simplifié.

class File:
    def __init__(self):
        self.contenu = []
 
    def enfile(self, element):
        self.contenu.append(element)
 
    def defile(self):
        return self.contenu.pop(0)
 
    def est_vide(self):
        return self.contenu == []

f = File(); print(f.defile()) produit une erreur.

3. Rectifier defile pour qu'elle renvoie None sur une file vide, au lieu d'une erreur.

Méthode du tourniquet : à chaque cycle, on enfile le nouveau processus créé s'il y en a un, on défile un processus et on l'exécute un cycle, puis on le replace en fin de file s'il n'est pas terminé.

p1 = Processus("p1", 4)
p2 = Processus("p2", 3)
p3 = Processus("p3", 5)
p4 = Processus("p4", 3)
depart_proc = {0: p1, 1: p3, 2: p2, 3: p4}

4. Construire le chronogramme (processus exécuté à chaque cycle) pour p1, p2, p3, p4.

5. Compléter la classe Ordonnanceur (attribut temps, méthodes ajoute_nouveau_processus et tourniquet, qui renvoie le nom du processus élu ou None).

6. Écrire un programme utilisant p1 à p4 et depart_proc, qui crée un ordonnanceur, ajoute chaque processus au bon cycle, affiche le processus élu à chaque cycle, et s'arrête quand il n'y a plus rien à exécuter.

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°03, exercice 2.

On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes. Un parenthésage est correct si :

• le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes ;
• en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes est, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.

Ainsi, ((()())(())) est un parenthésage correct. Les parenthésages ())(() et (())(() sont, eux, incorrects.

On dispose du code de la classe Pile suivant :

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []
 
    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []
 
    def empiler(self, v):
        """Place l'élément v au sommet de la pile"""
        self.contenu.append(v)
 
    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n'est pas vide. Produit une erreur sinon.
        """
        assert not self.est_vide()
        return self.contenu.pop()

On souhaite programmer une fonction bon_parenthesage qui prend en paramètre une chaîne de caractères ch formée de parenthèses et renvoie True si la chaîne est bien parenthésée et False sinon.

Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l'empile au sommet de la pile, et si on trouve une parenthèse fermante, on dépile (si possible) la parenthèse ouvrante stockée au sommet de la pile. La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide. Elle est, par contre, mal parenthésée :

• si, pendant le parcours, on trouve une parenthèse fermante alors que la pile est vide ;
• ou si, à la fin du parcours, la pile n'est pas vide.

Compléter le code de la fonction bon_parenthesage ci-dessous :

def bon_parenthesage(ch):
    """Renvoie un booléen indiquant si la chaîne ch
    est bien parenthésée"""
    p = Pile()
    for c in ch:
        if c == ...:
            p.empiler(c)
        elif c == ...:
            if p.est_vide():
                ...
            else:
                ...
    return ...

Exemples :

>>> bon_parenthesage("((()())(()))")
True
>>> bon_parenthesage("())(()")
False
>>> bon_parenthesage("(())(()")
False

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°38, exercice 2.

Cet exercice utilise des piles qui seront représentées par des listes Python.

Si pile est une pile, alors pile == [] indique si la pile est vide, pile.pop() retire et renvoie le sommet de la pile et pile.append(v) ajoute la valeur v au sommet de la pile.

Si on considère qu'une fonction manipule une pile, elle ne peut pas utiliser d'autres opérations que celles décrites ci-dessus.

On cherche à écrire une fonction positifs qui prend une pile de nombres entiers en paramètre et qui renvoie une nouvelle pile contenant les entiers positifs de la pile initiale, dans le même ordre, quitte à modifier la pile initiale.

Pour cela, on va également écrire une fonction renverse qui prend une pile en paramètre et qui renvoie une nouvelle pile contenant les mêmes éléments que la pile initiale, mais dans l'ordre inverse. Cette fonction sera également amenée à modifier la pile passée en paramètre.

Compléter le code Python des fonctions renverse et positifs ci-après.

def renverse(pile):
    '''renvoie une pile contenant les mêmes éléments que pile,
    mais dans l'ordre inverse.
    Cette fonction détruit pile.'''
    pile_inverse = ...
    while pile != []:
        ... .append(...)
    return ...
 
def positifs(pile):
    '''renvoie une pile contenant les éléments positifs de pile,
    dans le même ordre. Cette fonction détruit pile.'''
    pile_positifs = ...
    while pile != []:
        ... = pile.pop()
        if ... >= 0:
            ...
    return ...

Exemples :

>>> renverse([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
>>> positifs([-1, 0, 5, -3, 4, -6, 10, 9, -8])
[0, 5, 4, 10, 9]
>>> positifs([-2])
[]

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°47, exercice 2.

Nous avons l'habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : $(2 + 3) \times 5$.

Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n'utilise pas de parenthèses. L'expression arithmétique précédente est alors obtenue en saisissant successivement 2, puis 3, puis l'opérateur $+$, puis 5, et enfin l'opérateur $\times$. On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].

Autre exemple, la notation postfixe de $3 \times 2 + 5$ est modélisée par le tableau : [3, 2, '*', 5, '+'].

D'une manière plus générale, la valeur associée à une expression arithmétique en notation postfixe est déterminée à l'aide d'une pile en parcourant l'expression arithmétique de gauche à droite de la façon suivante :

• si l'élément parcouru est un nombre, on le place au sommet de la pile ;
• si l'élément parcouru est un opérateur, on récupère les deux éléments situés au sommet de la pile et on leur applique l'opérateur. On place alors le résultat au sommet de la pile ;
• à la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de l'expression arithmétique.

Dans le cadre de cet exercice, on se limitera aux opérations $\times$ et $+$.

Pour cet exercice, on dispose d'une classe Pile qui implémente les méthodes de base sur la structure de pile.

Compléter le script de la fonction eval_expression qui reçoit en paramètre une liste Python représentant la notation postfixe d'une expression arithmétique et qui renvoie sa valeur associée.

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []
 
    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []
 
    def empiler(self, v):
        """Place l'élément v au sommet de la pile"""
        self.contenu.append(v)
 
    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n'est pas vide. Produit une erreur sinon.
        """
        assert not self.est_vide()
        return self.contenu.pop()
 
def eval_expression(tab):
    p = Pile()
    for ... in tab:
        if element != '+' ... element != '*':
            p.empiler(...)
        else:
            if element == ...:
                resultat = ... + ...
            else:
                resultat = ...
            p.empiler(...)
    return ...

Exemples :

>>> eval_expression([2, 3, '+', 5, '*'])
25
>>> eval_expression([1, 2, '+', 3, '*'])
9
>>> eval_expression([1, 2, 3, '+', '*'])
5

Écrire une classe Rectangle avec :

1. un constructeur __init__(self, largeur, hauteur) qui initialise les attributs largeur et hauteur ;
2. une méthode aire(self) qui renvoie l'aire du rectangle ;
3. une méthode perimetre(self) qui renvoie son périmètre ;
4. une méthode est_carre(self) qui renvoie True si le rectangle est un carré.

Tester avec un rectangle de largeur 4 et de hauteur 6, puis un carré de côté 5.

Exercice tiré du sujet zéro 0.B du bac NSI (2024), sur les dictionnaires, la POO et le SQL, autour d'une base de livres de science-fiction.

Partie A (dictionnaire). Avec dico_livres structuré en colonnes parallèles (id, titre, auteur, ann_pub, note) : écrire titre_livre(dico, id_livre) (titre correspondant à un id, ou None), note_maxi(dico), livres_note(dico, n) (titres ayant la note n) et livre_note_maxi(dico) (titres ayant la meilleure note).

Partie B (POO). Une classe Livre (attributs id, titre, auteur, ann_pub, note, avec accesseurs) et une classe Bibliotheque (liste de Livre, méthode ajout_livre). Écrire get_note sur Livre. Créer le livre Blade Runner et l'ajouter à une bibliothèque. Écrire la méthode titre_livre(self, id_livre) de Bibliotheque.

Partie C (SQL). Table livres(id, titre, auteur, ann_pub, note). Pourquoi auteur ne peut-il pas être clé primaire ? Requête donnant les titres d'Asimov publiés après 1950. Requête faisant passer la note de Ubik à 10. On sépare ensuite auteurs(id, nom, prenom, annee_naissance) (Orwell 1903, Herbert 1920, Asimov 1920, K.Dick 1928, Bradbury 1920, Barjavel 1911, Hamilton 1960) et livres référence id_auteur. Pourquoi deux tables ? Requête donnant nom/prénom des auteurs publiés après 1960. Que renvoie une jointure filtrant sur ann_pub - annee_naissance < 30 ?

Exercice tiré du sujet NSI 2021 dit « 2 annulé », sur la POO et les arbres binaires de recherche.

Une classe Bim modélise un bien immobilier : nt (nature), sf (surface), pm (prix moyen au m²), avec estim_prix(self): return self.sf * self.pm.

1. Compléter le constructeur de Bim.

2. b1 = Bim('maison', 70.0, 2000.0) : que renvoie b1.estim_prix() ? Quel type ?

3. Modifier estim_prix : pour 'maison', multiplier par 1,1 ; pour 'bureau', par 0,8 ; sinon, ne pas changer.

4. Écrire nb_maison(lst), comptant les biens de nature 'maison' dans une liste.

5. Les biens sont stockés dans un arbre binaire de recherche abr (sous-arbre gauche : surfaces $\leqslant$ racine ; sous-arbre droit : surfaces strictement supérieures), avec est_vide(), get_v(), get_g(), get_d(). a. Pour un arbre de racine b1 (fils gauche b2, lui-même de fils droit b4 ; fils droit b3, de fils gauche b5 et fils droit b6), donner l'ordre croissant des surfaces. b. Compléter contient(surface, abr), qui renvoie True s'il existe un bien de surface $\geqslant$ surface :

def contient(surface, abr):
    if abr.est_vide():
        return False
    elif abr.get_v().sf >= ... :
        return True
    else:
        return contient(surface, ...)

Exercice tiré du bac NSI La Réunion 2022 (Jour 1), sur la programmation orientée objet.

Dans un jeu de plateforme, des bulles se déplacent aléatoirement ; quand une petite bulle touche une plus grosse, elle disparaît et cède sa surface à la grosse bulle (dont la vitesse est ensuite réduite de moitié).

from random import randint
from math import *
 
class Cbulle:
    def __init__(self):
        self.xc = randint(0, 100)
        self.yc = randint(0, 100)
        self.rayon = randint(0, 10)
        self.dirx = float(randint(-1, 1))
        self.diry = float(randint(-1, 1))
        self.couleur = randint(1, 65535)
 
    def bouge(self):
        self.xc = self.xc + self.dirx
        self.yc = self.yc + self.diry

6 bulles au maximum, stockées dans Mousse = [None]*6. Une bulle disparue redevient None ; une nouvelle bulle prend le premier None libre.

1.a. Compléter :

def donnePremierIndiceLibre(Mousse):
    i = 0
    while ......... and Mousse[i] != None:
        .........
    return i

(renvoie l'indice du premier None, ou 6 s'il n'y en a pas.)

1.b. Écrire placeBulle(B), qui place B (instance de Cbulle) dans le premier emplacement libre de Mousse (ne fait rien si aucun n'est libre).

2. On dispose de distanceEntreBulles(B1, B2). Écrire bullesEnContact(B1, B2), qui renvoie True si B2 touche B1.

3. Compléter collision :

def collision(indPetite, indGrosse, mousse):
    surfPetite = pi * Mousse[indPetite].rayon**2
    surfGrosse = pi * Mousse[indGrosse].rayon**2
    surfGrosseApresCollision = ..........................
    rayonGrosseApresCollision = sqrt(surfGrosseApresCollision / pi)
    Mousse[indGrosse].dirx = ..........................
    Mousse[indGrosse].diry = ..........................
    ..........................  # suppression de la petite bulle

Exercice tiré du bac NSI Métropole 2022 (Jour 1), sur la programmation orientée objet (jeu LaserGame).

class Joueur:
    def __init__(self, pseudo, identifiant, equipe):
        self.pseudo = pseudo
        self.equipe = equipe
        self.id = identifiant
        self.nb_de_tirs_emis = 0
        self.liste_id_tirs_recus = []
        self.est_actif = True
 
    def tire(self):
        if self.est_actif == True:
            self.nb_de_tirs_emis = self.nb_de_tirs_emis + 1
 
    def est_determine(self):
        return self.nb_de_tirs_emis > 500
 
    def subit_un_tir(self, id_recu):
        if self.est_actif == True:
            self.est_actif = False
            self.liste_id_tirs_recus.append(id_recu)

1. Laquelle déclare correctement joueur1 (pseudo "Sniper", id 319, équipe "A") ?

1. joueur1 = ["Sniper", 319, "A"]
2. joueur1 = new Joueur["Sniper", 319, "A"]
3. joueur1 = Joueur("Sniper", 319, "A")
4. joueur1 = Joueur{"pseudo":"Sniper", "id":319, "equipe":"A"}

2.a. Écrire redevenir_actif, qui réactive le joueur seulement s'il était désactivé. 2.b. Écrire nb_de_tirs_recus, renvoyant le nombre de tirs reçus.

3. Classe Base (equipe, liste_des_id_de_l_equipe, score=1000 initial ; est_un_id_allie, incremente_score, collecte_information) :

def collecte_information(self, participant):
    if participant.equipe == self.equipe:   # test 1
        for id in participant.liste_id_tirs_recus:
            if self.est_un_id_allie(id):   # test 2
                self.incremente_score(-20)
            else:
                self.incremente_score(-10)

3.a. Quel test vérifie qu'un participant égaré n'a pas rejoint la base adverse ? 3.b. Effet sur le score si un joueur de l'équipe est touché par un coéquipier ?

4. Bonus de 40 points par joueur déterminé (est_determine()) : compléter la fin de collecte_information (2 lignes).

Exercice tiré du bac NSI Centres étrangers 2021 (Jour 1), sur la programmation orientée objet (chiffrement de César).

class CodeCesar:
    def __init__(self, cle):
        self.cle = cle
        self.alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
    def decale(self, lettre):
        num1 = self.alphabet.find(lettre)
        num2 = num1 + self.cle
        if num2 >= 26:
            num2 = num2 - 26
        if num2 < 0:
            num2 = num2 + 26
        nouvelle_lettre = self.alphabet[num2]
        return nouvelle_lettre

1. Résultat de :

code1 = CodeCesar(3)
print(code1.decale('A'))
print(code1.decale('X'))

2. Ajouter cryptage(self, texte), qui chiffre texte lettre par lettre avec self.cle. Exemple : CodeCesar(3).cryptage("NSI") renvoie 'QVL'.

3. Écrire un programme demandant la clé, créant un objet CodeCesar, demandant le texte, puis affichant le texte chiffré.

4. Avec :

def transforme(self, texte):
    self.cle = -self.cle
    message = self.cryptage(texte)
    self.cle = -self.cle
    return message

Que va afficher print(CodeCesar(10).transforme("PSX")) ? Expliquer.

Exercice tiré du bac NSI Nouvelle-Calédonie 2022 (jour 2), sur la programmation orientée objet : un jeu vidéo de chevaliers de la table ronde.

Partie 1. Un personnage est repéré par des coordonnées x, y, z. a) Compléter le constructeur de Personnage(coordx, coordy, coordz). b) Écrire avancex, qui augmente x d'une unité. c) Écrire raz, qui remet les trois coordonnées à zéro. d) Écrire coord, qui renvoie les coordonnées sous forme de tuple. Écrire ensuite les instructions créant arthur en (5,5,5), avançant son x, puis affichant ses coordonnées.

Partie 2. La classe est enrichie d'un attribut vie et de méthodes get_etat, potionmystere (+1 ou -1 au hasard), piege (-10), repos (+5).

1. merlin = Personnage(4,5,8,15) puis merlin.potionmystere() : valeurs possibles de merlin.get_etat() ?
2. merlin = Personnage(4,5,8,20) puis deux merlin.piege() : valeur de merlin.get_etat() ?
3. Écrire newgame, qui, si vie <= 0, remet les coordonnées à (0,0,0) et vie à 15.

On ajoute perdre_vie(self, points) (retire points à vie puis appelle newgame) et attaquer(self, autre) (fait perdre à autre les degats de self).

4. Écrire un programme qui crée lancelot (coord. 5,5,5 ; 15 vie ; 3 dégâts) et sorcier (coord. 6,5,5 ; 15 vie ; 2 dégâts), fait attaquer le sorcier par lancelot, puis lancelot par le sorcier en retour, puis quatre attaques de suite de lancelot sur le sorcier, et affiche les points de vie finaux des deux personnages.

Exercice tiré du bac NSI Amérique du Nord 2024 (jour 2), exercice 3, sur la programmation orientée objet appliquée à une blockchain de monnaie nsicoin.

class Transaction:
    def __init__(self, expediteur, destinataire, montant):
        self.expediteur = expediteur
        self.destinataire = destinataire
        self.montant = montant

2. Dans un intervalle de dix minutes, Alice envoie dix nsicoin à Charlie, puis Bob envoie cinq nsicoin à Alice. Écrire la liste Python de ces transactions.

class Bloc:
    def __init__(self, liste_transactions, bloc_precedent):
        self.liste_transactions = liste_transactions
        self.bloc_precedent = bloc_precedent  # de type Bloc
 
class Blockchain:
    def __init__(self):
        self.tete = self.creer_bloc_0()
 
    def creer_bloc_0(self):
        """Cree le premier bloc, qui distribue 100 nsicoin a chaque
        utilisateur (expediteur pseudo-utilisateur Genesis)."""
        liste_transactions = [
            Transaction("Genesis", "Alice", 100),
            Transaction("Genesis", "Bob", 100),
            Transaction("Genesis", "Charlie", 100)
        ]
        return Bloc(liste_transactions, None)

Les trois premiers blocs d'une blockchain (tête = bloc2) sont : bloc0 (les 3 transactions Genesis) ; bloc1 (Alice->Charlie 50 ; Charlie->Bob 30) ; bloc2 (Bob->Charlie 20 ; Bob->Charlie 20 ; Charlie->Alice 30).

3. Pourquoi bloc_precedent du bloc0 vaut-il None ? 4. Que doit valoir bloc_precedent du bloc1 pour qu'il soit lié au bloc0 ? 5. Écrire le code créant un objet ma_blockchain représentant cette situation. 6. Donner le solde en nsicoin de Bob à l'issue du bloc2. 7. Écrire ajouter_bloc(self, liste_transactions) de Blockchain (crée un nouveau bloc à partir du bloc courant en tête, et l'y ajoute). 8. Pour envoyer le nouveau bloc à tous les autres membres, quelle adresse IP utiliser (nom et valeur) ?

Exercice 3 (8 points, partie programmation objet) du sujet de bac NSI 25-NSIPE2, session 2025.

Un parc d'attractions est représenté par un graphe : sommets = attractions (chacune avec une durée en minutes), arêtes = durée pour aller d'une attraction à l'autre. Attractions et durées : Petits chevaux (6 min), Grand huit (11 min), Grande roue (10 min), Train fantôme (9 min). Trajets : Petits chevaux–Grand huit (7 min), Petits chevaux–Grande roue (4 min), Petits chevaux–Train fantôme (3 min), Grand huit–Train fantôme (5 min), Grande roue–Train fantôme (6 min).

class Attraction:
    def __init__(self, nom, duree):
        self.nom = nom
        self.duree = duree
        self.voisines = []

a1 = Attraction("Grand huit", 11)
a2 = Attraction("Petits chevaux", 6)
a3 = Attraction("Train fantôme", 9)
a4 = Attraction("Grande roue", 10)
a1.voisines = [(a2,7), (a3,5)]
a2.voisines = [(a1,7), (a3,3), (a4,4)]
a3.voisines = [(a1,5), (a2,3), (a4,6)]
a4.voisines = ...

Par mesure de sécurité, la grande roue est ralentie : sa durée est maintenant de 12 minutes.

1. Écrire une ligne de code pour effectuer cette modification.
2. Donner et expliquer la valeur de a2.voisines[2][1].
3. Expliquer la ligne 7 (a3.voisines = ...) du code.
4. Recopier et compléter la ligne 8 (a4.voisines = ...).
5. Expliquer pourquoi cette modélisation utilise un graphe non orienté.

Une balade est un chemin du graphe, modélisé par un tableau d'attractions ; sa durée est la somme des durées de ses sommets et de ses arêtes. Par exemple [a1, a2, a3, a1, a3] est une balade.

6. Calculer la durée de la balade [a1, a2, a3] et expliquer le calcul.
7. Expliquer pourquoi [a2, a1, a4, a3] n'est pas une balade.

On suppose que deux objets Attraction peuvent être comparés avec ==.

8. Écrire sont_voisines(a, b) qui renvoie True si les deux attractions sont voisines.
9. Écrire est_balade(tableau) qui renvoie True si le tableau donné est une balade.

Fiche d'exercices POO, exercice 1 (application).

Cet exercice permet de pratiquer la manipulation d'objets et la surcharge d'opérateurs en Python, à travers des opérations mathématiques sur des vecteurs.

Objectif : créer une classe Vecteur qui représente un vecteur en deux dimensions avec les coordonnées x et y.

Ajouter les méthodes suivantes :

• une méthode d'initialisation __init__ ;
• une méthode __add__ pour additionner deux vecteurs ;
• une méthode __sub__ pour soustraire deux vecteurs ;
• une méthode __mul__ pour multiplier un vecteur par un scalaire (un nombre) ;
• une méthode __repr__ pour afficher un vecteur sous une forme lisible.

Aide : vérifier le résultat avec v1 = Vecteur(2, 3), v2 = Vecteur(1, 1), un scalaire = 3 (addition, soustraction v1 - v2, multiplication par un scalaire v1 * scalaire).

Fiche d'exercices POO, exercice 2 : création d'une classe Rectangle. Difficulté ().*

Objectif : créer une classe simple représentant un rectangle avec des attributs longueur et largeur.

• Créer la classe Rectangle avec un constructeur qui initialise les deux attributs.
• Ajouter une méthode calculer_surface qui renvoie la surface du rectangle.
• Ajouter une méthode afficher_dimensions qui affiche la longueur et la largeur du rectangle.

Extension : permettre de modifier les dimensions du rectangle après l'initialisation.

Fiche d'exercices POO, exercice « Gestion d'une Banque avec des comptes ». Difficulté (**).

Objectif : implémenter une classe représentant un compte bancaire avec des fonctionnalités de base.

• Créer une classe CompteBancaire avec les attributs titulaire, solde et numero_de_compte.
• Ajouter des méthodes pour deposer de l'argent, retirer de l'argent, et afficher_solde.
• Empêcher les retraits si le solde est insuffisant.

Extension : ajouter une méthode transferer pour transférer de l'argent entre deux comptes bancaires.

Fiche d'exercices POO, exercice « Hiérarchie de classes avec Animal ». Difficulté (**).

Objectif : utiliser l'héritage pour gérer différents types d'animaux.

• Créer une classe de base Animal avec un attribut nom et une méthode parler (qui ne fait rien dans la classe de base).
• Créer deux classes dérivées, Chien et Chat, qui redéfinissent la méthode parler (le chien aboie, le chat miaule).
• Créer un programme qui instancie plusieurs animaux et les fait parler.

Extension : ajouter une classe Oiseau qui a une méthode supplémentaire voler, et une classe Poisson qui a une méthode nager.

Fiche d'exercices POO, exercice « Système de gestion d'une bibliothèque ». Difficulté (**).*

Objectif : manipuler plusieurs objets pour simuler un système de gestion de bibliothèque.

• Créer une classe Livre avec des attributs comme titre, auteur, et disponible (booléen).
• Créer une classe Bibliotheque qui contient une liste de livres et propose des méthodes ajouter_livre, emprunter_livre (marquer un livre comme indisponible), et retourner_livre (marquer un livre comme disponible).
• Implémenter un système de recherche de livres par titre ou par auteur.

Extension : ajouter des classes dérivées LivrePapier et LivreNumerique, chaque type ayant des méthodes spécifiques comme telecharger pour un livre numérique.

Fiche d'exercices POO, exercice « Gestion d'un tournoi de jeu ». Difficulté (**).

Objectif : créer un système complexe simulant un tournoi avec des joueurs et des jeux.

• Créer une classe Joueur avec des attributs nom et score.
• Créer une classe Jeu avec une méthode jouer qui génère un score aléatoire pour deux joueurs et attribue la victoire au joueur avec le score le plus élevé.
• Créer une classe Tournoi qui gère une liste de joueurs et organise les matchs entre eux jusqu'à ce qu'il ne reste qu'un seul gagnant.

Extension : ajouter un système de classement des joueurs basé sur le nombre de victoires.

D'après un devoir de NSI Terminale.

En Python, 0.1 + 0.2 == 0.3 vaut False : 0,1 n'a pas d'écriture binaire finie, et le flottant stocké n'en est qu'une approximation. Une erreur de représentation numérique a d'ailleurs causé l'échec du vol inaugural d'Ariane 5 en 1996 (une valeur d'accélération trop grande pour le format qui devait la stocker).

Pour calculer exactement avec des décimaux, on les représente par une fraction décimale : 1,24 est stocké comme l'entier 124 et le nombre de chiffres après la virgule, 2, puisque $1{,}24 = \dfrac{124}{10^2}$.

class Decimal:
    def __init__(self, entier, n):
        while n > 0 and entier % 10 == 0:
            entier = entier // 10
            n = n - 1
        self.entier = entier
        self.n = n

1. Quel nombre représente chacun des objets Decimal(357, 2), Decimal(9200, 1), Decimal(92000, 2) et Decimal(50, 2) ? Donner leurs attributs entier et n après l'initialisation. Quel est le rôle de la boucle while ?
2. Écrire la méthode __eq__(self, other), qui teste l'égalité de deux décimaux.
3. Écrire les méthodes partEnt(self), qui renvoie la partie entière (un int), et partDec(self), qui renvoie la partie décimale (un Decimal), à l'aide des opérateurs //, % et **. Pour 13,025 : 13 et 0,025.
4. Écrire les méthodes __add__ et __mul__, sachant que $\dfrac{a}{10^n} + \dfrac{b}{10^m} = \dfrac{a \times 10^m + b \times 10^n}{10^{n+m}}$ et $\dfrac{a}{10^n} \times \dfrac{b}{10^m} = \dfrac{a \times b}{10^{n+m}}$.
5. Écrire l'instruction qui teste l'égalité $(1{,}2 + 0{,}8) \times 2{,}25 = 4{,}5$.
6. Expliquer chaque bloc de la méthode suivante.

    def __repr__(self):
        if self.n == 0:
            msg = str(self.entier)
        elif self.partEnt() == 0:
            ent = self.entier * 10
            msg = '0,'
            while ent // 10 ** self.n == 0:
                ent = ent * 10
                msg = msg + '0'
            msg = msg + str(self.entier)
        else:
            msg = str(self.entier)
            msg = msg[0:len(msg) - self.n] + ',' + msg[len(msg) - self.n:]
        return msg

7. Que modifier pour que l'entier 17 s'affiche 17,0 ?

D'après un devoir de NSI Terminale.

Partie A — Dominos. Un domino porte deux faces, A et B, avec chacune un nombre de points.

class Domino:
    def __init__(self, pointsA, pointsB):
        self.pointsA = pointsA
        self.pointsB = pointsB

1. Créer deux dominos domino_1 et domino_2, avec les points de votre choix.
2. Écrire la méthode affiche_points, qui affiche par exemple Face A : 4 Face B : 6, et la méthode total, qui renvoie le nombre total de points (10 ici).
3. Écrire une fonction cree_pioche() qui renvoie une liste de 7 dominos dont les points sont des entiers tirés au hasard entre 1 et 6, puis un programme qui crée une pioche et affiche les points de chacun de ses dominos.

Partie B — Durées. Une durée est définie par trois entiers : heures, minutes et secondes.

4. Écrire une classe Temps dont le constructeur reçoit ces trois valeurs.
5. Écrire une méthode conversion, qui renvoie la durée en secondes, et une méthode __str__, qui renvoie une chaîne de la forme 9 heures 45 minutes 10 secondes.
6. Écrire une méthode __add__, qui permet d'additionner deux durées, et une méthode __repr__, de sorte que la console produise :

>>> debut = Temps(9, 45, 10)
>>> duree = Temps(1, 30, 0)
>>> debut + duree
11:15:10

7. Écrire une méthode avance(self, s) qui fait avancer la durée de s secondes : Temps(17, 25, 38) avancé de 27 secondes doit donner 17 heures 26 minutes et 5 secondes.

D'après une fiche d'exercices de NSI Terminale.

1. Écrire une classe Eleve avec les attributs nom, classe et note, instancier trois élèves, puis écrire une fonction compare(eleve1, eleve2) qui renvoie le nom de l'élève qui a la meilleure note.

>>> henri = Eleve("Henri", "TG2", 12)
>>> lina = Eleve("Lina", "TG6", 15)
>>> compare(henri, lina)
'Lina'

2. Écrire une classe TriangleRect avec les attributs cote1, cote2 et hypotenuse. Le constructeur ne reçoit que les deux côtés de l'angle droit ; l'hypoténuse est calculée automatiquement : TriangleRect(3, 4).hypotenuse vaut 5.0.

3. Écrire une classe Player, instanciée sans argument, telle que :

• chaque joueur a un attribut energie, qui vaut 3 au départ, et un attribut alive, qui vaut True ;
• la méthode blessure() diminue l'énergie de 1, et la méthode soin() l'augmente de 1 ;
• quand l'énergie atteint 0, alive passe à False, et l'énergie ne doit plus jamais évoluer.

>>> mario = Player()
>>> mario.soin()
>>> mario.energie
4
>>> mario.blessure(); mario.blessure(); mario.blessure()
>>> mario.alive
True
>>> mario.blessure()
>>> mario.alive
False
>>> mario.soin()
>>> mario.alive, mario.energie
(False, 0)

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°14, exercice 2.

On dispose d'une classe Carte permettant de créer des objets modélisant des cartes à jouer. Compléter la classe Paquet_de_cartes suivante en respectant les spécifications données dans les chaînes de documentation.

Ajouter une assertion dans la méthode recuperer_carte afin de vérifier que le paramètre pos est correct. On rappelle que l'instruction

assert condition, message

permet de vérifier que la condition est vraie. Si ce n'est pas le cas, le programme s'arrête et affiche le message d'erreur fourni.

class Carte:
    def __init__(self, c, v):
        """Initialise les attributs couleur (entre 1 et 4),
        et valeur (entre 1 et 13). """
        self.couleur = c
        self.valeur = v
 
    def recuperer_valeur(self):
        """ Renvoie la valeur de la carte :
        As, 2, ..., 10, Valet, Dame, Roi """
        valeurs = ['As','2', '3', '4', '5', '6', '7', '8',
                   '9', '10', 'Valet', 'Dame', 'Roi']
        return valeurs[self.valeur - 1]
 
    def recuperer_couleur(self):
        """ Renvoie la couleur de la carte
        (parmi pique, coeur, carreau, trèfle). """
        couleurs = ['pique', 'coeur', 'carreau', 'trèfle']
        return couleurs[self.couleur - 1]
 
class Paquet_de_cartes:
    def __init__(self):
        """ Initialise l'attribut contenu avec une liste des 52
        objets Carte possibles rangés par valeurs croissantes en
        commençant par pique, puis cœur, carreau et trèfle. """
        ...
        ...
            ...
                ...
 
    def recuperer_carte(self, pos):
        """ Renvoie la carte qui se trouve à la position pos
        (entier compris entre 0 et 51). """
        ...
        ...

Exemple :

>>> jeu = Paquet_de_cartes()
>>> carte1 = jeu.recuperer_carte(20)
>>> carte1.recuperer_valeur() \
    + " de " + carte1.recuperer_couleur()
"8 de coeur"
>>> carte2 = jeu.recuperer_carte(0)
>>> carte2.recuperer_valeur() \
    + " de " + carte2.recuperer_couleur()
"As de pique"
>>> carte3 = jeu.recuperer_carte(52)
AssertionError : paramètre pos invalide

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°32, exercice 2.

Dans cet exercice, on appelle carré d'ordre $n$ un tableau de $n$ lignes et $n$ colonnes dont chaque case contient un entier naturel.

Exemples :

• c2, un carré d'ordre 2 : lignes [1, 7] et [7, 1] ;
• c3, un carré d'ordre 3 : lignes [3, 4, 5], [4, 4, 4] et [5, 4, 3] ;
• c3bis, un autre carré d'ordre 3 : lignes [2, 9, 4], [7, 0, 3] et [6, 1, 8].

Un carré est dit semimagique lorsque les sommes des éléments situés sur chaque ligne, chaque colonne sont égales.

• Ainsi c2 et c3 sont semimagiques car la somme de chaque ligne et de chaque colonne est égale à 8 pour c2 et 12 pour c3.
• Le carré c3bis n'est pas semimagique car la somme de la première ligne est égale à 15 alors que celle de la deuxième ligne est égale à 10.

Note : le sujet officiel ajoute « et chaque diagonale ». C'est faux, car les diagonales de c2 ont pour sommes 2 et 14, et c'est inutile, car la définition ne porte que sur les lignes et les colonnes.

La classe Carre ci-après contient des méthodes qui permettent de manipuler des carrés.

• La méthode constructeur crée un carré sous forme d'un tableau à deux dimensions à partir d'une liste d'entiers, et d'un ordre.
• La méthode affiche permet d'afficher le carré créé.

Exemple :

>>> lst_c3 = [3, 4, 5, 4, 4, 4, 5, 4, 3]
>>> c3 = Carre(lst_c3, 3)
>>> c3.affiche()
[3, 4, 5]
[4, 4, 4]
[5, 4, 3]

Compléter la méthode est_semimagique qui renvoie True si le carré est semimagique, False sinon.

class Carre:
    def __init__(self, liste, n):
        self.ordre = n
        self.tableau = [[liste[i + j * n] for i in range(n)]
                        for j in range(n)]
 
    def affiche(self):
        '''Affiche un carré'''
        for i in range(self.ordre):
            print(self.tableau[i])
 
    def somme_ligne(self, i):
        '''Calcule la somme des valeurs de la ligne i'''
        somme = 0
        for j in range(self.ordre):
            somme = somme + self.tableau[i][j]
        return somme
 
    def somme_col(self, j):
        '''Calcule la somme des valeurs de la colonne j'''
        somme = 0
        for i in range(self.ordre):
            somme = somme + self.tableau[i][j]
        return somme
 
    def est_semimagique(self):
        s = self.somme_ligne(0)
 
        #test de la somme de chaque ligne
        for i in range(...):
            if ... != s:
                return ...
 
        #test de la somme de chaque colonne
        for j in range(...):
            if ... != s:
                return ...
 
        return ...

Tester la méthode est_semimagique sur les carrés c2, c3 et c3bis.

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°39, exercice 2.

On définit une classe gérant une adresse IPv4.

On rappelle qu'une adresse IPv4 est une adresse de longueur 4 octets, notée en décimale à point, en séparant chacun des octets par un point. On considère un réseau privé avec une plage d'adresses IP de 192.168.0.0 à 192.168.0.255.

On considère que les adresses IP saisies sont valides.

Les adresses IP 192.168.0.0 et 192.168.0.255 sont des adresses réservées.

Le code ci-dessous implémente la classe AdresseIP.

class AdresseIP:
 
    def __init__(self, adresse):
        self.adresse =...
 
    def liste_octets(self):
        """renvoie une liste de nombres entiers,
        la liste des octets de l'adresse IP"""
        # Note : split découpe la chaine de caractères
        # en fonction du séparateur
        return [int(i) for i in self.adresse.split(".")]
 
    def est_reservee(self):
        """renvoie True si l'adresse IP est une adresse
        réservée, False sinon"""
        reservees = [ ... ]
        return ...
 
    def adresse_suivante(self):
        """renvoie un objet de AdresseIP avec l'adresse
        IP qui suit l'adresse self si elle existe et None sinon"""
        octets = ...
        if ... == 254:
            return None
        octet_nouveau = ... + ...
        return AdresseIP('192.168.0.' + ...)

Compléter le code ci-dessus et instancier trois objets : adresse1, adresse2, adresse3 avec respectivement les arguments suivants : '192.168.0.1', '192.168.0.2', '192.168.0.0'.

Vérifier que :

>>> adresse1.liste_octets()
[192, 168, 0, 1]
>>> adresse1.est_reservee()
False
>>> adresse3.est_reservee()
True
>>> adresse2.adresse_suivante().adresse # acces valide à adresse
                 # ici car on sait que l'adresse suivante existe
'192.168.0.3'

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°07 (situation d'évaluation d'une heure).

Coccinelles et pucerons

Les coccinelles jouent un rôle essentiel dans la régulation naturelle des pucerons, dont elles sont les principaux prédateurs. Dans une exploitation de tomates sous serre, un producteur est confronté à une prolifération de pucerons. Afin de limiter l'usage de traitements chimiques, il choisit une solution de lutte biologique consistant à introduire des coccinelles.

Il souhaite disposer d'un modèle numérique simplifié permettant d'étudier l'évolution de la population de coccinelles, leur consommation de pucerons, leur reproduction et leur mortalité.

Le fichier coccinelles.py contient :

• une classe Coccinelle dont les objets possèdent les attributs :
  • age : âge de la coccinelle (en jours) ;
  • esperance_de_vie : durée de vie maximale (en jours) ;
  • sexe : sexe de la coccinelle ("male" ou "femelle") ;
  • niv_nutrition : nombre de jours consécutifs durant lesquels la coccinelle s'est suffisamment nourrie ;
• une fonction evolution(population, nb_proies) simulant l'évolution de l'écosystème sur une journée.

Rappel : le module random permet de générer des valeurs aléatoires.

• random.randint(a, b) renvoie un entier aléatoire compris entre a et b inclus.
• random.random() renvoie un nombre flottant aléatoire compris entre 0 inclus et 1 exclu.

Question 1. On souhaite observer le comportement du modèle sur une courte période. Créer une population initiale contenant 3 coccinelles (2 femelles et 1 mâle), toutes âgées de 10 jours et ayant un niveau de nutrition de 2. Le nombre initial de pucerons est fixé à 200. Écrire une séquence d'instructions (utilisant une boucle) permettant de simuler l'évolution de ce petit écosystème sur 5 jours consécutifs, en appelant la fonction evolution. Afficher le nombre de coccinelles et de pucerons à la fin de chaque journée.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 2. Écrire une fonction simulation_simple(population, nb_proies) qui automatise ce processus sur une durée maximale de 30 jours. Cette fonction doit s'interrompre prématurément si la population de coccinelles ou de pucerons tombe à zéro. Elle doit renvoyer un triplet (tuple) contenant : le nombre final de coccinelles, le nombre final de pucerons, et le nombre de jours effectivement simulés. Tester cette fonction en créant une population initiale identique à la question précédente face à 1000 pucerons.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 3. Écrire la documentation et les commentaires de la méthode chasser.

Après une première analyse des résultats, le producteur se rend compte que le modèle actuel présente des limites biologiques importantes :

1. le modèle suppose que les coccinelles peuvent se reproduire dès leur naissance, alors qu'en réalité, la reproduction n'est possible qu'à partir de 20 jours de vie ;
2. le modèle ne tient pas compte des conséquences mortelles d'un manque de nourriture. Lorsqu'une coccinelle atteint un niveau de nutrition de 0, elle a en réalité 1 chance sur 3 (environ 33 % de probabilité) de ne pas survivre à la journée.

Question 4. Modifier les méthodes reproduction et a_survecu de la classe Coccinelle afin d'y intégrer ces deux nouvelles règles biologiques (la maturité sexuelle et l'impact mortel du manque de nourriture). Tester à nouveau la simulation globale pour observer les changements.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichier fourni : coccinelles.py

import random
 
 
class Coccinelle:
    def __init__(self, sexe, age, niv_nutrition):
        self.age = age
        self.esperance_de_vie = random.randint(200, 350)
        self.sexe = sexe
        self.niv_nutrition = niv_nutrition
 
    def chasser(self, nb_proies, nb_coccinelles):
        if nb_coccinelles == 0:
            return nb_proies
 
        proies_par_cocci = nb_proies / nb_coccinelles
 
        if proies_par_cocci > 20:
            consomme = random.randint(12, 20)
        elif proies_par_cocci > 10:
            consomme = random.randint(8, 15)
        else:
            consomme = random.randint(3, 8)
 
        consomme = min(consomme, nb_proies)
 
        if consomme >= 10:
            self.niv_nutrition += 1
        else:
            self.niv_nutrition = max(0, self.niv_nutrition - 1)
 
        return nb_proies - consomme
 
    def reproduction(self):
        """
        Une femelle avec un niveau de nutrition >= 2 engendre exactement
        deux descendants : un mâle et une femelle.
        """
        descendants = []
        if self.sexe == "femelle" and self.niv_nutrition >= 2:
            descendants.append(Coccinelle("male", 0, 0))
            descendants.append(Coccinelle("femelle", 0, 0))
            self.niv_nutrition = 0
 
        return descendants
 
    def a_survecu(self):
        """
        Met à jour l'âge de la coccinelle et indique si elle est encore en vie.
        """
        self.age = self.age + 1
        return self.age < self.esperance_de_vie
 
    def __repr__(self):
        return f"Coccinelle {self.sexe}, âge: {self.age}/{self.esperance_de_vie}, niv_nutrition: {self.niv_nutrition}"
 
 
def evolution(population, nb_proies):
    """
    Simule une journée dans l'écosystème :
    - chasse des coccinelles
    - reproduction
    - vieillissement et mortalité
    - croissance des pucerons
 
    population est une liste d'instances de la classe Coccinelle
    nb_proies est un entier indiquant le nombre de proies
 
    Cette fonction renvoie un couple (population_suivante, nouveau_nb_proies) indiquant
    la nouvelle population à la fin de la journée et le nombre de proies.
    """
    population_suivante = []
    nouveau_nes = []
    nb_coccinelles = len(population)
 
    for coccinelle in population:
        nb_proies = coccinelle.chasser(nb_proies, nb_coccinelles)
 
        if coccinelle.a_survecu():
            population_suivante.append(coccinelle)
 
        nouveau_nes += coccinelle.reproduction()
 
    # Croissance naturelle des pucerons (augmentation de 20% par jour)
    nb_proies = int(nb_proies * 1.2)
 
    # Ajout des nouveau-nés en fin de journée
    population_suivante += nouveau_nes
 
    return population_suivante, nb_proies
 
 
#############################################################################
# Écrire ci-dessous le code pour les questions de l'énoncé                  #
#############################################################################

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°09 (situation d'évaluation d'une heure).

Objets 3D et impression

Les fichiers OBJ constituent l'un des formats les plus utilisés dans le domaine de la modélisation 3D. Étant donné un repère orthonormé, ils servent à décrire une forme géométrique en listant ses sommets (les points dans l'espace) et ses faces (les surfaces reliant ces points). Grâce à ce principe, il est possible de représenter aussi bien des objets simples, comme un cube, que des modèles complexes issus de logiciels de modélisation.

Ce format est particulièrement apprécié parce qu'il est simple à lire, facile à manipuler et compatible avec la majorité des outils 3D. Cette simplicité vient du fait qu'un fichier OBJ n'est rien d'autre qu'un fichier texte, dans lequel on décrit ligne par ligne les différents éléments : le nom de l'objet (o), les sommets (v), les faces (f)…

Voici un exemple du contenu d'un fichier OBJ permettant de construire une seule face d'un cube (figure 1).

o cube
v 0.0 0.0 0.0
v 0.0 1.0 0.0
v 1.0 1.0 0.0
v 1.0 0.0 0.0
f 1 2 3 4

Dans ce sujet, on ne considère que des coordonnées entières.

Représentation de l'information

Pour manipuler ces fichiers OBJ, nous avons à disposition trois classes Python :

• la classe Sommet : elle représente un sommet, défini par trois entiers précisant les coordonnées $x$, $y$ et $z$ du sommet ;
• la classe Face : elle représente une face d'un élément 3D, définie par une liste d'indices. Cet indice identifie un sommet présent dans la liste des sommets d'un Objet3D ;
• la classe Objet3D : elle représente un élément 3D, défini par une liste d'objets de type Sommet et une liste d'objets de type Face.

Chaque classe est définie dans son propre module Python. Ainsi, la classe Sommet est définie dans Sommet.py.

Calcul du volume d'un élément 3D

On s'intéresse au calcul du volume d'un objet afin d'obtenir une estimation du temps d'impression à l'aide d'une imprimante 3D. Pour cela, on va chercher l'arête la plus longue présente sur une de ses faces et approcher le volume de l'objet par celui d'un cube de même arête. Pour calculer la longueur d'une arête, il suffit de calculer la distance entre les deux sommets qui la composent.

Question 1. Écrire la méthode distance de la classe Sommet. Elle prend en paramètre un objet de type Sommet. La méthode renvoie la distance entre l'objet courant et l'objet de type Sommet passé en paramètre. On rappelle que la distance entre deux points $A$ et $B$ dans un repère choisi s'obtient grâce à la formule

avec $(x_A ; y_A ; z_A)$ les coordonnées du point $A$ et $(x_B ; y_B ; z_B)$ les coordonnées du point $B$. Pour calculer le résultat d'une racine carrée en Python, on peut utiliser la fonction sqrt du module math.

Pour obtenir l'arête la plus longue, on va considérer tous les couples de sommets formant une arête et calculer le couple de plus grande longueur. Quand deux sommets sont les extrémités d'une arête d'une face, on dit qu'ils sont adjacents.

Question 2. Écrire la méthode sommets_adjacents de la classe Objet3D qui prend en entrée deux points donnés par leurs coordonnées et renvoie True s'ils représentent une arête de l'objet 3D et False sinon. Attention, on considère que les arêtes ne sont pas ordonnées, ainsi sommets_adjacents(s1, s2) == sommets_adjacents(s2, s1).

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

On dispose d'une méthode volume_cube_englobant dans la classe Objet3D qui utilise la fonction précédente pour estimer le volume d'un objet 3D.

Dans le fichier Imprimante3D.py, on définit une classe Imprimante3D qui contient deux attributs :

• l'attribut remplissage précise le taux de remplissage, flottant entre 0.0 et 1.0, du plastique lors de l'impression ;
• l'attribut vitesse_extrusion précise la vitesse d'impression de l'imprimante. Elle est représentée sous la forme d'un entier, précisant la vitesse en mm³/s.

On considère que l'unité géométrique est de 1 mm. Ainsi, le sommet de coordonnées (2, 0, 0) est à 2 mm de l'origine du repère.

Question 3. Écrire une méthode estimation_impression pour la classe Imprimante3D qui prend en paramètre un Objet3D et renvoie une estimation de son temps d'impression en secondes en procédant ainsi :

• dans un premier temps, il faut calculer le volume d'impression de l'objet, c'est-à-dire en multipliant le volume réel par le taux de remplissage ;
• dans un second temps, il faut calculer le temps d'impression en secondes. On rappelle que le temps s'obtient en divisant le volume d'impression de l'objet par la vitesse d'extrusion de l'imprimante.

Manipulation d'objets 3D

On souhaite agrandir ou rétrécir un objet 3D selon un rapport (agrandissement ou réduction). On dispose dans la classe Objet3D de la méthode transformer, qui permet de transformer l'instance courante selon le rapport passé en paramètre.

Question 4. Utiliser cette méthode pour doubler la dimension du cube présent dans Objet3D.py en l'affichant avant et après l'appel. Le cube n'apparaît pas deux fois plus grand : analyser le fonctionnement de la méthode transformer et proposer une correction.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichiers fournis

Le dossier comporte une version PDF de l'énoncé et les fichiers de classes Objet3D.py, Face.py, Sommet.py et Imprimante3D.py. Les bibliothèques matplotlib et math doivent être disponibles.

Sommet.py

import math
 
 
class Sommet:
 
    """
    Représente un sommet (point) dans l'espace 3D.
    """
 
    def __init__(self, x, y, z):
        """
        Initialise un sommet avec ses coordonnées.
        """
        self.x = x
        self.y = y
        self.z = z
 
    #############################################################################
    # Écrire le code de la méthode distance de la question 1                    #
    #############################################################################
 
    def distance(self, s):
        return ((s.x-self.x)**2+(s.y-self.y)**2+(s.z-self.z)**2)**0.5
 
 
#############################################################################
# Programme pour tester votre méthode de la question 1                      #
#############################################################################
s1 = Sommet(0, 0, 0)
s2 = Sommet(3, 4, 0)

Face.py

class Face:
 
    """
    Représente une face d'un objet 3D.
    """
 
    def __init__(self, sommets):
        self.sommets = sommets

Objet3D.py

from Sommet import Sommet
from Face import Face
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
 
 
class Objet3D:
 
    """
    Représente un objet 3D composé de sommets, de faces et d'un nom.
    """
 
    def __init__(self):
        """
        Initialise un objet 3D vide.
        """
        self.sommets = []
        self.faces = []
        self.nom = ""
 
    def ajouter_sommet(self, x, y, z):
        """
        Ajoute un sommet à l'objet 3D.
        """
        self.sommets.append(Sommet(x, y, z))
 
    def ajouter_face(self, liste_sommets):
        """
        Ajoute une face à l'objet 3D.
        """
        self.faces.append(Face([self.sommets[i] for i in liste_sommets]))
 
    def __str__(self):
        """
        Renvoie une représentation textuelle de l'objet 3D.
        """
        return str({'nom': self.nom, 'sommets': len(self.sommets), 'faces': len(self.faces)})
 
    def afficher(self):
        """
        Affiche l'objet 3D à l'aide de matplotlib.
        """
        fig = plt.figure()
        ax = fig.add_subplot(111, projection='3d')
 
        f = []
        for face in self.faces:
            x = [(s.x, s.y, s.z) for s in face.sommets]
            f.append(x)
        mesh = Poly3DCollection(f, alpha=0.4, edgecolor='black')
        ax.add_collection3d(mesh)
        plt.show()
 
    #############################################################################
    # Méthode à modifier de la question 5                                       #
    #############################################################################
    def transformer(self, rapport):
        """
        Applique une transformation d'échelle à l'objet 3D en modifiant directement ses sommets.
        """
        sommets = []
        for sommet in self.sommets:
            sommets.append(
                Sommet(sommet.x * rapport,
                       sommet.y * rapport, sommet.z * rapport))
        self.sommets = sommets
 
    #############################################################################
    # Écrire le code de la méthode sommets_adjacents de la question 2           #
    #############################################################################
 
    def sommets_adjacents(self, s1, s2):
        pass
 
    def longueur_plus_longue_arete(self):
        max_longueur = 0
        for s1 in self.sommets:
            for s2 in self.sommets:
                if self.sommets_adjacents(s1, s2):
                    d = s1.distance(s2)
                    if d > max_longueur:
                        max_longueur = d
        return max_longueur
 
    def volume_cube_englobant(self):
        longueur_max = self.longueur_plus_longue_arete()
        return longueur_max ** 3
 
 
#############################################################################
# Cube pour tester votre méthode de la question 2                           #
#############################################################################
 
cube = Objet3D()
cube.ajouter_sommet(0, 0, 0)  # s0
cube.ajouter_sommet(1, 2, 2)  # s1
cube.ajouter_sommet(3, 3, 0)  # s2
cube.ajouter_sommet(2, 1, -2)  # s3
cube.ajouter_sommet(-2, 2, -1)  # s4
cube.ajouter_sommet(-1, 4, 1)  # s5
cube.ajouter_sommet(1, 5, -1)  # s6
cube.ajouter_sommet(0, 3, -3)  # s7
cube.ajouter_face([0, 1, 2, 3])
cube.ajouter_face([4, 5, 6, 7])
cube.ajouter_face([0, 1, 5, 4])
cube.ajouter_face([1, 2, 6, 5])
cube.ajouter_face([2, 3, 7, 6])
cube.ajouter_face([3, 0, 4, 7])
# cube.afficher() # à décommenter pour afficher le cube en 3d

Imprimante3D.py

from Objet3D import Objet3D
 
#############################################################################
# Variables et fonctions fournies pour la question 3                        #
#############################################################################
 
 
class Imprimante3D:
    def __init__(self, remplissage, vitesse_extrusion):
        self.remplissage = remplissage
        self.vitesse_extrusion = vitesse_extrusion
 
    #############################################################################
    #  Écrire le code de la méthode estimation_impression de la question 3      #
    #############################################################################
 
    def estimation_impression(self, objet):
        pass
 
 
rhombi = Objet3D()
 
# Définition des 24 sommets
rhombi.ajouter_sommet(1, 1, 3)    # s0
rhombi.ajouter_sommet(1, 1, -3)   # s1
rhombi.ajouter_sommet(1, -1, 3)   # s2
rhombi.ajouter_sommet(1, -1, -3)  # s3
rhombi.ajouter_sommet(-1, 1, 3)   # s4
rhombi.ajouter_sommet(-1, 1, -3)  # s5
rhombi.ajouter_sommet(-1, -1, 3)  # s6
rhombi.ajouter_sommet(-1, -1, -3)  # s7
rhombi.ajouter_sommet(1, 3, 1)    # s8
rhombi.ajouter_sommet(1, 3, -1)   # s9
rhombi.ajouter_sommet(1, -3, 1)   # s10
rhombi.ajouter_sommet(1, -3, -1)  # s11
rhombi.ajouter_sommet(-1, 3, 1)   # s12
rhombi.ajouter_sommet(-1, 3, -1)  # s13
rhombi.ajouter_sommet(-1, -3, 1)  # s14
rhombi.ajouter_sommet(-1, -3, -1)  # s15
rhombi.ajouter_sommet(3, 1, 1)    # s16
rhombi.ajouter_sommet(3, 1, -1)   # s17
rhombi.ajouter_sommet(3, -1, 1)   # s18
rhombi.ajouter_sommet(3, -1, -1)  # s19
rhombi.ajouter_sommet(-3, 1, 1)   # s20
rhombi.ajouter_sommet(-3, 1, -1)  # s21
rhombi.ajouter_sommet(-3, -1, 1)  # s22
rhombi.ajouter_sommet(-3, -1, -1)  # s23
 
# Faces carrées principales (axiales)
rhombi.ajouter_face([0, 2, 6, 4])     # Z+
rhombi.ajouter_face([1, 5, 7, 3])     # Z-
rhombi.ajouter_face([16, 17, 19, 18])  # X+
rhombi.ajouter_face([20, 22, 23, 21])  # X-
rhombi.ajouter_face([8, 12, 13, 9])   # Y+
rhombi.ajouter_face([10, 11, 15, 14])  # Y-
 
# Faces carrées de jonction (arêtes)
rhombi.ajouter_face([0, 16, 18, 2])   # Z+/X+
rhombi.ajouter_face([4, 6, 22, 20])   # Z+/X-
rhombi.ajouter_face([1, 3, 19, 17])   # Z-/X+
rhombi.ajouter_face([5, 21, 23, 7])   # Z-/X-
rhombi.ajouter_face([0, 4, 12, 8])    # Z+/Y+
rhombi.ajouter_face([2, 10, 14, 6])   # Z+/Y-
rhombi.ajouter_face([1, 9, 13, 5])    # Z-/Y+
rhombi.ajouter_face([3, 7, 15, 11])   # Z-/Y-
rhombi.ajouter_face([8, 16, 17, 9])   # Y+/X+
rhombi.ajouter_face([12, 20, 21, 13])  # Y+/X-
rhombi.ajouter_face([10, 18, 19, 11])  # Y-/X+
rhombi.ajouter_face([14, 22, 23, 15])  # Y-/X-
 
# Faces triangulaires (sommets)
rhombi.ajouter_face([0, 8, 16])  # X+Y+Z+
rhombi.ajouter_face([4, 12, 20])  # X-Y+Z+
rhombi.ajouter_face([2, 10, 18])  # X+Y-Z+
rhombi.ajouter_face([6, 14, 22])  # X-Y-Z+
rhombi.ajouter_face([1, 17, 9])  # X+Y+Z-
rhombi.ajouter_face([5, 13, 21])  # X-Y+Z-
rhombi.ajouter_face([3, 19, 11])  # X+Y-Z-
rhombi.ajouter_face([7, 15, 23])  # X-Y-Z-
 
# rhombi.afficher() # à décommenter pour afficher le rhombicuboctaèdre
 
imprimante = Imprimante3D(20, 1.2)
print(imprimante.estimation_impression(rhombi))

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°21 (situation d'évaluation d'une heure).

Cartes mémoire et boîtes de Leitner

Les cartes mémoire (ou flashcards) sont des supports de révision comportant au recto une question et au verso la réponse. Elles permettent des révisions actives très efficaces.

On souhaite développer une application utilisant le système des boîtes de Leitner, qui permet de gérer ces cartes en se basant sur un principe de répétition espacée. Dans cette méthode, chaque carte possède un niveau d'avancement (de 0 à 4). Plus le niveau est élevé, plus le délai avant la prochaine révision est grand. Les délais sont donnés par le tableau suivant :

En pratique, la méthode fonctionne ainsi : lorsque l'utilisateur révise une carte, s'il répond correctement, la carte passe au niveau supérieur (sans dépasser le niveau 4 maximum). S'il se trompe, la carte retombe immédiatement au niveau 0, quel que soit son niveau précédent. La prochaine date de révision est ensuite calculée en ajoutant le délai du nouveau niveau à la date du jour.

On modélise ce fonctionnement à l'aide de la programmation orientée objet. Dans le fichier cartes.py, la classe Carte a été commencée.

Question 1. Écrire la méthode traiter_reponse(self, succes) qui prend en paramètre un booléen succes (True si l'utilisateur a bien répondu, False sinon). Cette méthode doit mettre à jour l'attribut self.niveau de la carte selon les règles de Leitner énoncées, puis calculer et mettre à jour l'attribut self.date_prochaine en utilisant la liste globale DELAIS.

Indication : pour ajouter des jours à la date d'aujourd'hui, on utilisera la fonction fournie date_future(nb_jours) qui renvoie la date située nb_jours après aujourd'hui.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

On considère que la base de révision, le paquet de cartes, est une liste d'instances de la classe Carte.

Question 2. Écrire une fonction extraire_cartes_du_jour(paquet, date_jour) qui prend en paramètres une liste de cartes paquet et une date de référence date_jour et qui renvoie une nouvelle liste contenant uniquement les cartes dont la date_prochaine est inférieure ou égale à date_jour. On admet qu'on peut comparer des dates avec les opérateurs usuels <, <=, ==, >= et >.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Afin d'aider l'étudiant à cibler ses lacunes, on souhaite extraire du paquet les cartes qui lui posent le plus de problèmes, c'est-à-dire celles dont le niveau est le plus bas parmi toutes les cartes du paquet. La fonction extraire_cartes_a_renforcer(paquet) a été rédigée dans ce but. Cependant, elle contient une faille logique.

Question 3. Exécuter la fonction test_renforcement() fournie. Observer le résultat affiché dans la console et constater l'incohérence. Analyser le code de la fonction extraire_cartes_a_renforcer(paquet), identifier la source de cette erreur logique, puis corriger le code afin qu'il ne renvoie que les cartes possédant rigoureusement le niveau minimum.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichier fourni : cartes.py

import datetime
 
 
def date_future(nb_jours):
    """Renvoie la date située nb_jours après aujourd'hui"""
    return datetime.date.today() + datetime.timedelta(days=nb_jours)
 
 
# Variable contenant les délais en jours pour chaque niveau (index 0 à 4)
DELAIS = [1, 3, 7, 15, 30]
 
 
class Carte:
 
    def __init__(self, question, reponse):
        self.question = question
        self.reponse = reponse
        self.niveau = 0
        # À la création, la carte est à réviser le jour même
        self.date_prochaine = datetime.date.today()
 
    def __repr__(self):
        return f"<Carte: {self.question} (Niveau {self.niveau})>"
 
    #############################################################################
    # Écrire la méthode traiter_reponse(self, succes) de la question 1          #
    #############################################################################
 
 
# Des cartes et un paquet de cartes pour réaliser des tests
c1 = Carte("Capitale de l'Italie ?", "Rome")
c1.niveau = 2
c1.date_prochaine = date_future(4)
c2 = Carte("7 x 8 ?", "56")
c2.date_prochaine = date_future(1)
c3 = Carte("Symbole du Fer ?", "Fe")
c3.date_prochaine = date_future(7)
 
paquet = [c1, c2, c3]
 
 
#############################################################################
# Écrire la fonction extraire_cartes_du_jour de la question 2               #
#############################################################################
 
 
#############################################################################
# Fonction défaillante à analyser et corriger pour la question 3            #
#############################################################################
 
def extraire_cartes_a_renforcer(paquet):
    """
    Parcourt le paquet et renvoie la liste des cartes ayant le 
    niveau d'avancement le plus faible.
    """
    if len(paquet) == 0:
        return []
 
    niveau_min = paquet[0].niveau
    a_renforcer = []
 
    for carte in paquet:
        if carte.niveau < niveau_min:
            niveau_min = carte.niveau
            a_renforcer.append(carte)
        elif carte.niveau == niveau_min:
            a_renforcer.append(carte)
 
    return a_renforcer
 
 
def test_renforcement():
    # Création d'un paquet de test
    c1 = Carte("Capitale de l'Italie ?", "Rome")
    c1.niveau = 2
 
    c2 = Carte("7 x 8 ?", "56")
    c2.niveau = 1
 
    c3 = Carte("Symbole du Fer ?", "Fe")
    c3.niveau = 2
 
    mon_paquet = [c1, c2, c3]
 
    # Appel de la fonction défaillante
    resultat = extraire_cartes_a_renforcer(mon_paquet)
 
    print("Cartes à renforcer (celles ayant le niveau le plus bas) :")
    print(resultat)

En utilisant la classe Noeud du cours, écrire une fonction récursive hauteur(arbre) qui renvoie la hauteur d'un arbre binaire (on prendra $-1$ pour un arbre vide, None, et $0$ pour un arbre réduit à un seul nœud). Calculer ensuite la hauteur de l'arbre T(Y(P,·),O(H,N)) de l'exemple du cours.

Exercice tiré du sujet zéro officiel du bac NSI (2021), sur les arbres binaires et les arbres binaires de recherche (convention : un arbre à un seul nœud a pour hauteur 1).

1. L'arbre suivant a pour racine A, avec B (fils gauche) et E (fils droit) ; B a pour fils C (gauche) et D (droite) ; D a pour fils gauche G ; E a pour fils gauche F ; F a pour fils H (gauche) et I (droite). Déterminer sa taille et sa hauteur.

2. On numérote les nœuds en binaire : racine = 1 ; fils gauche d'un nœud numéroté $k$ = $k$ suivi de 0 ; fils droit = $k$ suivi de 1. Sur cet arbre, A=1, B=10, C=100, E=11, F=110. a. Numéro binaire de G ? b. Quel nœud porte le numéro dont la valeur décimale est 13 ? c. Pour un arbre de hauteur $h$, sur combien de bits sont numérotés les nœuds du niveau le plus bas ? d. Justifier que pour un arbre de hauteur $h$ et de taille $n \geqslant 2$, on a $h \leqslant n \leqslant 2^h - 1$.

3. Un arbre binaire complet (à 15 nœuds, A à O, remplis niveau par niveau) est représenté par un tableau de taille 16 (indice 0 = taille $n$ ; racine à l'indice 1 ; fils gauche du nœud $i$ à $2i$ ; fils droit à $2i+1$). Donner ce tableau. Quel est, dans un tel tableau, l'indice du père du nœud d'indice $i \geqslant 2$ ?

4. Pour un arbre binaire de recherche complet représenté par un tel tableau, écrire recherche(arbre, element) qui renvoie True si element est présent, False sinon.

Exercice tiré du bac NSI 2022 (Asie/Pacifique, Jour 2), sur les arbres binaires de recherche.

Un éditeur stocke des noms d'auteurs dans un arbre binaire de recherche (ordre alphabétique). Arbre A1 : ELUARD (racine), ARAGON (gauche, avec APOLLINAIRE en fils gauche), VOLTAIRE (droite).

1. Insérer successivement DUMAS, HUGO, ZWEIG, ZOLA dans A1. Donner taille et hauteur de l'arbre obtenu (un nœud seul = hauteur 1). Pour une hauteur $h$, nombre maximal de nœuds ?

On définit l'équilibre d'un arbre (0 si vide, sinon différence des hauteurs gauche/droite) ; un arbre est équilibré si son équilibre est dans $\{-1,0,1\}$. Arbre A2 : KAFKA (racine), DURAS (gauche, feuille), SAGAN (droite, avec SIMENON en fils droit) — équilibre $-1$.

2. Insérer FLAUBERT, BALZAC, PROUST, SAND, WOOLF, COLETTE, CHRISTIE, AUDIARD dans A2, en choisissant un ordre qui garde l'arbre équilibré à chaque étape.

3. On donne une fonction mystere(abr, t) qui teste récursivement (sans utiliser la propriété de recherche) si t est une étiquette de abr. Que renvoie mystere(A2, 'SIMENON') ? Justifier.

4. Écrire une fonction récursive hauteur(abr) (renvoyant la hauteur d'un arbre binaire quelconque).

Exercice tiré du bac NSI La Réunion 2022 (Jour 1), sur les arbres binaires et leurs parcours en profondeur (préfixe/infixe).

Arbre généalogique fictif : nœud Noeud(identite=(prenom,nom), gauche, droite) — le sous-arbre gauche est le père, le sous-arbre droit la mère. Racine : Albert Normand. Parents : Jules Normand (père), Marie Comtois (mère). Grands-parents paternels : Michel Normand, Hélène Breton. Grands-parents maternels : Thibaut Comtois, Gabrielle Savoyard. Arrière-grands-parents (sans parents connus) : côté Michel → Jules Normand, Odile Picard ; côté Hélène → Evariste Breton, Camélia Charentais ; côté Thibaut → Léo Comtois, Eulalie Lorrain ; côté Gabrielle → Guillaume Savoyard, Janet Chesterfield.

1.a. En quoi cet arbre généalogique est-il un arbre binaire ? 1.b. Pourquoi n'est-ce pas un arbre binaire de recherche (ABR) ?

2.a. Donner les 7 premières personnes en parcours préfixe. 2.b. Donner les 7 premières personnes en parcours infixe.

def parcours(racine_de_l_arbre):
    if racine_de_l_arbre != None:
        noeud_actuel = racine_de_l_arbre
        parcours(noeud_actuel.gauche)
        parcours(noeud_actuel.droite)

2.c. Insérer l'instruction d'affichage pour un parcours préfixe. 2.d. Insérer l'instruction d'affichage pour un parcours infixe.

3.a. Ajouter à Noeud un attribut generation (0 par défaut) :

class Noeud:
    def __init__(self, prenom, nom):
        self.identite = (prenom, nom)
        self.gauche = None
        self.droite = None
        ..........................

3.b. Écrire numerotation(racine_de_l_arbre, num_gen=0) (récursive), qui affecte generation (parents = 1, etc.).

4. Avec :

def mystere(N, affiche):
    if N != None:
        if affiche:
            print(N.identite[0])
        mystere(N.gauche, False)
        mystere(N.droite, True)

donner le résultat, dans l'ordre, de mystere(racine_de_l_arbre, False) où racine_de_l_arbre référence Albert Normand.

Exercice tiré du bac NSI Métropole (session de remplacement) 2022, sur les arbres binaires de recherche (ABR) et leurs parcours.

Rappel : dans un ABR, les clés du sous-arbre gauche sont ≤ la racine, celles du sous-arbre droit sont strictement > la racine, et chaque sous-arbre est lui-même un ABR.

1. Parmi ces trois arbres, lequel/lesquels sont des ABR ?

• Arbre 1 : racine 3, gauche 2(enfants 1,3), droite 4(enfants 4,5).
• Arbre 2 : racine 4, gauche 2(enfants 1,3), droite 4(enfants 4,5).
• Arbre 3 : racine 3, gauche 2(enfants 1,1), droite 4(enfants 3,5).

2.a. Dans un ABR, où se trouve le plus petit élément ? Justifier. 2.b. Écrire RechercheValeur(cle, a) récursive (avec creer_arbre, est_vide, racine, sous_arbre_gauche, sous_arbre_droit), renvoyant un booléen indiquant si cle est présente dans l'ABR a.

3. ABR : racine 7, gauche 2 (enfants 1 et 5, 5 ayant pour enfants 3 et 6), droite 10 (enfants 8 et 9). a. À quel type de parcours correspond le résultat trié 1-2-3-5-6-7-8-9-10 ? b. Donner le parcours préfixe. c. Donner le parcours suffixe. d. Donner le parcours en largeur.

Exercice tiré du bac NSI Centres étrangers 2021 (Jour 1), sur les arbres binaires de recherche.

Rappel : pour chaque nœud X d'un ABR, le sous-arbre gauche contient des valeurs strictement inférieures à X, le sous-arbre droit des valeurs supérieures ou égales à X.

ABR construit en insérant, dans l'ordre : [26, 3, 42, 15, 29, 19, 13, 1, 32, 37, 30].

1. On insère 25 dans un nouveau nœud. Sous quel nœud s'insère-t-il, en fils gauche ou droit ? Détailler le raisonnement.

2. Le fils gauche du nœud de valeur 29 est vide. Quelles valeurs entières pourrait-il contenir, compte tenu des règles de l'ABR ?

3.

def Parcours(A):
    Afficher(A.valeur)
    Parcours(A.fils_gauche)
    Parcours(A.fils_droit)