Bac NSI 2025 Nouvelle-Calédonie jour 1

ABCEDF convient. Les sommets à distance 1 de A sont B, C et E ; ils doivent tous être visités avant D, qui est à distance 2. F est ensuite à distance 3. Dans les deux autres propositions, D apparaît avant E alors que E est un voisin direct de A.

Un parcours en largeur explore par couches de distance. L’ordre de B, C et E pourrait varier avec l’ordre des voisins ; parmi les trois séquences proposées, une seule respecte les couches.

F n’a qu’un voisin : D. Au départ, il ne connaît donc aucune route vers A, B, C ou E. Le tiret signifie qu’aucun routeur intermédiaire n’est nécessaire ; dans la classe de la partie B, cette convention sera représentée par None.

A reçoit de C une annonce « D est à 1 saut » et ajoute son propre saut vers C : D est à 2 sauts via C. L’annonce d’E donne le même coût. Comme le sujet ne remplace une route que par une route strictement plus courte, la première des deux annonces retenue décide du prochain routeur.

À ce premier échange synchrone, C et E n’annoncent encore que leurs voisins directs. Aucun des deux n’est relié directement à F : A ne connaît donc pas encore de route vers F. N’ajoutez pas un chemin que vous voyez sur le dessin avant que l’information ait pu se propager.

Les routes définitives sont acquises à l’issue de la troisième itération. Le trajet le plus court le plus long relie B à F : B → A → C → D → F, soit 4 sauts (on peut passer par E plutôt que C). L’initialisation connaît déjà les routes à un saut ; chaque échange synchrone gagne un saut : 2 sauts après l’itération 1, 3 après l’itération 2 et 4 après l’itération 3.

Pour lever toute ambiguïté de comptage : la troisième itération peut encore modifier une table ; la quatrième est la première itération qui constate qu’aucune modification n’est nécessaire. « Stabilisé après trois échanges » et « premier échange sans modification : le quatrième » décrivent donc le même déroulement.

La nouvelle arête crée A → E → F, de coût 2. D reste à deux sauts via C ou E ; les trois routes directes restent de coût 1. La nouvelle liaison n’est pas un routeur supplémentaire : on compte toujours les arêtes traversées.

def relie(self, autre):
    if autre not in self.voisins:
        self.voisins.append(autre)
        self.nb_sauts[autre] = 1
        self.prochain[autre] = None
        if self not in autre.voisins:
            autre.relie(self)

Le voisin est l’objet autre, pas son nom. Il devient aussi une clé des dictionnaires : sa distance vaut 1 et son prochain routeur intermédiaire vaut None. Le dernier appel construit la liaison dans l’autre sens.

Pourquoi la récursion s’arrête-t-elle ? Avant l’appel réciproque, autre a déjà été ajouté à self.voisins. Lorsque les rôles sont inversés, le test final voit que la première moitié de la liaison existe. Il ne déclenche pas une troisième construction. Le premier test empêche également les doublons lors d’un nouvel appel identique.

def relie_liste(self, lst):
    for routeur in lst:
        self.relie(routeur)

La boucle parcourt les objets de la liste et délègue chaque connexion à relie. Il serait fragile de ne modifier que voisins : on oublierait les deux dictionnaires et la connexion inverse. Réutiliser une méthode dont le contrat est déjà établi évite cette duplication.

Si lst est vide, la boucle n’effectue aucun appel. Si un routeur y figure deux fois, relie empêche les voisins en double.

C.relie_liste([D, E])
D.relie_liste([E, F])

A-B, A-C et A-E existent déjà. Il reste C-D, C-E, D-E et D-F. Ces deux appels les créent dans les deux sens ; aucun appel concernant B seul n’est nécessaire. D’autres regroupements sont possibles si et seulement si les sept arêtes du graphe sont présentes, sans arête supplémentaire.

def met_a_jour_table(self, autre):
    for r in autre.nb_sauts:
        if r != self:
            if (r not in self.nb_sauts or
                    self.nb_sauts[r] > autre.nb_sauts[r] + 1):
                self.nb_sauts[r] = autre.nb_sauts[r] + 1
                self.prochain[r] = autre

Pour atteindre r en passant par autre, on paie un saut jusqu’à ce voisin, puis les autre.nb_sauts[r] sauts qu’il annonce. Les trois compléments sont donc autre.nb_sauts[r] + 1, la même expression, puis autre.

Le test r != self évite d’ajouter une route vers soi via un détour. Le or est ici utile : si la destination est inconnue, Python n’évalue pas l’accès self.nb_sauts[r] qui provoquerait une erreur. Pour une destination connue, la comparaison doit être stricte afin de ne pas changer de prochain routeur à coût égal.

def itere_rip(self):
    for voisin in self.voisins:
        self.met_a_jour_table(voisin)

On reçoit une annonce de chaque objet contenu dans self.voisins. La méthode précédente sait comparer les routes ; cette méthode organise seulement la réception de toutes les annonces. Il faut parcourir les voisins, et non toutes les destinations déjà présentes dans la table, qui ne sont pas nécessairement directement connectées.

def iteration_rip(l_routeurs):
    for routeur in l_routeurs:
        routeur.itere_rip()

Il s’agit d’une fonction indépendante de la classe : elle ne reçoit pas de paramètre self. Chaque objet exécute sa propre méthode de réception.

Cette traduction met les tables à jour en place et dans l’ordre de la liste. Un routeur traité plus tard peut lire une table déjà améliorée durant ce même passage. Le nombre de passages du programme peut donc différer du nombre d’échanges synchrones de la partie A ; les routes finales restent celles de plus petit nombre de sauts.

def itere_rip(self):
    modifie = False
    for voisin in self.voisins:
        if self.met_a_jour_table(voisin):
            modifie = True
    return modifie

Le drapeau part de False. Dès qu’un voisin provoque une amélioration, il devient True et doit le rester jusqu’au retour. Les voisins suivants sont néanmoins tous traités. Une réception sans changement ne doit pas effacer le changement précédent.

Attention au court-circuit : modifie = modifie or self.met_a_jour_table(voisin) cesse d’appeler la méthode dès que modifie vaut True. Le bloc if proposé garantit au contraire que chaque annonce est réellement examinée.

modifie = True
while modifie:
    modifie = False
    for routeur in liste_routeurs:
        if routeur.itere_rip():
            modifie = True

Le premier True force un premier passage. Au début de chaque passage, on remet le drapeau à False ; un seul changement suffit à programmer un passage supplémentaire. La boucle s’arrête uniquement après avoir testé tous les routeurs sans obtenir de modification.

Dans ce réseau fini et sans panne, les mises à jour ajoutent des destinations ou diminuent strictement un nombre entier de sauts. On ne peut donc pas améliorer indéfiniment les tables. N’écrivez pas un return au milieu de ce programme principal et ne réinitialisez pas le drapeau pour chaque routeur.

On conserve les lignes dont l’altitude est au plus 2 000 m, puis on ne projette que la colonne nom. Le Lac Vert est à 1 266 m ; les trois autres lacs de l’extrait dépassent 2 000 m. Le résultat est une table d’une colonne et d’une ligne, pas une altitude.

Lac Blanc et Lacs Noirs. Le parking de Chamonix porte l’identifiant 1. Dans rando, les lignes de départ 1 mènent aux lacs 1 et 2. Dans lac, ces identifiants correspondent aux deux noms demandés.

Le numéro de la randonnée et celui du lac jouent des rôles différents : la randonnée 3 mène au lac 2. Suivre directement idR jusqu’à idL donnerait une association incorrecte.

SELECT coord_GPS
FROM parking
WHERE commune = 'Passy'
  AND altitude > 800
  AND altitude < 1000;

Les trois conditions doivent être vraies simultanément. Les comparaisons sont strictes : un parking situé exactement à 800 m ou 1 000 m ne serait pas retenu. Utiliser BETWEEN 800 AND 1000 serait ici incorrect, car cette expression inclut ses deux bornes.

Aucun des deux parkings de Passy affichés dans l’extrait ne convient, mais on travaille désormais sur la base entière. Cela n’autorise pas à conclure que la requête complète renverrait nécessairement une table vide.

SELECT DISTINCT l.nom
FROM parking AS p
JOIN rando AS r ON r.depart = p.idP
JOIN lac AS l ON l.idL = r.arrivee
WHERE p.commune = 'Cordon'
  AND p.altitude = 1300;

La première jointure relie le parking aux randonnées qui en partent ; la seconde donne les noms des lacs d’arrivée. Les alias p, r et l rendent explicite l’origine de chaque colonne, notamment altitude, qui existe dans deux relations.

DISTINCT évite d’afficher deux fois un même nom si plusieurs randonnées conduisent au même lac. Le filtre d’altitude doit porter sur le parking, pas sur le lac : confondre ces deux altitudes changerait le sens de la recherche.

INSERT INTO lac (idL, nom, altitude)
VALUES (42, 'Lac d''Anterne', 2059);

INSERT INTO rando (idR, depart, arrivee)
VALUES (100, 3, 42);

On crée le lac avant de le référencer dans une randonnée. Dans le cas contraire, arrivee = 42 désignerait une clé inexistante et violerait la contrainte d’intégrité référentielle. Le parking 3 est déjà présent : aucune insertion dans parking n’est demandée.

L’apostrophe du nom est doublée à l’intérieur de la chaîne SQL : d''Anterne. Ce sont deux apostrophes dans la requête pour une seule dans la valeur enregistrée. Expliciter les noms des colonnes évite aussi de dépendre d’un ordre supposé.

UPDATE lac
SET nom = 'Lac d''Anterne'
WHERE idL = 42;

La clé primaire cible exactement le lac ajouté. Sans WHERE, tous les lacs recevraient le même nom. Il ne faut ni supprimer la randonnée ni changer son arrivée : l’identifiant 42 reste le même, seul le nom est modifié.

DELETE FROM rando
WHERE depart = 28;

DELETE FROM parking
WHERE idP = 28;

On supprime d’abord les randonnées qui référencent ce parking, puis le parking lui-même. Cela évite de laisser un depart pointant vers une ligne disparue. Le sujet ne prévoit pas de suppression en cascade automatique : les deux requêtes rendent l’ordre explicite.

Ne supprimez pas les lacs d’arrivée de ces randonnées : ils continuent d’exister et peuvent rester accessibles depuis d’autres parkings. Une suppression doit se limiter à ce que demande le problème.

def get_parking(randos):
    parkings = []
    for rando in randos:
        if rando.depart not in parkings:
            parkings.append(rando.depart)
    return parkings

Le parcours fournit successivement un objet Rando. Son attribut depart est l’identifiant à ajouter. Dans l’exemple : on ajoute 1, puis 2, puis on ignore le second départ 1, déjà présent. La fonction garde donc l’ordre de première apparition.

Ajouter l’objet entier rando serait une erreur de type de résultat. La liste vide constitue un bon cas limite : le résultat doit être [] sans accès à un premier élément qui n’existe pas.

def get_nb_rando(parking, randos):
    nb = 0
    for rando in randos:
        if rando.depart == parking:
            nb = nb + 1
    return nb

On compare un identifiant à un identifiant : rando.depart == parking. Une randonnée d’arrivée 1 mais de départ 2 ne doit pas être comptée pour le parking 1. Le compteur est augmenté seulement si le prédicat est vrai, puis renvoyé après avoir examiné toutes les randonnées.

Si le parking n’apparaît jamais ou si la liste est vide, le compteur reste à 0. Ne placez pas return nb dans la boucle : cela arrêterait le comptage après le premier objet.

def nb_rando_par_parking(randos):
    resultat = {}
    for parking in get_parking(randos):
        resultat[parking] = get_nb_rando(parking, randos)
    return resultat

On réutilise les deux contrats précédents : get_parking fournit les clés sans doublon, puis get_nb_rando calcule leur valeur. Cette décomposition facilite une première solution correcte.

On peut aussi compter en un seul parcours :

def nb_rando_par_parking(randos):
    resultat = {}
    for rando in randos:
        parking = rando.depart
        if parking not in resultat:
            resultat[parking] = 0
        resultat[parking] += 1
    return resultat

Avant chaque incrément, la clé existe. Sur les départs 1, 2, 1, le dictionnaire devient successivement {1: 1}, {1: 1, 2: 1}, puis {1: 2, 2: 1}. La liste des randonnées seule ne permet pas de connaître les parkings de la base qui n’ont aucun départ : ils ne figurent pas dans ce résultat.

Une somme de chiffres entiers est un entier. Cinq cases contenant au plus 9 chacune donnent au maximum 5 × 9 = 45. Garder au moins un chiffre non nul sur une ligne donne une somme au moins égale à 1.

Le sujet choisit aussi des cibles de colonnes positives : il exclut donc les colonnes entièrement vidées. Cette exclusion des colonnes vides vient du choix des cibles ; la seule obligation de garder un chiffre par ligne ne suffirait pas à l’imposer. Il ne faut pas confondre ces deux conditions.

La plus petite cible est 2, en conservant uniquement le dernier chiffre. La plus grande est 25, en conservant tous les chiffres : 6 + 4 + 5 + 8 + 2 = 25. Vider toute la ligne donnerait 0, mais c’est interdit.

Ces bornes ne signifient pas que tous les entiers intermédiaires sont nécessairement atteignables pour n’importe quelle ligne. Les valeurs accessibles dépendent des sommes de sous-ensembles.

def extraireLigne(plateau, i):
    return plateau[i]

