Mme Tortue et M. Lièvre font la course
On s'intéresse dans cet exercice à des listes chaînées. Une cellule d'une liste chaînée est une instance de la classe Cellule ci-dessous.
La classe Cellule
class Cellule():
def __init__(self):
self.suivante = None
On fournit un exemple d'utilisation créant une liste chaînée contenant 18 éléments. Étudiez bien ce programme pour comprendre la suite et testez vos modifications pour bien comprendre la structure de la liste.
tete = Cellule()
actuelle = tete
for i in range(1, 18):
actuelle.suivante = Cellule()
actuelle = actuelle.suivante
Le plus souvent, la dernière cellule n'a pas de successeur. Dans ce cas, l'attribut suivante de la cellule en question vaut None.
Il arrive toutefois que cet attribut pointe vers une des cellules précédentes, ce qui forme une boucle. Le parcours d'une telle liste chaînée ne se termine jamais.
Une liste chaînée comportant une boucle
graph LR
0[0]-->1[1]
1[1]-->2[2]
2[2]-- ... de 3 à 10 ... -->11[11]
11[11]-->12[12]
12[12]-->13[13]
13[13]-->14[14]
14[14]-->15[15]
15[15]-->16[16]
16[16]-->17[17]
17[17]-->13[13]Les numéros correspondent à la position de la cellule dans la liste chaînée.
Cette liste chaînée peut être construite par les instructions suivantes :
tete = Cellule()
actuelle = tete
for i in range(1, 18):
actuelle.suivante = Cellule()
actuelle = actuelle.suivante
if i == 13:
debut_boucle = actuelle
actuelle.suivante = debut_boucle # la suivante de la n°17 devient la n°13
Il existe un moyen très simple de détecter une boucle. Cet algorithme est dû à Robert Floyd.
Supposons deux variables lievre et tortue qui prennent comme valeurs des cellules d'une liste chaînée, en commençant par la tete. tortue passe d'une cellule à sa suivante alors que lievre passe directement d'une cellule à la suivante de sa suivante. Autrement dit, lievre fait deux pas quand tortue n'en fait qu'un.
On représente dans le tableau ci-dessous les positions respectives de lievre et tortue au fil du parcours. Le tableau s'arrête lorsque tortue == lievre.
| Etape | 0 | 1 | 2 | ... | 6 | 7 | 8 | 9 | ... | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|
Position de tortue |
0 | 1 | 2 | ... | 6 | 7 | 8 | 9 | ... | 14 | 15 |
Position de lievre |
0 | 2 | 4 | ... | 12 | 14* | 16 | 13 | ... | 13 | 15 |
Lorsque lievre entre dans la boucle (noté avec une astérisque *), il se met à tourner en rond. Au bout d'un moment, tortue le rattrape et se trouve sur la même cellule que lui. Quand la condition lievre == tortue devient vraie, nous savons qu'il y a une boucle.
Si par contre, lievre atteint la fin de la liste chaînée avant d'avoir été « rattrapé » par tortue, la liste ne contient pas de boucle.
Pourquoi ça marche ?
Appelons \(\lambda\) le nombre de cellules dans la boucle. Dans notre exemple, \(\lambda = 5\).
graph LR;
0[0]-->1[1]
1[1]-->2[2]
2[2]-- ... de 3 à 10 ... -->11[11]
11[11]-->12[12]
12[12]-->13[13]
subgraph "Boucle (λ = 5)"
13[13]-->14[14]
14[14]-->15[15]
15[15]-->16[16]
16[16]-->17[17]
17[17]-->13[13]
endDe manière générale, nous savons que lorsque tortue a effectué \(x\) pas, lievre en a effectué \(2x\). De plus, à partir d'une des cellules comprises dans la boucle, si lievre avance d'un multiple de \(\lambda\) cellules, il fait un tour complet et se retrouve sur la même cellule.
Lorsque tortue arrive sur une cellule de la boucle dont le numéro est un multiple de \(\lambda\)1 (dans l'exemple la cellule à la position \(15 = 3\times 5\)) elle se trouve sur à une position de la forme \(k\lambda\).
Dans ce cas, lievre a effectué \(2 k \lambda = k \lambda + k \lambda\) pas. Autrement dit, il a effectué \(k\) tours complets depuis la cellule numéro \(k \lambda\) où se trouve actuellement la tortue.
tortue et lievre sont donc à la même position.
Écrivez la fonction qui détermine la présence d'une boucle dans la liste chaînée tete passée en argument. On garantit que la liste est non vide.
# Tests (insensible à la casse)(Ctrl+I)
-
On peut en effet montrer qu'une boucle de longueur \(\lambda\) contient toujours une cellule dont la position est un multiple de \(\lambda\). ↩
# Tests(insensible à la casse)(Ctrl+I)