Épreuve pratique NSI 2024 — Sujet 18 : multiplication par additions, recherche dichotomique récursive

Épreuve pratique de NSI, session 2024 — sujet n°18 de la banque nationale. Durée : 1 heure, sur ordinateur. Le candidat traite les deux exercices, notés chacun sur 10 points.

Exercice 1 — multiplier avec des additions

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

Les seules opérations arithmétiques autorisées sont l'addition et la soustraction.

Exemples :

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

Exercice 2 — recherche dichotomique récursive

Soit tab un tableau non vide d'entiers triés dans l'ordre croissant et x un entier.

La fonction chercher ci-dessous doit renvoyer un indice où la valeur x apparaît dans tab si cette valeur y figure et None sinon.

Les paramètres de la fonction sont :

• tab, le tableau dans lequel s'effectue la recherche ;
• x, l'entier à chercher dans le tableau ;
• i, l'indice de début de la partie du tableau où s'effectue la recherche ;
• j, l'indice de fin de la partie du tableau où s'effectue la recherche.

L'algorithme demandé est une recherche dichotomique récursive.

Recopier et compléter le code de la fonction chercher suivante :

def chercher(tab, x, i, j):
    '''Renvoie l'indice de x dans tab, si x est dans tab,
    None sinon.
    On suppose que tab est trié dans l'ordre croissant.'''
    if i > j:
        return None
    m = (i + j) // ...
    if ... < x:
        return chercher(tab, x, ... , ...)
    elif tab[m] > x:
        return chercher(tab, x, ... , ...)
    else:
        return ...

Exemples :

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 10)
>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 5)
>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4
>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2