Solution de Recherche dichotomique - Sujet 10 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche dichotomique du nombre entier n dans le tableau non vide tab.

Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le tableau, None sinon.

Exemples :

>>> recherche([2, 3, 4, 5, 6], 5)
3
>>> recherche([2, 3, 4, 6, 7], 5) # renvoie None

Exercice 2

EXERCICE 2 (10 points)

Le codage de César transforme un message en changeant chaque lettre en la décalant dans l’alphabet. Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, …, le X en A, le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’ …) ne sont pas codés.

La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre et renvoie la position de lettre dans la chaîne de caractères alphabet s’il s’y trouve.

La fonction cesar prend en paramètre une chaîne de caractères message et un nombre entier decalage et renvoie le nouveau message codé avec le codage de César utilisant le décalage decalage.

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    '''Renvoie la position de la lettre dans l'alphabet'''
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    '''Renvoie le message codé par la méthode de César
    pour le decalage donné'''
    resultat = ''
    for ... in message:
        if 'A' <= c and c <= 'Z':
            indice = (...) % 26
            resultat = resultat + alphabet[indice]
        else:
            resultat = ...
    return resultat

Compléter la fonction cesar.

Exemples :

>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !', 4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !', -5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

  • 1 <= len(tab) <= 10^6 (le tableau tab est non vide)
  • tab ne contient que des nombres entiers (int) et n est un nombre entier (int)
  • -10^9 <= tab[i] <= 10^9 et -10^9 <= n <= 10^9
  • tab est strictement croissant : tab[i] < tab[i+1] pour tout i valide, donc l’indice renvoyé est unique
  • La fonction renvoie None lorsque n n’appartient pas à tab
  • Un grand tableau est interrogé par plusieurs milliers de recherches successives : une solution en O(len(tab)) par recherche dépassera la limite de temps

Exercice 2

Contraintes :

  • 0 <= len(message) <= 10^4
  • message est une chaîne de caractères ASCII imprimables (lettres majuscules et minuscules, chiffres, espaces, ponctuation)
  • -10^3 <= decalage <= 10^3, decalage peut être négatif ou nul
  • Seuls les caractères compris entre 'A' et 'Z' sont décalés ; tout autre caractère est recopié tel quel
  • La chaîne renvoyée a la même longueur que message

Solution

Corrigé - Sujet 10

Exercice 1 - recherche dichotomique

L’idée. Le tableau est trié par ordre croissant : c’est cette information qu’il faut exploiter. Plutôt que de parcourir toutes les cases une par une, on regarde la valeur du milieu. Si c’est la bonne, on a fini. Sinon, comme le tableau est trié, on sait de quel côté chercher : si la valeur du milieu est trop petite, n ne peut être que dans la moitié droite ; si elle est trop grande, seulement dans la moitié gauche. À chaque tour, la zone de recherche est donc divisée par deux. Quand cette zone devient vide, c’est que n n’est pas dans le tableau : on renvoie None.

Un petit exemple. Pour recherche([2, 3, 4, 5, 6], 5), on cherche entre les indices 0 et 4 : le milieu est l’indice 2, qui vaut 4. C’est trop petit, on continue entre les indices 3 et 4 : le milieu est l’indice 3, qui vaut 5. C’est gagné, on renvoie 3.

def recherche(tab, n):
    debut = 0
    fin = len(tab) - 1
    # Tant que la zone de recherche n'est pas vide, on la coupe en deux
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == n:
            return milieu
        elif tab[milieu] < n:
            # Le tableau est trié : n ne peut être que dans la moitié droite
            debut = milieu + 1
        else:
            fin = milieu - 1
    return None

debut et fin délimitent la portion du tableau où n peut encore se trouver : au départ, le tableau entier. La boucle continue tant que debut <= fin, c’est-à-dire tant que cette portion contient au moins une case. On écrit debut = milieu + 1 (et non milieu) parce que la case du milieu vient d’être testée : la reprendre ferait tourner la boucle indéfiniment. Si on sort de la boucle, c’est que debut a dépassé fin : il ne reste plus aucune case à examiner, donc n est absent et le return None final s’exécute.

Attention : parcourir le tableau avec une simple boucle for pour comparer chaque valeur donnerait le bon résultat, mais ce n’est pas ce que demande l’énoncé, et c’est bien trop lent sur un grand tableau. La dichotomie divise la zone par deux à chaque tour : pour un million de valeurs, une vingtaine de tours suffisent.

Exercice 2 - codage de César

L’idée. On parcourt le message caractère par caractère et on construit petit à petit la chaîne resultat. Pour une lettre majuscule, on récupère sa position dans l’alphabet (0 pour 'A', 1 pour 'B', …) grâce à position_alphabet, on ajoute le décalage, et on prend le reste de la division par 26 : c’est ce % 26 qui fait « repartir au début » quand on dépasse le Z. La nouvelle position sert alors d’indice dans la chaîne alphabet. Pour tout autre caractère (espace, ponctuation, chiffre, minuscule), on le recopie tel quel.

Un petit exemple. Avec un décalage de 4, la lettre 'Y' est en position 24 ; 24 + 4 = 28, et 28 % 26 = 2, donc alphabet[2], c’est-à-dire 'C'.

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    '''Renvoie la position de la lettre dans l'alphabet'''
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    '''Renvoie le message codé par la méthode de César
    pour le decalage donné'''
    resultat = ''
    for c in message:
        if 'A' <= c and c <= 'Z':
            # Le modulo 26 ramène dans l'alphabet, même si decalage est négatif
            indice = (position_alphabet(c) + decalage) % 26
            resultat = resultat + alphabet[indice]
        else:
            resultat = resultat + c
    return resultat

Il n’y avait que trois trous à remplir. for c in message: donne le nom c au caractère courant, celui que la ligne suivante utilise déjà. indice = (position_alphabet(c) + decalage) % 26 est le cœur du codage. Enfin, dans le else, resultat = resultat + c recopie le caractère sans le modifier : c’est ce qui laisse intacts les espaces, le point et le point d’exclamation des exemples.

Un point utile : en Python, le reste d’une division par 26 est toujours compris entre 0 et 25, même pour un nombre négatif. Par exemple (1 - 5) % 26 vaut 22. C’est pour cela que le deuxième exemple de l’énoncé, avec decalage = -5, fonctionne sans écrire une seule ligne de plus : le décodage n’est qu’un codage avec un décalage négatif.