Aller au contenu

Sujet n°23

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°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 :

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'attribut 'enclos' est num_enclos.

Exemples

Avec la table animaux ci-dessus :

>>> 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)
[]
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def selection_enclos(table_animaux, num_enclos):
    """
    table_animaux - list, tableau de dictionnaires représentant des animaux et
                    ayant au moins la clef 'enclos' associée à une valeur entière
    num_enclos - int, numéro d'enclos
    Sortie: list - table contenant les enregistrements de table_animaux dont
            l'attribut 'enclos' est associé à la valeur num_enclos
    """
    return [animal for animal in table_animaux if animal['enclos'] == num_enclos]


if __name__ == '__main__':
    # Exemples de l'énoncé
    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}]

    print(selection_enclos(animaux, 5) == [{'nom':'Titine', 'espece':'chat', 'age':2, 'enclos':5}, {'nom':'Mirza', 'espece':'chat', 'age':6, 'enclos':5}])
    print(selection_enclos(animaux, 2) == [{'nom':'Medor', 'espece':'chien', 'age':5, 'enclos':2}])
    print(selection_enclos(animaux, 7) == [])

Exercice n°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 :

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 ^ :

[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 ci-dessous qui met en œuvre cet algorithme.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def trouver_intrus(tab, g, d):
    '''
    Renvoie la valeur de l'intrus situé entre les indices g et d 
    dans la liste 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 ...
Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. Cet algorithme se veut proche d'une méthode « Diviser pour Régner ». Il nécessite du temps d'appropriation...

Exemples

>>> 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
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def trouver_intrus(tab, g, d):
    '''
    Renvoie la valeur de l'intrus situé entre les indices g et d
    dans la liste tab où
        - tab vérifie les conditions de l'exercice,
        - g et d sont des multiples de 3.
    '''
    if g == d:
        return tab[g]

    else:
        nombre_de_triplets = (d - g) // 3
        indice = g + 3 * (nombre_de_triplets // 2)
        if tab[indice] == tab[indice+1] :
            return trouver_intrus(tab, indice+3, d)
        else:
            return trouver_intrus(tab, g, indice)


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(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)
    print(trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12) == 8)
    print(trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15) == 3)