Aller au contenu

Ep 05

le document

l'algorithme

Issue de : 23-NSI-18⚓

EXERCICE 1⚓

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

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

Exemples :

🐍 Script Python
>>> 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)

RĂ©ponse

Complétez le code ci-dessous

###
# Mettre ici votre codebksl-nlbksl-nl

Solution

###
def maxpy-undetpy-undindice(tab):bksl-nl '''bksl-nl renvoie la valeur du plus grand Ă©lĂ©ment de cette liste ainsibksl-nl que l’indice de sa premiĂšre apparition dans cette liste.bksl-nl '''bksl-nl assert tab != [], 'le tableau est vide'bksl-nlbksl-nl valpy-undmax = tab[0]bksl-nl indpy-undmax = 0bksl-nl for i in range(len(tab)):bksl-nl if tab[i] > valpy-undmax:bksl-nl valpy-undmax = tab[i]bksl-nl indpy-undmax = ibksl-nl return (valpy-undmax, indpy-undmax)bksl-nlbksl-nltry:bksl-nl assert maxpy-undetpy-undindice([1, 5, 6, 9, 1, 2, 3, 7, 9, 8]) == (9, 3)bksl-nl assert maxpy-undetpy-undindice([-2]) == (-2, 0)bksl-nl assert maxpy-undetpy-undindice([-1, -1, 3, 3, 3]) == (3, 2)bksl-nl assert maxpy-undetpy-undindice([1, 1, 1, 1]) == (1, 0)bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nlbksl-nl

EXERCICE 2⚓

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.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
    return nb

Exemple :

🐍 Script Python
>>> est_un_ordre([1, 6, 2, 8, 3, 7])
False
>>> est_un_ordre([5, 4, 3, 6, 7, 2, 1, 8, 9])
True
>>> nombre_points_rupture([5, 4, 3, 6, 7, 2, 1, 8, 9])
4
>>> nombre_points_rupture([1, 2, 3, 4, 5])
0
>>> nombre_points_rupture([1, 6, 2, 8, 3, 7, 4, 5])
7
>>> nombre_points_rupture([2, 1, 3, 4])
2

RĂ©ponse

Complétez le code ci-dessous

###
def estpy-undunpy-undordre(tab):bksl-nl '''bksl-nl Renvoie True si tab est de longueur n et contient tous les entiersbksl-nl de 1 à n, False sinonbksl-nl '''bksl-nl for i in range(1,...):bksl-nl if ...:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nldef nombrepy-undpointspy-undrupture(ordre):bksl-nl '''bksl-nl Renvoie le nombre de point de rupture de ordre qui représente un ordrebksl-nl de gÚnes de chromosomebksl-nl '''bksl-nl assert ... # ordre n'est pas un ordre de gÚnesbksl-nl n = len(ordre)bksl-nl nb = 0bksl-nl if ordre[...] != 1: # le premier n'est pas 1bksl-nl nb = nb + 1bksl-nl i = 0bksl-nl while i < ...:bksl-nl if ... not in [-1, 1]: # l'écart n'est pas 1bksl-nl nb = nb + 1bksl-nl i = i + 1bksl-nl if ordre[...] != n: # le dernier n'est pas nbksl-nl nb = nb + 1bksl-nl return nbbksl-nlbksl-nl

Solution

###
def estpy-undunpy-undordre(tab):bksl-nl '''bksl-nl Renvoie True si tab est de longueur n et contient tous les entiersbksl-nl de 1 Ă  n, False sinonbksl-nl '''bksl-nl for i in range(1, len(tab)+1):bksl-nl if i not in tab:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nldef nombrepy-undpointspy-undrupture(ordre):bksl-nl '''bksl-nl Renvoie le nombre de point de rupture de ordre qui reprĂ©sente un ordrebksl-nl de gĂšnes de chromosomebksl-nl '''bksl-nl assert estpy-undunpy-undordre(ordre) # ordre n'est pas un ordre de gĂšnesbksl-nl n = len(ordre)bksl-nl nb = 0bksl-nl if ordre[0] != 1: # le premier n'est pas 1bksl-nl nb = nb + 1bksl-nl i = 0bksl-nl while i < n-1:bksl-nl if ordre[i+1] - ordre[i] not in [-1, 1]: # l'Ă©cart n'est pas 1bksl-nl nb = nb + 1bksl-nl i = i + 1bksl-nl if ordre[n-1] != n: # le dernier n'est pas nbksl-nl nb = nb + 1bksl-nl return nbbksl-nlbksl-nltry:bksl-nl assert estpy-undunpy-undordre([1, 6, 2, 8, 3, 7]) == Falsebksl-nl assert estpy-undunpy-undordre([5, 4, 3, 6, 7, 2, 1, 8, 9]) == Truebksl-nl assert nombrepy-undpointspy-undrupture([5, 4, 3, 6, 7, 2, 1, 8, 9]) == 4bksl-nl assert nombrepy-undpointspy-undrupture([1, 2, 3, 4, 5]) == 0bksl-nl assert nombrepy-undpointspy-undrupture([1, 6, 2, 8, 3, 7, 4, 5]) == 7bksl-nl assert nombrepy-undpointspy-undrupture([2, 1, 3, 4]) == 2bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl