Bac NSI 2026 Polynésie jour 1

def suite(n):
    if n < 2:
        valeur = n
    else:
        valeur = suite(n - 1) + suite(n - 2)
    return valeur

Pour n = 0 ou 1, la valeur est n. Pour n ≥ 2, la relation de récurrence est traduite directement. Les appels diminuent jusqu’à l’un des deux cas de base. On suppose n entier naturel, comme pour l’indice de la suite.

Pour suite(4), le premier appel demande suite(3) et suite(2). À son tour, suite(3) redemande suite(2), ce qui illustre déjà un calcul répété. Les cas de base renvoient les valeurs de la suite et ne font pas d’addition entre termes. La terminaison s’appuie sur la diminution stricte de n, pour un indice naturel.

def nb_additions_suite(n):
    if n < 2:
        return 0
    return 1 + nb_additions_suite(n - 1) + nb_additions_suite(n - 2)

L’addition des deux termes de la suite compte pour 1 ; il faut y ajouter les additions des deux sous-appels. Ce programme calcule le décompte p(n). Ses propres additions ne sont pas celles que l’on mesure dans suite : on applique simplement la récurrence fournie.

p(2) = 1, p(4) = 4 et p(7) = 20. Par exemple p(4) = 1 + p(3) + p(2) = 1 + 2 + 1 ; p(7) = 1 + 12 + 7. Calculer les valeurs successives évite de redessiner tout l’arbre d’appels.

À partir d’un cache neuf [0, 1], chaque terme d’indice 2 à n n’est calculé qu’une fois, soit n - 1 additions. Les valeurs manquantes sont donc 4, 5, 6. Le paramètre par défaut mutable du code conserve cependant les résultats entre appels : si on lance successivement suite2(2), suite2(3), etc. sans réinitialiser la liste, chaque nouvel indice ne demande qu’une addition. Le tableau du sujet suppose des calculs isolés, chacun avec le cache initial.

Une façon simple de lever l’ambiguïté lors d’un test consiste à appeler suite2(n,[0,1]) avec une nouvelle liste explicitement fournie pour chaque n. Ainsi le tableau compare des conditions initiales identiques. Pour éviter le partage implicite d’un paramètre mutable, une version d’application pourrait utiliser un paramètre par défaut None et créer [0,1] dans la fonction lorsque le cache n’est pas fourni.

La mémoïsation, technique de programmation dynamique, conserve chaque terme calculé dans valeurs_calculees. Un terme déjà connu se lit directement au lieu d’être recalculé. La récursion naïve répète les mêmes sous-problèmes et son coût croît exponentiellement ; le nombre d’additions de la version mémorisée croît linéairement à cache neuf. Par exemple U₇ exige 20 additions naïves, contre 6 mémorisées.

