Aller au contenu

Ep 40

le document

l'algorithme

Issue de : 23-NSI-23⚓

EXERCICE 1⚓

On considÚre des tables (des tableaux de dictionnaires) qui contiennent des enregistrements relatifs à des animaux hébergés dans un refuge. Les attributs des enregistrements sont 'nom', 'espece', 'age', 'enclos'.

Voici un exemple d'une telle table :

🐍 Script Python
animaux = [ {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},
            {'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
            {'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},
            {'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},
            {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]

Programmer une fonction selection_enclos qui :

  • prend en paramĂštres :

    • une table table_animaux contenant des enregistrements relatifs Ă  des animaux (comme dans l'exemple ci-dessus),
    • un numĂ©ro d'enclos num_enclos ;

  • renvoie une table contenant les enregistrements de table_animaux dont l'atribut 'enclos' est num_enclos.

Exemples avec la table animaux ci-dessus :

🐍 Script Python
>>> selection_enclos(animaux, 5)
[{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},
{'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]

>>> selection_enclos(animaux, 2)
[{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}]

>>> selection_enclos(animaux, 7)
[]
RĂ©ponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlanimaux = [ {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},bksl-nl {'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},bksl-nl {'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},bksl-nl {'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},bksl-nl {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]bksl-nl

Solution

###
def selectionpy-undenclos(tablepy-undanimaux, numpy-undenclos):bksl-nl table = []bksl-nl for animal in tablepy-undanimaux:bksl-nl if animal['enclos'] == numpy-undenclos:bksl-nl table.append(animal)bksl-nl return tablebksl-nlbksl-nltry:bksl-nl animaux = [ {'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2},bksl-nl {'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},bksl-nl {'nom':'Tom', 'espece':'chat', 'age':7, 'enclos':4},bksl-nl {'nom':'Belle', 'espece':'chien', 'age':6, 'enclos':3},bksl-nl {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]bksl-nl bksl-nl assert selectionpy-undenclos(animaux, 5) == [{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5},bksl-nl {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}]bksl-nl assert selectionpy-undenclos(animaux, 2) == [{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}]bksl-nl assert selectionpy-undenclos(animaux, 7) == []bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl

EXERCICE 2⚓

On considÚre des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle «l'intrus ». Voici quelques exemples :

🐍 Script Python
tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7

tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8

tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3
On remarque qu'avec de tels tableaux :

  • pour les indices multiples de 3 situĂ©s strictement avant l'intrus, l'Ă©lĂ©ment correspondant et son voisin de droite sont Ă©gaux,
  • pour les indices multiples de 3 situĂ©s aprĂšs l'intrus, l'Ă©lĂ©ment correspondant et son voisin de droite - s'il existe - sont diffĂ©rents.

Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractÚres ^

🐍 Script Python
[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^
0        3        6        9        12       15       18       21
Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.

Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.

Par exemple, si on s’intĂ©resse Ă  l’indice 12, on voit les valeurs 2 et 4 qui sont diffĂ©rentes : l’intrus est donc Ă  gauche de l’indice 12 (indice 12 compris)

En revanche, si on s’intĂ©resse Ă  l’indice 3, on voit les valeurs 9 et 9 qui sont identiques : l’intrus est donc Ă  droite des indices 3-4-5, donc Ă  partir de l’indice 6.

ComplĂ©ter la fonction rĂ©cursive trouver_intrus proposĂ©e page suivante qui met en Ɠuvre cet algorithme.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def trouver_intrus(tab, g, d):
    """Renvoie la valeur de l'intrus situé entre les indices g et d 
    dans le tableau tab oĂč :
    tab vérifie les conditions de l'exercice,
    g et d sont des multiples de 3."""
    if g == d:
        return ... 
    else:
        nombre_de_triplets = (d - g) // ... 
        indice = g + 3 * (nombre_de_triplets // 2)
        if ...: 
            return ... 
        else:
            return ...

Exemple :

🐍 Script Python
>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5], 0, 21)
7
>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12)
8
>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15)
3

RĂ©ponse

Complétez le code ci-dessous

###
def trouverpy-undintrus(tab, g, d):bksl-nl '''bksl-nl Renvoie la valeur de l'intrus situĂ© entre les indices g et d bksl-nl dans la liste tab oĂč :bksl-nl tab vĂ©rifie les conditions de l'exercice,bksl-nl g et d sont des multiples de 3.bksl-nl '''bksl-nl if g == d:bksl-nl return ...bksl-nlbksl-nl else:bksl-nl nombrepy-unddepy-undtriplets = (d - g) // ...bksl-nl indice = g + 3 py-str (nombrepy-unddepy-undtriplets // 2)bksl-nl if ... :bksl-nl return ...bksl-nl else:bksl-nl return ...bksl-nlbksl-nl

Solution

###
def trouverpy-undintrus(tab, g, d):bksl-nl '''bksl-nl Renvoie la valeur de l'intrus situĂ© entre les indices g et d bksl-nl dans la liste tab oĂč :bksl-nl tab vĂ©rifie les conditions de l'exercice,bksl-nl g et d sont des multiples de 3.bksl-nl '''bksl-nl if g == d:bksl-nl return tab[g]bksl-nlbksl-nl else:bksl-nl nombrepy-unddepy-undtriplets = (d - g) // 3bksl-nl indice = g + 3 py-str (nombrepy-unddepy-undtriplets // 2)bksl-nl if tab[indice] != tab[indice + 1] :bksl-nl return trouverpy-undintrus(tab, g, indice)bksl-nl else:bksl-nl return trouverpy-undintrus(tab, indice + 3, d)bksl-nlbksl-nltry:bksl-nl assert trouverpy-undintrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5], 0, 21) == 7bksl-nl assert trouverpy-undintrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12) == 8bksl-nl assert trouverpy-undintrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15) == 3bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl