Exercice 1

EXERCICE 1 (10 points)

Programmer la fonction multiplication qui 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

EXERCICE 2 (10 points)

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

La fonction chercher ci-dessous doit renvoyer un indice où la valeur n 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, 5)
>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4
>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2
>>> chercher([1], 0, 0, 0)
>>> chercher([1], 1, 0, 0)
0

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
• -10^3 <= n1 <= 10^3 et -10^3 <= n2 <= 10^3
• la fonction renvoie un entier
• seules l’addition et la soustraction sont autorisées comme opérations arithmétiques

Exercice 2

Contraintes :

• 1 <= len(tab) <= 10^5
• tab est un tableau non vide d’entiers triés dans l’ordre croissant, doublons possibles
• -10^9 <= tab[k] <= 10^9 et -10^9 <= x <= 10^9
• 0 <= i < len(tab) et 0 <= j < len(tab) ; l’appel externe se fait avec i = 0 et j = len(tab) - 1
• la fonction renvoie None si x ne figure pas dans tab, sinon un indice où la valeur x figure
• jusqu’à 2*10^4 appels successifs sont effectués sur un même tableau : une solution en O(len(tab)) par appel dépassera la limite de temps

Solution commentée

Exercice 1 - multiplier sans multiplier

L’idée. Multiplier un nombre a par un nombre b positif, c’est simplement ajouter a à lui-même b fois. Comme seules l’addition et la soustraction sont autorisées, on part de 0 et on ajoute a autant de fois que l’indique b. Reste la question des signes : on fait le calcul avec les deux valeurs rendues positives, et on retient dans un booléen si le résultat final doit être négatif. Il l’est quand exactement un des deux nombres de départ est négatif.

Un petit exemple. Pour multiplication(-2, 6) : on travaille avec 2 et 6, on ajoute 2 six fois, ce qui donne 12 ; comme un seul des deux nombres était négatif, on renvoie 0 - 12, soit -12.

def multiplication(n1, n2):
    a = n1
    b = n2
    negatif = False
    # On rend a et b positifs, en notant a chaque fois un changement de signe
    if a < 0:
        a = 0 - a
        negatif = not negatif
    if b < 0:
        b = 0 - b
        negatif = not negatif
    produit = 0
    compteur = 0
    while compteur < b:
        produit = produit + a
        compteur = compteur + 1
    if negatif:
        produit = 0 - produit
    return produit

Quelques explications. a et b sont des copies de n1 et n2 que l’on peut modifier sans risque ; après les deux if, elles sont toutes les deux positives ou nulles. negatif bascule une fois par nombre négatif rencontré : il vaut donc True seulement si un seul des deux l’était, ce qui est exactement la règle des signes. La boucle tourne b fois et produit accumule les additions. On écrit 0 - a plutôt que -a pour n’utiliser que les opérations permises. Le cas multiplication(-2, 0) fonctionne tout seul : la boucle ne s’exécute pas, produit reste à 0, et 0 - 0 vaut bien 0.

Exercice 2 - recherche dichotomique récursive

L’idée. Le tableau est trié, on n’a donc pas besoin de le parcourir en entier. On regarde la case du milieu de la zone de recherche, celle qui va de l’indice i à l’indice j. Si la valeur du milieu est plus petite que x, alors x ne peut se trouver que dans la moitié de droite ; si elle est plus grande, x ne peut être que dans la moitié de gauche ; sinon c’est qu’on a trouvé x. À chaque appel la zone de recherche est divisée par deux, on arrive donc très vite au bout. Si la zone devient vide, c’est-à-dire si i > j, c’est que x n’est pas dans le tableau et on renvoie None.

Un petit exemple. Pour chercher([1, 5, 6, 6, 9, 12], 9, 0, 5) : le milieu est m = (0 + 5) // 2 = 2, et tab[2] vaut 6, qui est plus petit que 9 ; on recommence donc sur la zone 3 à 5. Là m = 4 et tab[4] vaut 9 : c’est gagné, on renvoie 4.

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) // 2
    if tab[m] < x:
        return chercher(tab, x, m + 1, j)
    elif tab[m] > x:
        return chercher(tab, x, i, m - 1)
    else:
        return m

Quelques explications. i et j délimitent la partie du tableau qui reste à explorer, et m est l’indice de son milieu. Le test i > j est le cas d’arrêt : la zone est vide, la valeur cherchée est absente. Dans les deux appels récursifs, on écrit m + 1 et m - 1, et non m : la case m vient d’être comparée à x, on sait qu’elle ne convient pas, et l’exclure garantit que la zone diminue vraiment à chaque appel. Sans cela, la fonction pourrait s’appeler indéfiniment sur la même zone. Enfin, quand tab[m] n’est ni plus petit ni plus grand que x, c’est qu’il est égal à x : on renvoie m, l’indice trouvé. Si la valeur cherchée apparaît plusieurs fois, cette méthode renvoie l’un de ses indices, pas forcément le premier : pour chercher([1, 5, 6, 6, 9, 12], 6, 0, 5), le premier milieu calculé est justement 2, et la fonction s’arrête tout de suite.