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 :
Exemple
🐍 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 7tab_b=[8,5,5,5,9,9,9,18,18,18,3,3,3]#l'intrus est 8tab_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 ^ :
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 qui met en œuvre cet algorithme
def trouverpy-undintrus(tab, g, d):bksl-nl '''bksl-nl Renvoie la valeur de l'intrus situe entre les indices g et dbksl-nl dans la liste tab ou :bksl-nl tab verifie 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 + 3py-str(nombrepy-unddepy-undtriplets//2)bksl-nl if ... :bksl-nl return ...bksl-nl else:bksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert trouverpy-undintrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8,bksl-nl8, 5, 5, 5], 0, 21) == 7bksl-nlassert trouverpy-undintrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12) == 8bksl-nlassert trouverpy-undintrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15) == 3bksl-nlbksl-nldef trouverpy-undintrus(tab, g, d):bksl-nl '''bksl-nl Renvoie la valeur de l'intrus situe entre les indices g et dbksl-nl dans la liste tab ou :bksl-nl tab verifie 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 + 3py-str(nombrepy-unddepy-undtriplets//2)bksl-nl if tab[indice] == tab[indice + 1] :bksl-nl return trouverpy-undintrus(tab, indice + 3, d)bksl-nl else:bksl-nl return trouverpy-undintrus(tab, g, indice)bksl-nlbksl-nlbksl-nl