Solution de Séparation des 0 et des 1 - Sujet 19 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction recherche_min qui prend en paramètre un tableau de nombres tab non vide, et qui renvoie l’indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de liste Python.

Exemples :

>>> recherche_min([5])
0
>>> recherche_min([2, 4, 1])
2
>>> recherche_min([5, 3, 2, 2, 4])
2
>>> recherche_min([-1, -2, -3, -3])
2

Exercice 2

EXERCICE 2 (10 points)

On considère la fonction separe ci-dessous qui prend en argument un tableau tab dont les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de tableau et les 1 à la suite.

def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = ...
    while gauche < droite:
        if tab[gauche] == 0 :
            gauche = ...
        else :
            tab[gauche] = ...
            tab[droite] = ...
            droite = ...
    return tab

Compléter la fonction separe ci-dessus.

Exemples :

>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0])
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Description d’étapes effectuées par la fonction separe sur le tableau ci-dessous, les caractères ^ indiquent les cases pointées par les indices gauche et droite :

tab = [1, 0, 1, 0, 1, 0, 1, 0]
       ^                    ^

• Étape 1 : on regarde la première case, qui contient un 1 : ce 1 va aller dans la seconde partie du tableau final et on l’échange avec la dernière case. Il est à présent bien positionné : on ne prend plus la dernière case en compte.

tab = [0, 0, 1, 0, 1, 0, 1, 1]
       ^                 ^

• Étape 2 : on regarde à nouveau la première case, qui contient maintenant un 0 : ce 0 va aller dans la première partie du tableau final et est bien positionné : on ne prend plus la première case en compte.

tab = [0, 0, 1, 0, 1, 0, 1, 1]
          ^              ^

• Étape 3 : on regarde la seconde case, qui contient un 0 : ce 0 va aller dans la première partie du tableau final et est bien positionné : on ne prend plus la seconde case en compte.

tab = [0, 0, 1, 0, 1, 0, 1, 1]
             ^           ^

• Étape 4 : on regarde la troisième case, qui contient un 1 : ce 1 va aller dans la seconde partie du tableau final et on l’échange avec l’avant-dernière case. Il est à présent bien positionné : on ne prend plus l’avant-dernière case en compte.

tab = [0, 0, 1, 0, 1, 0, 1, 1]
             ^        ^

Et ainsi de suite…

tab = [0, 0, 0, 0, 1, 1, 1, 1]

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

Exercice 1

Contraintes :

• tab est une liste Python non vide : 1 <= len(tab) <= 10^4
• tab[i] est un entier avec -10^6 <= tab[i] <= 10^6
• les valeurs de tab peuvent se répéter
• recherche_min renvoie un entier : l’indice de la première occurrence du minimum, donc un indice compris entre 0 et len(tab) - 1

Exercice 2

Contraintes :

• tab est une liste Python avec 0 <= len(tab) <= 10^4
• chaque élément tab[i] vaut 0 ou 1
• tab peut être vide ou ne contenir qu’un seul élément
• separe renvoie le tableau tab, contenant les mêmes nombres de 0 et de 1 qu’en entrée, les 0 placés avant les 1

Exercice 1 - recherche_min

L’idée. Un seul parcours du tableau suffit. On retient au fur et à mesure l’indice de la plus petite valeur rencontrée jusque-là. On part de l’indice 0, la seule case connue au début, puis on compare chaque case suivante à la valeur retenue. Le point délicat est la première occurrence : on ne change d’indice que si la nouvelle valeur est strictement plus petite, jamais si elle est égale.

Un petit exemple. Pour [5, 3, 2, 2, 4] : on part de l’indice 0 (valeur 5), puis 3 < 5 donc on retient l’indice 1, puis 2 < 3 donc on retient l’indice 2, puis le 2 d’indice 3 n’est pas strictement plus petit donc on ne bouge pas, et 4 non plus. La fonction renvoie 2.

def recherche_min(tab):
    indice_min = 0
    # On ne change d'indice que si la valeur est strictement plus petite :
    # c'est ce qui garde la première occurrence du minimum
    for i in range(1, len(tab)):
        if tab[i] < tab[indice_min]:
            indice_min = i
    return indice_min

indice_min contient un indice, pas la valeur du minimum : c’est bien un indice que l’énoncé demande de renvoyer. La boucle démarre à 1 parce que la case 0 sert de point de départ, et le tableau est non vide donc cette case existe toujours. Si on écrivait <= au lieu de <, la fonction renverrait la dernière occurrence du minimum : sur [-1, -2, -3, -3] elle donnerait 3 au lieu de 2.

Exercice 2 - separe

L’idée. On se sert de deux indices : gauche part du début du tableau, droite part de la fin. À tout moment, ce qui est avant gauche est déjà un 0 bien placé, et ce qui est après droite est déjà un 1 bien placé. On regarde la case gauche :

• si elle contient un 0, il est déjà du bon côté : on avance gauche d’un cran ;
• si elle contient un 1, on l’échange avec la case droite, ce 1 se retrouve au bon endroit et on recule droite d’un cran.

On s’arrête quand les deux indices se rejoignent.

Comment remplir les cinq trous. droite doit démarrer sur la dernière case, donc len(tab) - 1. Pour le cas du 0 : gauche = gauche + 1. Pour le cas du 1, on échange les deux cases : comme on sait déjà que tab[gauche] vaut 1, l’échange revient à recopier tab[droite] dans tab[gauche], puis à écrire 1 dans tab[droite]. Enfin on recule : droite = droite - 1.

def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = len(tab) - 1
    while gauche < droite:
        if tab[gauche] == 0 :
            gauche = gauche + 1
        else :
            # tab[gauche] vaut 1 : on échange les deux cases, donc on recopie
            # tab[droite] à gauche et on écrit le 1 à droite
            tab[gauche] = tab[droite]
            tab[droite] = 1
            droite = droite - 1
    return tab

Attention : quand tab[gauche] vaut 1, on n’avance pas gauche, car la valeur qui vient d’arriver à cette place n’a pas encore été examinée. C’est pour cela que l’étape 4 de l’énoncé laisse le tableau inchangé : les cases 2 et 6 contenaient toutes les deux un 1, l’échange ne change rien, mais droite recule quand même. Comme on ne fait que des échanges, le nombre de 0 et de 1 est le même au début et à la fin.

La boucle s’arrête dès que gauche et droite se rejoignent : la case restante est la frontière entre la zone des 0 et celle des 1, elle est correcte quelle que soit sa valeur. Cela couvre aussi les petits cas : sur un tableau vide, droite vaut -1 et la boucle ne s’exécute jamais ; sur un tableau à un seul élément, gauche et droite valent 0 dès le départ. Là encore, un seul parcours suffit, chaque case n’étant regardée qu’une fois.