Solution de Multiplication par additions - Sujet 09 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Programmer la fonction multiplication, prenant en paramètres deux nombres entiers relatifs n1 et n2, et qui renvoie le produit de ces deux nombres.

Les seules opérations autorisées sont l’addition et la soustraction.

>>> multiplication(3, 5)
15
>>> multiplication(-4, -8)
32
>>> multiplication(-2, 6)
-12
>>> multiplication(-2, 0)
0

Exercice 2

EXERCICE 2 (10 points)

On s’intéresse dans cet exercice à la recherche dichotomique dans un tableau trié d’entiers.

Compléter la fonction suivante en respectant la spécification.

def dichotomie(tab, x):
    """
    tab : tableau d'entiers trié dans l'ordre croissant
    x : nombre entier
    La fonction renvoie True si tab contient x et False sinon
    """
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = m + 1
        else:
            fin = ...
    return ...

Exemples :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
False

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

Exercice 1

Contraintes :

• n1 et n2 sont des entiers relatifs (négatifs, nuls ou positifs)
• -10^4 <= n1 <= 10^4 et -10^4 <= n2 <= 10^4
• La fonction renvoie un entier égal au produit n1 * n2
• Seules l’addition et la soustraction sont autorisées : l’opérateur * est interdit

Exercice 2

Contraintes :

• 0 <= len(tab) <= 10^5, le tableau vide [] est une entrée valide
• tab est un tableau d’entiers trié dans l’ordre croissant
• -10^9 <= tab[i] <= 10^9
• -10^9 <= x <= 10^9
• La fonction renvoie un booléen : True si tab contient x, False sinon (donc False pour tab = [])

Exercice 1 - multiplication par additions

L’idée. Multiplier a par b, c’est ajouter a à lui-même b fois. On part donc de 0 et on ajoute a dans une boucle qui tourne b fois : aucune multiplication n’est utilisée, seulement des additions. Reste le problème des nombres négatifs, car on ne peut pas répéter une boucle un nombre négatif de fois. On règle cela en travaillant sur les valeurs positives, et en retenant à part si le résultat doit être négatif : il l’est quand exactement un des deux nombres est négatif.

Un petit exemple. Pour multiplication(-2, 6) : on rend -2 positif, ce qui donne a = 2 et retient un signe négatif ; b vaut 6, donc on additionne six fois 2, ce qui fait 12 ; le signe retenu transforme ce 12 en -12.

def multiplication(n1, n2):
    # On raisonne sur des valeurs positives et on retient le signe du produit à part
    negatif = False
    a = n1
    b = n2
    if a < 0:
        a = -a
        negatif = not negatif
    if b < 0:
        b = -b
        negatif = not negatif
    produit = 0
    # Multiplier a par b, c'est ajouter a un nombre b de fois
    for i in range(b):
        produit = produit + a
    if negatif:
        produit = -produit
    return produit

a et b sont des copies de n1 et n2 qu’on rend positives, et negatif retient si le résultat devra changer de signe. Le not negatif sert exactement à cela : si les deux nombres sont négatifs, on bascule deux fois et on revient à False, ce qui donne bien un produit positif comme dans multiplication(-4, -8). Le cas 0 se règle tout seul : si b vaut 0, la boucle ne tourne jamais et produit reste 0.

Exercice 2 - recherche dichotomique

L’idée. Le tableau est trié, et c’est ce qui permet d’aller vite. Plutôt que de regarder les valeurs une par une, on regarde celle du milieu de la zone de recherche. Si c’est x, c’est gagné. Si x est plus grand, alors x ne peut se trouver que dans la moitié droite ; s’il est plus petit, seulement dans la moitié gauche. À chaque tour on jette donc la moitié du travail restant. Si la zone finit par devenir vide, c’est que x n’est pas dans le tableau.

Un petit exemple. Dans [15, 16, 18, 19, 23, 24, 28, 29, 31, 33] on cherche 28. Le milieu est 23 (position 4) ; 28 > 23, on ne garde que la droite. Le milieu devient 29 ; 28 < 29, on ne garde que la gauche. Le milieu est alors 28 : on renvoie True.

def dichotomie(tab, x):
    """
    tab : tableau d'entiers trié dans l'ordre croissant
    x : nombre entier
    La fonction renvoie True si tab contient x et False sinon
    """
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m + 1
        else:
            # x est plus petit que tab[m] : on ne garde que la partie gauche
            fin = m - 1
    # debut a dépassé fin : la zone de recherche est vide, x n'est pas dans tab
    return False

debut et fin délimitent la zone où x peut encore se trouver, et m en est la position du milieu, calculée avec // pour obtenir un indice entier. Les m + 1 et m - 1 sont importants : on vient de comparer tab[m] à x et ce n’était pas égal, donc on peut exclure la position m elle-même, ce qui garantit que la zone rétrécit à chaque tour et que la boucle finit toujours par s’arrêter. La condition debut <= fin autorise une zone d’une seule case, qu’il faut bien examiner ; quand debut dépasse fin, il ne reste plus rien à regarder et on renvoie False. C’est aussi ce qui donne la bonne réponse pour le tableau vide : fin vaut alors -1, la boucle n’est jamais exécutée et la fonction renvoie directement False.