def suite3(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Au début de l’itération k, a = Uₖ et b = Uₖ₊₁. L’affectation simultanée calcule les nouvelles valeurs avec les anciennes. Après n tours, a = Uₙ. Pour n = 0, la boucle ne s’exécute pas et renvoie bien 0. Cette version fait n additions ; on pourrait réduire à n - 1 pour n ≥ 2 avec un traitement séparé des cas de base.

Une affectation séquentielle a=b puis b=a+b n’aurait pas le même effet, car le second calcul lirait le nouveau a. L’affectation simultanée évalue d’abord les deux expressions avec les anciennes valeurs. Une variable temporaire serait une autre solution correcte. Le tableau montre qu’après quatre tours, a contient bien U₄=3.

Elle conserve seulement deux valeurs au lieu d’une liste de tous les termes et évite l’empilement des appels récursifs, donc le risque d’atteindre la limite de récursion de Python. Par rapport à suite2, son ordre de temps reste linéaire en nombre d’additions, mais le nombre de variables de travail est constant. Les entiers eux-mêmes grandissent avec n : « mémoire constante » désigne ici le nombre de cases, pas un nombre constant de bits.

C’est une liste de dictionnaires. Chaque dictionnaire contient une seule association : une clé de type chaîne (le prénom) et une valeur de type chaîne (le téléphone). Les numéros sont des textes pour conserver leurs zéros initiaux et leurs espaces.

Pour chaque nœud, tous les prénoms du sous-arbre gauche le précèdent et tous ceux du sous-arbre droit le suivent. Ainsi Antoine, Benjamin, Emilie et Eric précèdent Olivier ; Roxanne, Sophie, Victor, Yann et Zoé le suivent. La propriété est aussi vraie à l’intérieur : Emilie précède Eric, tandis qu’Eric suit Benjamin. Vérifier seulement les deux enfants de la racine ne suffirait pas.

Racine : Olivier. Feuilles : Antoine, Emilie, Roxanne, Zoé, car elles n’ont aucun enfant. Eric et Yann ne sont pas des feuilles même s’ils n’ont qu’un enfant.

Hauteur 5 ; taille 10. Le plus long chemin est Olivier → Sophie → Victor → Yann → Zoé, soit cinq nœuds avec la convention du sujet. La taille compte tous les nœuds, un par contact.

La recherche suit une seule branche, en éliminant à chaque comparaison un sous-arbre entier. Son coût dépend de la hauteur h, soit O(h), contre O(n) pour rechercher un prénom dans la liste non triée de petits dictionnaires. Un ABR équilibré donne O(log n), mais un ABR dégénéré peut encore demander O(n). L’ordre n’assure pas à lui seul l’équilibrage.

Dans cet arbre, chercher Emilie compare Olivier, Benjamin, Eric puis Emilie : quatre nœuds sont visités, alors qu’une recherche séquentielle dans la liste de départ atteint ce contact en huitième position. Cet exemple montre le gain possible sans en faire une garantie universelle. Insérer des clés déjà triées dans un ABR non équilibré créerait une longue chaîne et ferait disparaître le gain logarithmique.

    Eric
    /
 Emilie

Il contient Eric comme racine et Emilie comme enfant gauche. Le sous-arbre inclut les descendants, pas seulement le fils direct.

B. Benjamin reçoit Antoine à gauche et Eric à droite ; Eric reçoit Emilie à gauche. A inverse Eric et Emilie. C mélange des tuples et des nœuds à des emplacements où le constructeur attend un Contact et des sous-arbres.

noeud.droite = self.inserer_recursive(noeud.droite, contact)  # 14
if prenom == noeud.contact.prenom:                         # 23
    return noeud.contact.num_tel
elif prenom < noeud.contact.prenom:
    return self.trouver_recursive(noeud.gauche, prenom)    # 26

L’insertion doit réaffecter le sous-arbre renvoyé, notamment lorsqu’un emplacement vide reçoit un nouveau nœud. La recherche teste l’égalité avant de choisir une branche et transmet avec return le résultat du sous-appel. Le code suppose, comme annoncé, que les prénoms insérés sont distincts ; sans cette précondition, le else d’insertion accepterait un doublon à droite.

Pour insérer Emilie, la comparaison avec Olivier choisit gauche ; avec Benjamin, elle choisit droite ; avec Eric, elle choisit gauche. Cet enfant est None, donc on crée le nœud. Les affectations successives replacent les racines des sous-arbres renvoyés à leur bon emplacement. Pour une recherche absente comme Adrien, on descend jusqu’à un None, puis ce résultat remonte inchangé grâce aux return.

def recherche_contact(prenom_recherche):
    print("Prénom recherché :", prenom_recherche)
    numero = contact_manager.trouver_contact(prenom_recherche)
    if numero is None:
        print("Contact '" + prenom_recherche + "' introuvable")
    else:
        print(prenom_recherche + " : " + numero)

La recherche est appelée une seule fois et son résultat est conservé. On distingue explicitement None, marqueur d’absence, d’un numéro stocké sous forme de chaîne. Cette fonction affiche ; elle n’a pas besoin de renvoyer le numéro.

Le parcours en profondeur infixe : sous-arbre gauche, nœud, sous-arbre droit. Les clés de gauche sont plus petites que le nœud et celles de droite plus grandes. En appliquant récursivement le même ordre, on obtient toute la liste triée.

affichage_contacts_trie(noeud.gauche)
print(noeud.contact.prenom + " : " + noeud.contact.num_tel)

Le cas None ne produit aucun affichage. Pour chaque nœud non vide, on traite à gauche, affiche son contact puis utilise l’appel à droite déjà fourni. Les numéros restent associés à leurs prénoms : on ne trie pas séparément les deux listes.

Sur le sous-arbre Benjamin, l’exécution descend d’abord sur Antoine, l’affiche, revient afficher Benjamin, puis visite le sous-arbre Eric. Dans celui-ci, Emilie est affichée avant Eric. On obtient donc Antoine, Benjamin, Emilie, Eric. Le cas None se contente de revenir à l’appel précédent : il représente une branche absente et ne doit rien afficher.

self.base_donnees = {}
# Dans ajouter_question_reponse :
self.base_donnees[question] = reponse

Les accolades vides créent un dictionnaire, pas une liste. Une affectation à une clé ajoute une association ou remplace sa valeur si cette même question existait déjà.

Bot1 = Chatbot()
Bot1.ajouter_question_reponse(
    "Bonjour, comment vas-tu ?",
    "Bonjour, je vais bien, merci.")

L’appel au constructeur crée l’instance. La méthode agit ensuite sur cette instance : Python transmet automatiquement Bot1 comme self.

reponse = Bot1.repondre("Bonjour, comment vas-tu ?")
print(reponse)

La réponse renvoyée est Bonjour, je vais bien, merci.. La recherche est exacte : le programme ne comprend pas les variantes de formulation et l’accès à une question absente provoquerait KeyError. Ajouter une réponse par défaut serait une amélioration distincte de la consigne.

SELECT consulte sans modifier. INSERT crée une ligne. UPDATE modifie des lignes existantes, généralement sélectionnées par WHERE.

Une clé primaire est un attribut ou un ensemble d’attributs choisi pour identifier de façon unique chaque ligne d’une table. Ses valeurs ne peuvent pas être nulles et deux lignes ne peuvent pas partager la même valeur de clé. Une clé composée s’interprète comme un ensemble, pas comme plusieurs identifiants séparés.

id, à condition qu’il soit attribué de façon unique et non nulle. Il identifie une interaction indépendamment de son texte. Un même mot-clé peut concerner plusieurs questions ; une réponse comme « Oui » peut aussi se répéter. L’identifiant reste stable si le texte est corrigé.

SELECT question
FROM questions_reponses
WHERE mot_cle = 'python';

On compare le champ de classement au mot-clé demandé. On ne recherche pas le mot python à l’intérieur du texte de la question, car ce n’est pas ce que demande la consigne.

Le résultat SELECT question est une projection : même si la table contient identifiant, réponse et mot-clé, seuls les textes de questions apparaissent. WHERE est appliqué au champ mot_cle. Une question contenant le mot Python mais classée sous un autre mot-clé ne serait pas retenue par cette requête, conformément au besoin formulé.

INSERT INTO questions_reponses (id, question, reponse, mot_cle)
VALUES (15, 'Date de la bataille de Marignan ?', '1515', 'Histoire');

15 identifie l’enregistrement ; « 1515 » est le texte de la réponse. Écrire les colonnes rend explicite l’association de chaque valeur et évite de dépendre implicitement de l’ordre physique du schéma.

UPDATE questions_reponses
SET reponse = 'Oui'
WHERE id = 12;

La condition cible une seule interaction par son identifiant. Sans WHERE, toutes les réponses deviendraient « Oui ». On ne modifie ni la question ni son mot-clé.

Le parcours en largeur, de gauche à droite dans chaque niveau : d’abord la racine, ensuite ses enfants, puis les quatre petits-enfants.

algo, bot, chatbot, IA, informatique, programmation, python. On visite gauche, racine, droite à chaque nœud. Le sous-arbre de bot est donc entièrement visité avant IA.

Pour ne pas se perdre, appliquez la règle à un seul sous-arbre : le nœud bot produit algo, bot, chatbot. Le nœud programmation produit informatique, programmation, python. La racine IA se place entre ces deux groupes. Les parcours se déterminent par la structure des liens ; il n’est pas nécessaire de comparer les mots pendant un parcours.

algo, chatbot, bot, informatique, python, programmation, IA. Cette fois, chaque racine est visitée après ses deux sous-arbres : gauche, droite, nœud. IA est donc le dernier élément.

Le parcours infixe, puisque l’arbre est déclaré ordonné alphabétiquement. Attention à la majuscule de IA : l’ordre alphabétique usuel de l’exercice ignore ici la casse. Python compare directement les chaînes selon les points de code Unicode, où "IA" < "algo". Avec cette comparaison native, le dessin ne serait pas un ABR valide. Pour réaliser le modèle alphabétique annoncé, on peut normaliser les clés avec casefold() au moment des comparaisons.

if arbre is None or arbre.cle == cle:
    return arbre
if cle < arbre.cle:
    return recherche(arbre.gauche, cle)
else:
    return recherche(arbre.droit, cle)

Les trois compléments attendus sont cle, gauche, droit. Le premier test arrête la recherche sur un arbre vide ou une égalité. L’attribut s’appelle ici droit, sans e, contrairement à l’exercice précédent.

Le code imprimé place cependant la fonction à l’intérieur de la classe tout en appelant recherche sans qualification. Pour disposer d’une version directement exécutable, on peut définir cette fonction à l’extérieur de la classe, ou employer une méthode statique et appeler Noeud.recherche(...). Pour l’arbre donné avec IA, les comparaisons doivent aussi respecter l’ordre alphabétique sans casse :

def recherche(arbre, cle):
    if arbre is None or arbre.cle.casefold() == cle.casefold():
        return arbre
    if cle.casefold() < arbre.cle.casefold():
        return recherche(arbre.gauche, cle)
    return recherche(arbre.droit, cle)

La recherche sur une clé absente doit aboutir à None, tandis qu’une clé égale à celle du nœud courant renvoie ce nœud lui-même. Les deux tests de base se font avant l’accès aux enfants. La normalisation de casse doit être la même à l’insertion et à la recherche : corriger seulement la comparaison de recherche sur un arbre construit avec un autre ordre ne suffirait pas à restaurer l’invariant d’ABR.