Bac NSI 2025 centres étrangers groupe 1 jour 1

balise12 = Balise(12, ['vert', 'noir'])

La figure place 12 sur les parcours vert et noir, pas sur le rouge. Le constructeur reçoit le numéro puis la liste de couleurs ; il initialise lui-même voisines et visitee. L’ordre des deux couleurs n’affecte pas les tests d’appartenance.

balise9.voisines = [balise8, balise11, balise12]

La balise 9 est reliée à 8,11 et 12. Les autres affectations de l’annexe ont déjà enregistré les liaisons dans l’autre sens. Les éléments sont des objets Balise ; mettre les entiers 8,11,12 empêcherait ensuite d’accéder à leurs attributs.

[2, 5, 6]

La compréhension parcourt les trois objets voisins dans l’ordre de la liste et extrait leur num_balise. Elle renvoie une nouvelle liste d’entiers sans modifier le graphe.

['noir', 'vert']

methode2 reconstruit la liste en supprimant les occurrences de rouge ; il reste noir. methode3 ajoute vert à la fin. On ne trie pas les couleurs et l’ajout n’est pas un remplacement. Comme indiqué dans l’énoncé, on rétablit ensuite la balise 4 originale pour traiter la suite.

def itineraire(balise_debut, balise_fin, couleur):
    assert couleur in balise_debut.couleurs_balise
    assert couleur in balise_fin.couleurs_balise
    balise = balise_debut
    chemin = [balise]
    while balise.num_balise != balise_fin.num_balise:
        for b in balise.voisines:
            if couleur in b.couleurs_balise and b not in chemin:
                balise = b
                chemin.append(balise)
    return [b.num_balise for b in chemin]

Les compléments sont balise_fin.num_balise, b.couleurs_balise, chemin et b. Le chemin stocke des objets afin de tester qu’un voisin n’a pas déjà été choisi ; la compréhension finale transforme ces objets en numéros. Pour vert, on suit 1,3,6,7,10,12. Pour noir, on suit 1,3,6,4,5,10,12.

Ce squelette fonctionne pour les parcours colorés de ce graphe, qui fournissent la continuation attendue. Il ne constitue pas une recherche de chemin générale : dans un autre graphe, plusieurs voisins admissibles ou une impasse pourraient provoquer un mauvais choix ou une boucle sans progrès. Une version générale devrait prévoir un échec et éventuellement un retour en arrière.

[1, 2, 4, 5, 10, 7, 6, 3, 11, 9, 8, 12]

On s’enfonce jusqu’à 3, qui ne possède plus de voisin non découvert. On revient alors à 6 pour visiter 11, puis 9,8 et 12. La liste donne l’ordre des premières découvertes ; les retours physiques par des balises déjà poinçonnées ne sont pas ajoutés comme de nouvelles visites. Marquer les sommets évite de tourner dans les cycles du graphe.

balise4.voisines = [(balise2, 13), (balise5, 21), (balise6, 15)]

La première composante reste une instance Balise ; la seconde est un temps moyen en minutes. Les chemins sont plats et les arêtes non orientées : les temps sont les mêmes dans les deux sens.

Le résultat est 5. Les voisines 5,7 et 12 sont accessibles en 6,12 et 7 minutes ; la durée minimale est 6. mystere renvoie l’objet balise 5, puis l’accès à num_balise fournit l’entier 5. Si aucun voisin n’était disponible, mystere renverraitNone et cet accès à num_balise ne serait plus possible.

[1, 2, 4, 6, 11, 9, 12]

Le total de ces décisions locales est61 minutes. À4, on préfère 6 à 5 ; à 6, on préfère 11 à 7 et 3 ; à 9, on préfère 12 à 8. Aucun retour vers une balise visitée n’est autorisé. Ce trajet ne prétend pas être le plus rapide globalement :1-3-6-11-9-12 coûte51 minutes.

def itineraire_trail(balise_debut, balise_fin):
    balise_debut.visitee = True
    balise = balise_debut
    chemin = [balise]
    while balise_fin not in chemin:
        prochaine = mystere(balise)
        if prochaine is not None:
            prochaine.visitee = True
            balise = prochaine
            chemin.append(balise)
        else:
            return None
    return [b.num_balise for b in chemin]

mystere choisit le prochain objet. Il faut alors le marquer, mettre à jour la balise courante et ajouter l’objet au chemin. Oublier le marquage permettrait des retours ; oublier la mise à jour de balise répéterait les choix depuis le même sommet. Le casNone correspond à une impasse pour cette stratégie. Il ne prouve pas qu’aucun autre trajet n’existe dans le graphe.

Le marquage modifie les objets partagés. Il faut donc les réinitialiser avant une nouvelle simulation, conformément à l’hypothèse du sujet. Lorsque départ et arrivée sont identiques, la boucle ne s’exécute pas et la fonction renvoie la liste contenant ce seul numéro.

PropositionA : algorithme glouton.

Avantage : chaque décision locale est simple et n’exige pas d’énumérer tous les itinéraires, ce qui réduit souvent le travail de recherche. Inconvénient : la succession de meilleurs choix locaux ne garantit pas une solution optimale globale, ni même de trouver une solution lorsqu’il en existe une. Ici, le parcours de 61 minutes est plus long que celui de 51 minutes indiqué précédemment. Un exemple concret montre mieux la limite qu’une affirmation générale.

v vaut 6 : la ligne d’indice 1 est [8,14,6,7], puis l’indice 2 y désigne le troisième élément. Les deux indices commencent à 0.

def plateau_init(n, m, cartes):
    shuffle(cartes)
    plateau = []
    for i in range(n):
        plateau.append([cartes[i + j*n] for j in range(m)])
    return plateau

Les indices utilisés sont i+j×n, pour 0≤i< n et 0≤j< m. Ils couvrent une seule fois les n×m premières positions, en remplissant les colonnes par paquets de n. C’est une disposition différente d’un parcours ligne par ligne, mais elle respecte les dimensions et le tirage sans remise. Deux cartes peuvent porter la même valeur : sans remise signifie que l’on ne réutilise pas une même position de la liste de cartes.

def cartes_voisines(n, m, i, j):
    voisines = []
    for i2 in range(i - 1, i + 2):
        for j2 in range(j - 1, j + 2):
            if (i2, j2) != (i, j) and i2 in range(n) and j2 in range(m):
                voisines.append((i2, j2))
    return voisines

Les deux boucles explorent le carré 3×3 centré sur la carte. Trois filtres écartent la carte elle-même, les lignes hors plateau et les colonnes hors plateau. Un coin d’un plateau assez grand possède trois voisines ; une carte intérieure en possède huit. Le tuple(i 2, j 2) conserve ensemble ligne et colonne.

e 1 est valide et vaut 9+8+6+7=30. e 2 n’est pas valide : de(1,2) à(2,0), on se déplace de deux colonnes, donc les cartes ne sont pas voisines. e 3 n’est pas valide : la colonne 4 n’existe pas dans un plateau dont les colonnes sont indexées 0 à 3. Il ne faut pas simplement additionner les valeurs sans vérifier les règles de déplacement.

def chaine_evalue(plateau, chaine):
    total = 0
    for i, j in chaine:
        total += plateau[i][j]
    return total

Le déballage for i,j in chaine rend les coordonnées explicites ; on ajoute la valeur de chaque case. La fonction suppose une chaîne valide comme son contrat le demande. Elle ne vérifie ni les voisinages ni les répétitions : ces propriétés sont garanties par la construction dans explore. La chaîne vide donnerait 0, même si les solutions du jeu commencent par une carte.

La file traite d’abord toutes les chaînes d’une carte, puis de deux cartes, puis de trois, etc. La première chaîne dont la somme atteint la cible possède donc une longueur minimale. Une exploration en profondeur peut s’enfoncer dans une chaîne longue et trouver une solution avant d’avoir essayé une autre branche courte. La largeur ne minimise pas la somme : elle organise les candidats par nombre de cartes.

def explore(plateau, cible):
    n, m = len(plateau), len(plateau[0])
    a_visiter = file_init()
    for i in range(n):
        for j in range(m):
            file_ajoute(a_visiter, [(i, j)])
    while not file_est_vide(a_visiter):
        chemin = file_retire(a_visiter)
        if chaine_evalue(plateau, chemin) == cible:
            return chemin
        i0, j0 = chemin[-1]
        for i, j in cartes_voisines(n, m, i0, j0):
            if (i, j) not in chemin:
                file_ajoute(a_visiter, chemin + [(i, j)])
    return None

