EXERCICE 1 (10 points)

On considère des tables, c’est-à-dire des tableaux de dictionnaires ayant tous les mêmes clés, 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 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 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)
[]

EXERCICE 2 (10 points)

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]
#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]
 ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^
 0        3        6        9        12       15

Dans des tableaux 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.

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 ... 

Exemples :

>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7,
        2, 2, 2, 4, 4, 4, 8, 8, 8], 0, 18)
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

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

Exercice 1

Contraintes :

• animaux est un tableau de dictionnaires ayant tous exactement les clés 'nom', 'espece', 'age', 'enclos'
• 0 <= len(animaux) <= 100
• animaux[i]['nom'] et animaux[i]['espece'] sont des chaînes de caractères d’au plus 20 caractères
• animaux[i]['age'] est un entier avec 0 <= animaux[i]['age'] <= 30
• animaux[i]['enclos'] est un entier avec 0 <= animaux[i]['enclos'] <= 50
• num_enclos est un entier avec 0 <= num_enclos <= 50
• la table renvoyée peut être vide ; ses enregistrements apparaissent dans le même ordre que dans animaux

Exercice 2

Contraintes :

• tab est un tableau d’entiers vérifiant les conditions de l’exercice : chaque élément y figure exactement trois fois à la suite, sauf un unique élément, l’intrus, présent une seule fois
• len(tab) vaut 3 * k + 1 avec 0 <= k <= 300
• -10^3 <= tab[i] <= 10^3
• g et d sont des entiers multiples de 3 vérifiant 0 <= g <= d <= len(tab) - 1
• l’intrus se situe entre les indices g et d
• les appels effectués sont de la forme trouver_intrus(tab, 0, len(tab) - 1)

Correction

Exercice 1 - selection_enclos

L’idée. Une table n’est rien d’autre qu’un tableau de dictionnaires. Pour ne garder que les animaux d’un enclos donné, il suffit de parcourir la table du début à la fin et, pour chaque enregistrement, de regarder la valeur associée à la clé 'enclos'. Si elle vaut num_enclos, on ajoute l’enregistrement à un tableau résultat créé vide au départ. À la fin du parcours, on renvoie ce tableau.

Un petit exemple. Avec la table animaux du sujet et num_enclos = 2, un seul enregistrement a son attribut 'enclos' égal à 2, celui de Medor : on renvoie donc un tableau contenant ce seul enregistrement.

def selection_enclos(animaux, num_enclos):
    resultat = []
    for animal in animaux:
        if animal['enclos'] == num_enclos:
            resultat.append(animal)
    return resultat

Explication. animal désigne tour à tour chaque dictionnaire de la table, et animal['enclos'] lit son numéro d’enclos. resultat accumule les enregistrements retenus. Comme on parcourt animaux dans l’ordre, les enregistrements gardés apparaissent dans le même ordre que dans la table de départ, ce qui correspond bien aux exemples du sujet (Titine avant Mirza). Si aucun animal ne convient, resultat n’est jamais modifié et on renvoie [].

Exercice 2 - trouver_intrus

L’idée. C’est une recherche par dichotomie. Les deux paramètres g et d sont des indices multiples de 3 entre lesquels se trouve l’intrus. Si g et d sont égaux, il ne reste plus qu’une seule case possible : l’intrus est tab[g]. Sinon, on compte combien de triplets séparent g de d, on se place sur l’indice multiple de 3 situé à peu près au milieu, et on compare la valeur de cet indice avec celle de son voisin de droite. Si les deux valeurs sont égales, c’est qu’on est encore avant l’intrus : il faut chercher plus loin, à partir de indice + 3. Si elles sont différentes, l’intrus est à gauche, indice compris.

Un petit exemple. Pour tab_a avec g = 0 et d = 18 : il y a (18 - 0) // 3 = 6 triplets, donc indice = 0 + 3 * (6 // 2) = 9. On lit tab[9] qui vaut 7 et tab[10] qui vaut 2 : elles diffèrent, on continue donc la recherche entre les indices 0 et 9.

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 tab[g]
    else:
        nombre_de_triplets = (d - g) // 3
        indice = g + 3 * (nombre_de_triplets // 2)
        if tab[indice] == tab[indice + 1]:
            # valeurs égales : on est avant l'intrus, il est après ce triplet
            return trouver_intrus(tab, indice + 3, d)
        else:
            # valeurs différentes : l'intrus est à cet indice ou avant
            return trouver_intrus(tab, g, indice)

Explication. (d - g) // 3 donne le nombre de triplets compris entre g et d : c’est pour cela que le trou de cette ligne est un 3. En prenant la moitié de ce nombre, indice reste un multiple de 3, puisqu’on ajoute à g (multiple de 3) un multiple de 3. La comparaison tab[indice] == tab[indice + 1] est exactement l’observation du sujet : avant l’intrus, un indice multiple de 3 et son voisin de droite sont égaux ; à partir de l’intrus, ils diffèrent.

Les deux appels récursifs travaillent sur un intervalle strictement plus petit : dans la branche de gauche, indice est toujours strictement inférieur à d ; dans la branche de droite, indice + 3 est strictement supérieur à g. L’intervalle est ainsi divisé par deux à chaque appel et on finit toujours par atteindre le cas g == d, qui arrête la récursion. Enfin, tab[indice + 1] existe bien : comme indice est strictement inférieur à d, l’indice indice + 1 reste dans le tableau.