Solution de Points de rupture d'un ordre de gènes - Sujet 02 - EP NSI 2025

EXERCICE 1 (10 points)

Écrire une fonction max_et_indice qui prend en paramètre un tableau non vide tab (type Python list) de nombres entiers et qui renvoie la valeur du plus grand élément de ce tableau ainsi que l’indice de sa première apparition dans ce tableau.

L’utilisation de la fonction native max n’est pas autorisée.

Exemples :

>>> max_et_indice([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, 3)
>>> max_et_indice([-2])
(-2, 0)
>>> max_et_indice([-1, -1, 3, 3, 3])
(3, 2)
>>> max_et_indice([1, 1, 1, 1])
(1, 0)

EXERCICE 2 (10 points)

L’ordre des gènes sur un chromosome est représenté par un tableau ordre de n cases d’entiers distincts deux à deux et compris entre 1 et n.

Par exemple, ordre = [5, 4, 3, 6, 7, 2, 1, 8, 9] dans le cas n = 9.

On dit qu’il y a un point de rupture dans ordre dans chacune des situations suivantes :

• la première valeur de ordre n’est pas 1 ;
• l’écart entre deux gènes consécutifs n’est pas égal à 1 ;
• la dernière valeur de ordre n’est pas n.

Par exemple, si ordre = [5, 4, 3, 6, 7, 2, 1, 8, 9] avec n = 9, on a

• un point de rupture au début car 5 est différent de 1
• un point de rupture entre 3 et 6 (l’écart est de 3)
• un point de rupture entre 7 et 2 (l’écart est de 5)
• un point de rupture entre 1 et 8 (l’écart est de 7)

Il y a donc 4 points de rupture.

Compléter les fonctions Python est_un_ordre et nombre_points_rupture proposées à la page suivante pour que :

• la fonction est_un_ordre renvoie True si le tableau passé en paramètre représente bien un ordre de gènes de chromosome et False sinon ;
• la fonction nombre_points_rupture renvoie le nombre de points de rupture d’un tableau passé en paramètre représentant l’ordre de gènes d’un chromosome.

def est_un_ordre(tab):
    '''
    Renvoie True si tab est de longueur n et contient tous les
    entiers de 1 à n, False sinon
    '''
    n = len(tab)
    # les entiers vus lors du parcours
    vus = ...

    for x in tab:
        if x < ... or x >... or ...:
            return False
        ... .append(...)
    return True

def nombre_points_rupture(ordre):
    '''
    Renvoie le nombre de point de rupture de ordre qui représente
    un ordre de gènes de chromosome
    '''
    # on vérifie que ordre est un ordre de gènes
    assert ...
    n = len(ordre)
    nb = 0
    if ordre[...] != 1: # le premier n'est pas 1
        nb = nb + 1
    i = 0
    while i < ...:
        if ... not in [-1, 1]: # l'écart n'est pas 1
            nb = nb + 1
        i = i + 1
    if ordre[i] != ...: # le dernier n'est pas n
        nb = nb + 1

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

Exercice 1

Contraintes :

• tab est un tableau (type Python list) de nombres entiers
• 1 <= len(tab) <= 10^4
• -10^9 <= tab[i] <= 10^9
• max_et_indice renvoie un tuple (valeur, indice) de deux entiers

Exercice 2

Contraintes :

• pour est_un_ordre, tab est un tableau (type Python list) d’entiers quelconques, avec 0 <= len(tab) <= 10^3 et -10^9 <= tab[i] <= 10^9
• est_un_ordre renvoie un booléen (True ou False)
• pour nombre_points_rupture, ordre est un tableau de n entiers contenant chaque entier de 1 à n exactement une fois, avec 1 <= n <= 10^3
• nombre_points_rupture renvoie un entier

Exercice 1 - max_et_indice

L’idée. On ne peut pas utiliser max, donc on cherche le maximum « à la main » : on parcourt le tableau en retenant au fur et à mesure la plus grande valeur rencontrée jusque-là, et à quelle position on l’a vue. On part de la case 0 (le tableau n’est jamais vide), puis chaque fois qu’on tombe sur une valeur strictement plus grande, on met à jour les deux mémoires.

Un petit exemple. Pour [1, 5, 6, 9, 1, 2, 3, 7, 9, 8] : on part de 1 en position 0, puis 5 est plus grand (position 1), puis 6 (position 2), puis 9 (position 3). Le second 9, en position 8, n’est pas strictement plus grand : on ne change rien. Résultat : (9, 3).

def max_et_indice(tab):
    maximum = tab[0]
    indice = 0
    for i in range(1, len(tab)):
        # comparaison stricte : on ne remplace pas en cas d'egalite,
        # donc indice garde la premiere apparition du maximum
        if tab[i] > maximum:
            maximum = tab[i]
            indice = i
    return (maximum, indice)

maximum contient toujours la plus grande valeur vue depuis le début, et indice la position où on l’a vue pour la première fois. La boucle démarre à 1 parce que la case 0 sert de valeur de départ : inutile de la comparer avec elle-même. Le point à ne pas rater est le > : avec un >=, on remplacerait l’indice à chaque égalité et on renverrait la dernière apparition au lieu de la première ([1, 1, 1, 1] donnerait (1, 3) au lieu de (1, 0)).

Exercice 2 - points de rupture

est_un_ordre

L’idée. Un tableau de longueur n est un ordre de gènes s’il contient chaque entier de 1 à n exactement une fois. Comme il y a autant de cases que de valeurs attendues, il suffit de vérifier deux choses en parcourant le tableau : chaque valeur est bien entre 1 et n, et aucune valeur n’apparaît deux fois. C’est pour cela que le sujet propose la liste vus : elle mémorise les valeurs déjà rencontrées, et on refuse le tableau dès qu’on retombe sur l’une d’elles.

Un petit exemple. Pour [1, 6, 2, 8, 3, 7], on a n = 6 : 1, 6 et 2 passent, mais 8 est plus grand que 6, donc c’est False.

def est_un_ordre(tab):
    '''
    Renvoie True si tab est de longueur n et contient tous les
    entiers de 1 à n, False sinon
    '''
    n = len(tab)
    # les entiers vus lors du parcours
    vus = []

    for x in tab:
        if x < 1 or x > n or x in vus:
            return False
        vus.append(x)
    return True

vus part vide et grandit à chaque tour. Les trois conditions du if sont dans l’ordre du sujet : trop petit, trop grand, déjà vu. Le x in vus est un test d’appartenance sur une liste, exactement ce que la trame du sujet demandait. Si on arrive au bout de la boucle sans jamais refuser, c’est que les n valeurs sont distinctes et toutes entre 1 et n : elles ne peuvent donc être que 1, 2, …, n, d’où le return True.

nombre_points_rupture

L’idée. On compte les ruptures dans le compteur nb, en suivant les trois situations décrites par l’énoncé, dans l’ordre : d’abord la première valeur si elle ne vaut pas 1, puis chaque couple de gènes voisins dont l’écart n’est pas de 1, puis la dernière valeur si elle ne vaut pas n.

Un petit exemple. Pour [2, 1, 3, 4] avec n = 4 : le premier vaut 2 et non 1, donc une rupture ; les écarts sont -1, 2, 1, seul le 2 est une rupture ; le dernier vaut bien 4. Total : 2.

def nombre_points_rupture(ordre):
    '''
    Renvoie le nombre de point de rupture de ordre qui représente
    un ordre de gènes de chromosome
    '''
    # on vérifie que ordre est un ordre de gènes
    assert est_un_ordre(ordre)
    n = len(ordre)
    nb = 0
    if ordre[0] != 1: # le premier n'est pas 1
        nb = nb + 1
    i = 0
    while i < n - 1:
        if ordre[i + 1] - ordre[i] not in [-1, 1]: # l'écart n'est pas 1
            nb = nb + 1
        i = i + 1
    if ordre[i] != n: # le dernier n'est pas n
        nb = nb + 1
    return nb

L’assert réutilise la fonction précédente : on refuse de compter si le tableau n’est pas un ordre de gènes. La boucle compare la case i et la case i + 1, donc elle doit s’arrêter avant la dernière case : d’où le i < n - 1, sinon ordre[i + 1] sortirait du tableau. La différence est comparée à [-1, 1] et non à 1 seulement, parce que les gènes peuvent se suivre en montant ou en descendant : 3 puis 4 et 4 puis 3 sont tous les deux acceptables.

Enfin, remarquez que le dernier test réutilise i sans le remettre à zéro : quand la boucle while s’arrête, i vaut exactement n - 1, c’est-à-dire l’indice de la dernière case. ordre[i] est donc bien le dernier gène, qu’on compare à n.