Toutes les positions de départ sont mises en file avant la boucle. Chaque élément de la file est un chemin complet ; on le prolonge par chaque voisine non encore dans ce chemin. Un marquage global des cases serait incorrect ici : la même case peut appartenir à plusieurs candidats avec des sommes et des historiques différents. Seule sa répétition dans une même chaîne est interdite.

L’expression chemin + [(i,j)] crée une nouvelle liste pour chaque branche. Modifier chemin en place ajouterait successivement plusieurs voisines au même candidat et mélangerait les branches. La file FIFO garantit l’ordre des longueurs. La terminaison vient du nombre fini de chemins sans répétition, mais leur quantité peut être très grande ; ce code ne promet pas une recherche rapide pour tous les plateaux.

Créer une liste de solutions vide avant la boucle. Lorsqu’un chemin atteint la cible, l’ajouter à cette liste au lieu de le retourner immédiatement. Continuer le traitement de la file jusqu’à son épuisement, puis retourner la liste, éventuellement vide. On conserve la contrainte de non-répétition dans chaque chemin.

La question demande tous les chemins solutions, pas seulement les plus courts. Sur des cartes strictement positives comme le plateau donné, prolonger une somme déjà égale à la cible ne peut plus fournir une autre solution, mais cette coupure doit être justifiée par la positivité. L’extension parle d’entiers : avec des zéros ou des négatifs, il peut être nécessaire de continuer à prolonger une solution pour en trouver une plus longue. Ne pas appliquer un élagage sans vérifier les valeurs autorisées.

print(enregistrement['latitude'])

Le nom de clé est une chaîne entre guillemets. L’accès utilise le dictionnaire, sans supposer une position numérique des champs.

('2024-06-27', '23:36:01')

La première boucle copie les indices 0 à 9, soit la date. La seconde copie les indices 11 à 18, en sautant le séparateurT à l’indice 10. Le résultat est un tuple de deux chaînes ; les fractions de seconde et l’indicationZ ne sont pas conservées. Le code extrait un format fixe, sans convertir de fuseau horaire.

len(frames) vaut 4 : il y a quatre enregistrements. len(frames[1]) vaut 5 : le second enregistrement est un dictionnaire possédant cinq clés. La longueur d’un dictionnaire compte ses associations, pas le nombre de caractères de ses valeurs.

def detecter_anomalie(enregistrement):
    return enregistrement['altitude'] < 0 or enregistrement['altitude'] > 35000

Les deux anomalies sont alternatives, d’où or. Les valeurs 0 et 35000 restent acceptées : les comparaisons sont strictes. L’exemple de la sonde 700 à60000m renvoieTrue. Utiliser and rendrait la condition impossible, puisqu’une même altitude ne peut pas être à la fois négative et supérieure à 35000.

def liste_num_serie(frames):
    numeros = []
    for enregistrement in frames:
        numero = enregistrement['num_serie']
        if numero not in numeros:
            numeros.append(numero)
    return numeros

La liste numeros mémorise les identifiants déjà rencontrés. La seconde mesure de 623 n’ajoute rien, tandis que 500 et 700 créent de nouvelles entrées. On ne modifie pas frames. Un ensemble éliminerait aussi les doublons, mais le retour demandé conserve l’ordre des premières apparitions ; cette version le rend explicite.

def distance_totale(dep):
    total = 0
    for i in range(len(dep) - 1):
        total += distance_haversine(dep[i], dep[i + 1])
    return total

Une trajectoire de n positions possède n−1 segments consécutifs. Le dernier indice utilisé dans la boucle vaut n−2, de sorte que i+1 reste au plus n−1. On ne relie pas directement chaque point au premier : cela mesurerait autre chose que le chemin parcouru. Les trajectoires vides ou d’une seule position donnent naturellement 0.

Avec les exemples fournis, les trois premières positions donnent 46,1 km ; l’ajout de la quatrième donne 73,5 km. La fonction ne doit pas reconvertir cette unité ni arrondir chaque segment sans que le contrat de distance_haversine le demande.

sonde623 = Sonde(623,38.38825,27.09004,'2024-06-27',
    Sonde(None,None,None,None,None,None),
    Sonde(None,None,None,None,None,None))

Les enfants sont des arbres vides représentés par des instances Sonde, conformément à la convention annoncée. Mettre directement None comme enfants d’un nœud non vide ferait ensuite échouer les appels récursifs à rechercher sur une branche absente. Les deux instances vides ont leurs six attributs à None.

900 est supérieur à 623 puis 700 : il devient le fils droit de 700.650 est supérieur à 623 mais inférieur à 700 : il devient le fils gauche de 700.300 est inférieur à 623 puis 500 : il devient le fils gauche de 500. L’ordre d’insertion ne déplace pas les nœuds existants, en particulier 575 reste le fils droit de 500.

Le parcours infixe : sous-arbre gauche, racine, sous-arbre droit. Dans un ABR, tous les numéros du sous-arbre gauche sont plus petits que la racine et ceux du droit plus grands. L’ordre obtenu après les insertions est 300,500,575,623,650,700,900.

def rechercher(self, numero):
    if self.est_vide():
        return None
    if numero == self.num_serie:
        return self
    elif numero < self.num_serie:
        return self.gauche.rechercher(numero)
    else:
        return self.droit.rechercher(numero)

Le cas vide doit précéder toute comparaison de numéro, car un arbre vide porte num_serie=None. Une égalité renvoie l’objet courant, pas son seul numéro. Sinon, la propriété de l’ABR permet d’écarter un sous-arbre entier. Pour chercher 650, on compare à 623 puis 700, puis on trouve 650 à gauche. Pour un numéro absent, la descente atteint un objet vide et renvoieNone.

La recherche prend un nombre d’étapes proportionnel à la hauteur de l’arbre. Elle est rapide sur un arbre équilibré, mais peut devenir linéaire dans un arbre en chaîne : la structure d’ABR ne garantit pas à elle seule l’équilibrage.

La méthode appelle rechercher sur l’un de ses sous-arbres. Le problème est de même nature, mais porte sur une partie strictement plus petite de l’arbre. Les cas de base sont l’arbre vide et le numéro trouvé. La descente termine sur un arbre fini sans cycle.

id_abonne convient : il identifie chaque membre du club par une valeur unique et non nulle. Les noms et prénoms peuvent être partagés par plusieurs personnes ; leur apparente unicité dans l’extrait ne constitue pas une garantie générale. Une contrainte de clé primaire formalise cette identification dans la base.

num_serie référence sonde.num_serie ; id_abonne référence abonne.id_abonne. Elles relient chaque récupération à une sonde et à la personne qui l’a retrouvée. ref identifie la récupération elle-même et joue le rôle de clé primaire ; ce n’est pas la même fonction.

Les lignes visées sont celles d’identifiants 32 et 24 : Détoile, Diane et Girard, Antoine. Leur ordre n’est pas garanti sans ORDER BY.

Attention au nom de table : l’extrait la nomme abonne, tandis que la requête écrit Abonnes au pluriel. Sur une base créée exactement avec le schéma reproduit, cette requête échouerait faute de table correspondante. La requête cohérente est :

SELECT nom, prenom FROM abonne WHERE id_abonne > 20;

INSERT INTO info_recuperation (ref,num_serie,id_abonne,date_recup,latitude,longitude)
VALUES (14,480,24,'2024-07-10',47.230,12.244);

Antoine Girard porte l’identifiant 24 dans abonne. Les clés 480 et 24 existent déjà dans leurs tables, ce qui permet la création de cette récupération. Les noms de colonnes protègent contre une inversion de latitude et longitude. Le nom InfosRecuperation employé dans la consigne est remplacé par celui du schéma reproduit.

SELECT s.num_serie, a.nom, r.date_recup
FROM sonde AS s
JOIN info_recuperation AS r ON r.num_serie = s.num_serie
JOIN abonne AS a ON a.id_abonne = r.id_abonne;

info_recuperation sert de relation de liaison : elle désigne à la fois la sonde et l’abonné. Les alias abrègent les noms sans changer les tables. Une sonde sans récupération n’apparaît pas dans cette jointure interne ; cela correspond à l’objectif de référencer les radiosondes retrouvées. Plusieurs récupérations éventuelles produiraient plusieurs lignes, sauf contrainte supplémentaire que le sujet ne fournit pas.