Aller au contenu

La course aux plus grands⚓︎

Vous êtes le plus petit nombre d'un tableau et vous devez rattraper, dans l'ordre croissant, chacun des nombres qui vous est supérieur en vous déplaçant le moins possible. Pour réduire vos déplacements, vous devrez parfois passer les limites du tableau afin de vous retrouver automatiquement transporté à l'autre bout.

Exemple⚓︎

Prenons l'exemple du tableau [3, 1, 2, 4, 5].

  • Vous êtes le 1 (à l'indice 1) et commencez par rejoindre le 2 (à l'indice 2) en avançant de 1 position.
  • Vous rejoignez ensuite le 3 (à l'indice 0) en reculant de 2 positions.
  • Vous atteignez alors le 4 (à l'indice 3) en reculant de 2 positions (dans l'autre sens il faudrait avancer de 3).
  • Vous arrivez enfin au 5 (à l'indice 4) en avançant de 1 position.

Vous totalisez ainsi 6 déplacements (1+2+2+1) pour rattraper tous vos successeurs.

Exemple 3-1-2-4-5

Attendus⚓︎

Votre challenge consiste à créer une fonction rattraper qui prend en paramètre le tableau tab d'entiers distincts et qui renvoie le nombre minimum de déplacements à effectuer pour rattraper tous les successeurs, du plus petit nombre, dans l'ordre croissant.

Pour mieux structurer votre solution, vous commencerez par créer une fonction distance de paramètres i, j et n représentant respectivement l'indice de départ et l'indice d'arrivé dans un tableau de longueur n et qui renvoie le nombre minimum de déplacements à effectuer pour se rendre à l'indice j en partant de l'indice i.

Vous créerez aussi la fonction trier_indices dont le seul paramètre tab est le tableau des entiers distincts et qui renvoie la liste des indices des nombres du tableau tab triée suivant l'ordre croissant des entiers de tab.

Exemple

🐍 Console Python
>>> distance(1, 3, 5)
2
>>> distance(0, 4, 5)
1
>>> trier_indices([3, 1, 2, 4, 5])
[1, 2, 0, 3, 4]
>>> rattraper([3, 1, 2, 4, 5])
6
assert distance(0, 4, 5) == 1, "distance numéro 1"bksl-nlassert distance(2, 3, 5) == 1, "distance numéro 2"bksl-nlassert distance(3, 2, 5) == 1, "distance numéro 3"bksl-nlassert distance(4, 1, 5) == 2, "distance numéro 4"bksl-nlassert distance(1, 4, 6) == 3, "distance numéro 5"bksl-nlbksl-nlassert trierpy-undindices([1, 2, 3, 4]) == [0, 1, 2, 3], "trierpy-undindices numéro 1"bksl-nlassert trierpy-undindices([4, 3, 2, 1]) == [3, 2, 1, 0], "trierpy-undindices numéro 2"bksl-nlassert trierpy-undindices([3, 1, 2, 4, 5]) == [1, 2, 0, 3, 4], "trierpy-undindices numéro 3"bksl-nlassert trierpy-undindices([3, 6, 9, 2, 4]) == [3, 0, 4, 1, 2], "trierpy-undindices numéro 4"bksl-nlassert trierpy-undindices([9, 4, 8, 7, 2, 6, 1, 0, 3, 5]) == [7, 6, 4, 8, 1, 9, 5, 3, 2, 0], "trierpy-undindices numéro 5"bksl-nlbksl-nlassert rattraper([1, 2, 3, 4, 5]) == 4, "rattraper numéro 1"bksl-nlassert rattraper([4, 3, 2, 1]) == 3, "rattraper numéro 2"bksl-nlassert rattraper([5, 7, 4]) == 2, "rattraper numéro 3"bksl-nlassert rattraper([3, 1, 2, 4, 5]) == 6, "rattraper numéro 4"bksl-nlassert rattraper([9, 4, 8, 7, 2, 6, 1, 0, 3, 5]) == 21, "rattraper numéro 5"bksl-nlbksl-nl ∞/∞

def distance(i, j, n):bksl-nl """ Renvoie le nombre minimum de déplacements à effectuer pour se rendrebksl-nl à l'indice j en partant de l'indice i dans un tableau de longueur n """bksl-nl ...bksl-nlbksl-nlbksl-nldef trierpy-undindices(tab):bksl-nl """ Renvoie la liste des indices des nombres du tableau tabbksl-nl trié suivant l'ordre croissant des nombres du tableau tab """bksl-nl ...bksl-nlbksl-nlbksl-nldef rattraper(tab):bksl-nl """ Renvoie le nombre minimal de déplacements à effectuer pour rattraperbksl-nl chaque nombre du tableau tab, dans l'ordre croissant de leur valeur """bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert distance(0, 4, 5) == 1bksl-nlassert distance(2, 3, 5) == 1bksl-nlassert distance(4, 1, 5) == 2bksl-nlbksl-nlassert trierpy-undindices([1, 2, 3, 4]) == [0, 1, 2, 3]bksl-nlassert trierpy-undindices([4, 3, 2, 1]) == [3, 2, 1, 0]bksl-nlassert trierpy-undindices([3, 1, 2, 4, 5]) == [1, 2, 0, 3, 4]bksl-nlbksl-nlassert rattraper([1, 2, 3, 4, 5]) == 4bksl-nlassert rattraper([3, 1, 2, 4, 5]) == 6bksl-nlassert rattraper([4, 3, 2, 1]) == 3bksl-nlassert rattraper([5, 7, 4]) == 2bksl-nlbksl-nldef distance(i, j, n):bksl-nl """ Renvoie le nombre minimum de déplacements à effectuer pour se rendrebksl-nl à l'indice j en partant de l'indice i dans un tableau de longueur n """bksl-nl if i > j:bksl-nl dist = i - jbksl-nl else:bksl-nl dist = j - ibksl-nl return min(dist, n-dist) # deplacements direct ou par les extrémitésbksl-nlbksl-nlbksl-nldef trierpy-undindices(tab):bksl-nl """ Renvoie la liste des indices des nombres du tableau tabbksl-nl trié suivant l'ordre croissant des nombres du tableau tab """bksl-nl n = len(tab)bksl-nl # on commence par associer les nombres à leurs indices dans tabbksl-nl tabpy-undind = [(tab[i], i) for i in range(n)]bksl-nl # on effectue un tri par sélection mais on peut utiliser la méthode sort()bksl-nl for i in range(n-1):bksl-nl imin = ibksl-nl for j in range(i+1, n):bksl-nl if tabpy-undind[imin][0] > tabpy-undind[j][0]:bksl-nl imin = jbksl-nl tabpy-undind[i], tabpy-undind[imin] = tabpy-undind[imin], tabpy-undind[i]bksl-nl # on renvoie uniquement la liste des indicesbksl-nl return [tabpy-undind[i][1] for i in range(n)]bksl-nlbksl-nlbksl-nldef rattraper(tab):bksl-nl """ Renvoie le nombre minimal de déplacements à effectuer pour rattraperbksl-nl chaque nombre du tableau tab, dans l'ordre croissant de leur valeur """bksl-nl indices = trierpy-undindices(tab)bksl-nl n = len(tab)bksl-nl i = indices[0]bksl-nl total = 0bksl-nl for k in range(1, n):bksl-nl j = indices[k]bksl-nl total += distance(i, j, n)bksl-nl i = jbksl-nl return totalbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert distance(0, 4, 5) == 1bksl-nlassert distance(2, 3, 5) == 1bksl-nlassert distance(4, 1, 5) == 2bksl-nlbksl-nlassert trierpy-undindices([1, 2, 3, 4]) == [0, 1, 2, 3]bksl-nlassert trierpy-undindices([4, 3, 2, 1]) == [3, 2, 1, 0]bksl-nlassert trierpy-undindices([3, 1, 2, 4, 5]) == [1, 2, 0, 3, 4]bksl-nlbksl-nlassert rattraper([1, 2, 3, 4, 5]) == 4bksl-nlassert rattraper([3, 1, 2, 4, 5]) == 6bksl-nlassert rattraper([4, 3, 2, 1]) == 3bksl-nlassert rattraper([5, 7, 4]) == 2bksl-nlbksl-nl

A

Commentaires⚓︎

Le calcul de la distance directe entre deux indices i et j correspond à la différence d = i - j lorsque i est plus grand que j et à d = j - i dans le cas contraire. Il faut aussi établir la distance indirecte du chemin qui traverse les extrémités du tableau au lieu d'emprunter les cases intermédiaires. Elle est tout simplement égale à la longueur du tableau moins la distance directe len(tab) - d. Il ne reste plus qu'à choisir la plus petite de ces deux distances, pour minimiser le déplacement à effectuer.

Comme il faut parcourir les nombres dans l'ordre croissant, il suffit d'établir la liste de leurs indices dans l'ordre où il faut les parcourir. Pour y parvenir on peut construire la liste des couples (nombre,indice) et la trier suivant l'ordre croissant des nombres afin de constituer ensuite la liste des indices.

La fonction rattraper se réduit alors à sommer les distances entre les indices successifs.

Autre solution⚓︎

Voici une autre solution, qui utilise la fonction valeur absolue abs dans le calcul de la diistance et la fonction de tri sorted pour trier la liste des indices.

🐍 Script Python
def distance(i, j, n):
    """ Renvoie le nombre minimum de déplacements à effectuer pour se rendre
    à l'indice j en partant de l'indice i dans un tableau de longueur n """
    return min(abs(i-j), n-abs(i-j))


def trier_indices(tab):
    """ Renvoie la liste des indices des nombres du tableau tab
    trié suivant l'ordre croissant des nombres du tableau tab """
    ti = [(x, i) for i,x in enumerate(tab)]
    return [i for t,i in sorted(ti)]


def rattraper(tab):
    """ Renvoie le nombre minimal de déplacements à effectuer pour rattraper
    chaque nombre du tableau tab, dans l'ordre croissant de leur valeur """
    dist = 0
    indices = trier_indices(tab)
    for k in range(1, len(tab)):
        i, j = indices[k-1], indices[k]
        dist += distance(i, j, len(tab))
    return dist

Z

Retour en haut de la page