Nous considérons une fonction \(f\) qui à tout entier naturel \(i\), \(0 \leq i \leq n\), associe un entier naturel \(j\) tel que \(0\leq j\leq m\),
avec \(m\) la valeur maximale de \(f(i)\).
Une telle fonction est représentée par le tableau images = [f(0), f(1), ..., f(n)]. Ainsi la valeur de \(f(i)\) est obtenue avec images[i].
L'objectif est d'obtenir pour tout entier \(j\), \(0\leq j\leq m\), la liste de ses antécédents, c'est-à-dire la liste des entiers \(i\), \(0 \leq i \leq n\), pour lesquels \(f(i) = j\).
Pour cela nous construisons deux tableaux, un tableau tetes et un tableau suivants, de la manière suivante:
les valeurs des éléments de tetes et de suivantssont initialisées à \(-1\);
si j a un unique antécédent i, alors tetes[j] a pour valeur i et suivant[i] a pour valeur -1.
si \(i_1, i_2, i_3, ..., i_p\), avec \(p \geq 2\), sont les antécédents de \(j\), alors tetes[j] a pour valeur \(i_p\), chaque élément de suivants d'indice \(i_k\), pour \(2\leq k\leq p\), a pour valeur \(i_{k-1}\) et l'élément de suivants d'indice \(i_1\) a pour valeur \(-1\);
Remarque: en Python, nous pouvons répondre à cette question de manière élégante à l'aide d'un dictionnaire, objet du type construit dict. Mais cette solution nécessite plus d'espace mémoire
et l'utilisation de tableaux dynamiques pour stocker les antécédents.
1. Construction des tableaux tetes et suivants
Compléter la fonction image_rec qui prend en paramètres un tableau images représentant une fonction \(f\) et un entier m représentant la valeur maximale des images, et qui construit et renvoie les deux tableaux tetes et suivants.
Il s'agit maintenant avec les deux tableaux tetes et suivants de parcourir la liste des antécédents d'un entier \(j\), \(0\leq j\leq m\), \(m\) étant la valeur maximale de \(f\)
qu'on peut obtenir si nécessaire avec len(tetes)-1. Le coût pour chaque entier \(j\) est de l'ordre du nombre d'antécédents de \(j\).
Remarque: on pourrait parcourir la liste des images et noter les indices des éléments de valeur \(j\), mais dans ce cas le coût pour obtenir la liste des antécédents d'un entier \(j\) serait de l'ordre de \(n\).
Ce parcours permet de traiter chaque antécédent d'un entier \(j\). Ici, il est demandé de construire une liste liste initialement vide et complétée à chaque étape du parcours par l'antécédent de \(j\) obtenu.
2. Antécédents d'un élément
Compléter la fonction antecedents qui prend en paramètres deux tableaux tetes et suivants, un entier j, et renvoie la liste des antécédents de j.
La méthode décrite ci-dessus n'est pas du tout adaptée pour certaines valeurs de \(n\) et \(m\). Un exemple extrème est par exemple images = [0, 100]. Le tableau tetes contient alors \(101\) valeurs dont \(99\) sont égales à \(-1\).
L'idée qui apparaît déjà avec les tableaux tetes et suivants est d'utiliser des listes chainées. Un maillon contient un entier et un accès au maillon suivant.
3. Avec une liste chaînée
Dans la suite, un objet maillon sera une instance de la classe Entier:
Compléter les méthodes __init__ et ajouter de la classe ImageRec. Une instance de cette classe, ImageRec(images, j) est une liste chainée composée des antécédents de \(j\).
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)