Le plateau est une liste dont chaque élément est déjà une ligne. Un seul accès suffit donc. Cette version renvoie la liste qui se trouve dans le plateau, pas une copie : modifier un élément de la ligne retournée modifierait aussi le plateau. Pour une copie indépendante, on pourrait écrire return plateau[i][:], mais le sujet ne l’exige pas.

def extraireColonne(plateau, i):
    colonne = []
    for ligne in plateau:
        colonne.append(ligne[i])
    return colonne

Cette fois, la colonne n’existe pas comme une sous-liste déjà rangée dans le plateau. On prend l’élément d’indice i dans chaque ligne et on construit une nouvelle liste. Il faut garder i fixe pendant que la ligne change.

Une compréhension est équivalente : return [ligne[i] for ligne in plateau]. Confondre plateau[i][j] et plateau[j][i] échange les rôles des axes : les exemples du sujet servent justement à repérer cette inversion.

[[0, 9, 2, 0, 2],
 [8, 0, 0, 0, 1],
 [7, 0, 3, 2, 0],
 [0, 4, 0, 0, 2],
 [0, 0, 0, 0, 4]]

Chaque ligne doit garder cinq positions : une case vidée devient 0, elle ne disparaît pas de la liste. La première ligne totalise 9 + 2 + 2 = 13 et la première colonne 8 + 7 = 15. Ces vérifications rapides confirment que les positions ont été conservées.

[[7, 9, 2, 3, 2],
 [8, 6, 3, 5, 1],
 [7, 7, 3, 2, 7],
 [6, 4, 5, 0, 2],
 [0, 0, 0, 0, 4]]

Les trois premières cibles de lignes sont 13, 9 et 12 : aucun chiffre de leurs lignes ne les dépasse. Pour L3, la cible 6 élimine le 8. Pour L4, la cible 4 élimine 8, 6, 8 et 8.

La consigne de cette question ne demande que le traitement des lignes. N’anticipez pas celui des colonnes : par exemple le 3 en position L0-C3 est encore présent ici, même si la cible de C3 vaut 2.

def regle1(plateau, ciblesLignes, ciblesColonnes):
    for i in range(5):
        tab = extraireLigne(plateau, i)
        cible = ciblesLignes[i]
        for j in range(5):
            if tab[j] > cible:
                plateau[i][j] = 0
    for j in range(5):
        tab = extraireColonne(plateau, j)
        cible = ciblesColonnes[j]
        for i in range(5):
            if tab[i] > cible:
                plateau[i][j] = 0

La cible de la ligne i est ciblesLignes[i]. Celle de la colonne j est ciblesColonnes[j]. Les variables de parcours gardent donc leur rôle : i pour la ligne, j pour la colonne.

La fonction modifie le plateau en place. Elle ne renvoie pas un nouveau plateau. Un appel doit s’écrire regle1(plateau, ciblesLignes, ciblesColonnes), sans affecter son résultat à plateau, faute de quoi on remplacerait celui-ci par None.

def unImpair(tab):
    nb = 0
    for valeur in tab:
        if valeur % 2 == 1:
            nb += 1
    return nb == 1

Le reste modulo 2 repère chaque valeur impaire. On compte ces valeurs, puis on teste si le compteur vaut exactement 1. Trois valeurs impaires donnent donc False, même si leur nombre est impair : la propriété demandée n’est pas « un nombre impair de valeurs impaires ».

assert unImpair([6, 4, 5, 8, 2]) is True
assert unImpair([0, 2, 4]) is False
assert unImpair([1, 3, 5]) is False
assert unImpair([]) is False

Les zéros représentant les cases vides sont pairs. Ils ne doivent pas augmenter le compteur.

def regle2(plateau, ciblesLignes, ciblesColonnes):
    for i in range(5):
        ligne = extraireLigne(plateau, i)
        cible = ciblesLignes[i]
        if cible % 2 == 0 and unImpair(ligne):
            for j in range(5):
                if plateau[i][j] % 2 == 1:
                    plateau[i][j] = 0
    for j in range(5):
        colonne = extraireColonne(plateau, j)
        cible = ciblesColonnes[j]
        if cible % 2 == 0 and unImpair(colonne):
            for i in range(5):
                if plateau[i][j] % 2 == 1:
                    plateau[i][j] = 0

Les deux conditions sont nécessaires : une cible paire et un seul impair encore présent. Si la cible est impaire, cet impair peut au contraire être indispensable. Si deux impairs sont présents, leur somme peut être paire : en éliminer un arbitrairement serait injustifié.

Les colonnes sont extraites après les modifications des lignes. Le test doit donc porter sur leur état actuel. La fonction conserve la même convention que regle1 : modification du plateau en place.

Le masque donné conserve les positions 0, 1 et 4, donc 1 + 2 + 2 = 5. Les autres masques sont :

[0, 1, 1, 0, 0]  # 2 + 3
[0, 0, 1, 0, 1]  # 3 + 2
[0, 0, 0, 1, 0]  # 5

Les deux chiffres 2 sont égaux mais occupent des positions différentes ; ils produisent deux masques distincts lorsqu’on les associe au 3. Pour vérifier l’exhaustivité : soit on garde le 5 seul, soit on utilise le 3 avec l’un des deux 2, soit on n’utilise ni 3 ni 5 et il faut alors garder 1 et les deux 2.

def somme(tab, masque):
    total = 0
    for i in range(5):
        total += tab[i] * masque[i]
    return total

Chaque produit vaut soit la valeur de la case, si le bit vaut 1, soit zéro. On additionne les cinq contributions. Dans l’exemple, on obtient 0 + 5 + 3 + 0 + 8 = 16. Une version avec if masque[i] == 1 est également correcte.

La liste et le masque ne sont pas modifiés : ils pourront être réutilisés pour d’autres tests. Vérifiez le masque tout nul, qui donne 0, et le masque tout à 1, qui donne la somme de la liste entière.

[1, 1, 0, 1, 0]

On décompose 26 = 16 + 8 + 2. Avec les poids 16, 8, 4, 2, 1 de gauche à droite, cela donne 1, 1, 0, 1, 0. L’ordre des bits est le même que celui des positions du masque.

Chaque bit possède deux valeurs possibles. Il existe donc 2⁵ = 32 configurations. En représentation non signée, elles vont de 00000, soit 0, à 11111, soit 16 + 8 + 4 + 2 + 1 = 31.

Il faut distinguer le nombre de valeurs représentables, 32, de la plus grande valeur, 31. Cet écart d’une unité reviendra dans la borne de range à la question 15.

def dec2bin(n):
    bits = [0, 0, 0, 0, 0]
    for i in range(4, -1, -1):
        bits[i] = n % 2
        n = n // 2
    return bits

Les restes des divisions successives par 2 donnent d’abord les bits de poids faible. On remplit donc la liste de droite à gauche. Pour 9, les restes successifs sont 1, 0, 0, 1, 0 ; placés aux indices 4, 3, 2, 1, 0, ils donnent la liste demandée.

range(4, -1, -1) inclut l’indice 0 et réalise toujours cinq tours, ce qui conserve les zéros en tête. Le quotient entier // est indispensable : une division réelle introduirait des nombres flottants.

assert dec2bin(0) == [0, 0, 0, 0, 0]
assert dec2bin(9) == [0, 1, 0, 0, 1]
assert dec2bin(31) == [1, 1, 1, 1, 1]

def masques_solutions(tab, cible):
    solutions = []
    for n in range(32):
        masque = dec2bin(n)
        if somme(tab, masque) == cible:
            solutions.append(masque)
    return solutions

On examine exhaustivement les 32 configurations, convertit chacune en masque, puis conserve celles dont la somme vaut la cible. range(32) inclut 31 : range(31) oublierait le masque qui garde tous les chiffres.

Il faut placer le retour après la boucle et conserver toutes les solutions, même si une première a déjà été trouvée. Chaque appel à dec2bin crée une liste indépendante : les masques enregistrés ne sont pas plusieurs références vers une unique liste modifiée au tour suivant.

Pour cinq cases, cela fait seulement 32 masques. Une généralisation à n cases examinerait 2ⁿ possibilités : cette recherche exhaustive devient rapidement coûteuse. Ce constat explique l’intérêt des règles de simplification, sans les confondre avec une preuve qu’elles résolvent tout.

def teste_solution(plateau, ciblesLignes, ciblesColonnes):
    for i in range(5):
        if sum(extraireLigne(plateau, i)) != ciblesLignes[i]:
            return False
    for j in range(5):
        if sum(extraireColonne(plateau, j)) != ciblesColonnes[j]:
            return False
    return True

Une seule somme incorrecte suffit à rejeter le plateau : le retour False peut donc être immédiat. Au contraire, on ne renvoie True qu’après avoir vérifié les cinq lignes et les cinq colonnes. Des lignes correctes ne garantissent pas des colonnes correctes.

Les cibles étant positives, une ligne entièrement vide échouerait automatiquement. Cette fonction vérifie exactement les sommes demandées. Elle ne peut pas vérifier que chaque case conservée vient du plateau d’origine : ce plateau n’est pas un paramètre de la fonction.

assert teste_solution(solution, ciblesLignes_ex, ciblesColonnes_ex)
assert not teste_solution(plateau_ex, ciblesLignes_ex, ciblesColonnes_ex)