Listes récursives
Énoncé
On va écrire dans cette séance des fonctions récursives pour manipuler des listes chaînées. On travaillera sur des listes chaînées simples sans élément fictif en tête, en utilisant la classe Cellule habituelle contenant un champ val et un champ suiv.
Pour chaque question, on réfléchira en identifiant à chaque fois le ou les cas de base (c'est-à-dire le ou les cas pour lesquels la récursivité s'arrêtera) et l'hypothèse de récurrence (c'est-à-dire la façon dont on traitera le cas N en fonction du cas N-1), comme illustré pour la fonction de création fournie dans le squelette de code affiché ci-dessous.
Toutes les fonctions doivent être implantées sans aucune allocation de cellules.
Création de la liste à partir d'un tableau d'entiers
- cas de base : si le tableau est de taille nulle alors la liste est vide ;
- hypothèse de récurrence : si L' est la liste créée à partir de tous les éléments du tableau sauf le premier, alors L est la liste créée en insérant le premier élément du tableau en tête de L'.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 | #!/usr/bin/env python3
"""
Manipulations récursives de listes chainees
"""
from random import randint
from cellule import Cellule
def creer(tab):
"""
Construit la liste en inserant les valeurs du tableau.
Les elements doivent apparaitre dans le meme ordre.
Renvoie la liste construite.
Cas de base :
- si le tableau est de taille 0 alors la liste renvoyee est vide
Hypothese de recurrence :
- si L' est la liste créée à partir de tous les elements du tableau
sauf le premier alors L est la liste créée en insérant
le premier element du tableau en tete de L'
"""
if len(tab) == 0:
return None
liste_p = creer(tab[1:])
return Cellule(tab[0], liste_p)
def main():
"""
Fonction principale
"""
for taille in range(8):
print(f"-- Taille = {taille} --")
tab = [randint(0, 9) for _ in range(taille)]
print("Tableau initial :", tab)
liste = creer(tab)
print("Liste initiale : ", end="")
afficher(liste)
liste1, liste2 = separer(liste)
print("Listes separees :")
print(" ", end="")
afficher(liste1)
print(" ", end="")
afficher(liste2)
liste = trier(creer(tab))
print("Liste triee : ", end="")
afficher(liste)
print()
# tests de la fonction fusionner avec des listes deja triees
tabs = (([], []), ([], [1]), ([2], []), ([1], [2]), ([1, 3], [2]),
([3], [2, 4]), ([1, 5, 7], [2, 4, 6, 8]))
for tab1, tab2 in tabs:
print(f"Fusion de {tab1} et {tab2} :")
liste = fusionner(creer(tab1), creer(tab2))
print(" liste fusionnee : ", end="")
afficher(liste)
print()
main()
|
Affichage d'une liste chaînée
Écrire une fonction afficher(liste) affichant le contenu de la liste chaînée.
Découpage de la liste en deux sous-listes
Écrire une fonction separer(liste) qui découpe la liste en deux sous-listes composées des mêmes éléments que la liste et dans le même ordre, en répartissant un élément sur deux dans chaque sous-liste. La fonction renvoie les deux sous-listes à la fin sous la forme d'un tuple.
Fusion de deux listes triées
Écrire une fonction fusionner(liste1, liste2) qui prend deux listes triées par ordre croissant en paramètre et renvoie la liste triée par ordre croissant constituée des éléments des deux sous-listes.
Tri d'une liste chaînée
Écrire une fonction trier(liste) qui trie la liste chaînée passée en paramètre en implantant l'algorithme suivant :
- on sépare la liste en deux sous-listes liste1 et liste2 ;
- on trie les sous-listes liste1 et liste2 ;
- on fusionne les sous-listes liste1 et liste2 pour produire la liste triée.
Correction
Cliquez ici pour révéler la correction.
liste_rec.py :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140 | #!/usr/bin/env python3
"""
Manipulations récursives de listes chainees
"""
from random import randint
from cellule import Cellule
def creer(tab):
"""
Construit la liste en inserant les valeurs du tableau.
Les elements doivent apparaitre dans le meme ordre.
Renvoie la liste construite.
Cas de base :
- si le tableau est de taille 0 alors la liste renvoyee est vide
Hypothese de recurrence :
- si L' est la liste créée à partir de tous les elements du tableau
sauf le premier alors L est la liste créée en insérant
le premier element du tableau en tete de L'
"""
if len(tab) == 0:
return None
liste_p = creer(tab[1:])
return Cellule(tab[0], liste_p)
def afficher(liste):
"""
Affiche la liste
Cas de base :
- si la liste est nulle alors on affiche "Fin" et on va a la ligne
- Hypothese de recurrence :
- si Prem est le premier element de la liste alors on affiche Prem suivi
de la fin de L (i.e. L sans Prem)
"""
if liste is None:
print("FIN")
else:
print(liste, end="")
afficher(liste.suiv)
def separer(liste):
"""
Decoupe la liste en deux listes.
On repartit les elements un sur deux dans chaque liste.
Renvoie un tuple contenant les deux listes.
Cas de base :
- si la liste L est nulle alors L1 et L2 sont nulles aussi
- sinon si L ne contient qu'un element, alors on place cet
element dans L1 et L2 est nulle
Hypothese de recurrence :
- si L1' et L2' sont issues de la separation de L privee de
ses deux premiers elements (Prem et Deux dans l'ordre),
alors on obtient L1 en inserant Prem en tete de L1' et L2
en inserant Deux en tete de L2'
"""
if liste is None:
return (None, None)
if liste.suiv is None:
return (liste, None)
prem = liste
deux = liste.suiv
liste1_p, liste2_p = separer(liste.suiv.suiv)
prem.suiv = liste1_p
deux.suiv = liste2_p
return (prem, deux)
def fusionner(liste1, liste2):
"""
Cas de base :
- si L1 est nulle alors L est egale a L2
- sinon si L2 est nulle alors L est egale a L1
Hypothese de recurrence :
- si le premier element de L1 (Prem1) est inferieur au premier
element de L2 (Prem2), alors si L' est issue de la fusion
de la fin de L1 et de L2, on obtient L en inserant Prem1
en tete de L'
- sinon, idem avec Prem2 et L2
"""
prem1 = liste1
prem2 = liste2
if liste1 is None:
return liste2
if liste2 is None:
return liste1
if prem1.val <= prem2.val:
liste_p = fusionner(liste1.suiv, liste2)
prem1.suiv = liste_p
return prem1
liste_p = fusionner(liste1, liste2.suiv)
prem2.suiv = liste_p
return prem2
def trier(liste):
"""
Cas de base :
- si L est vide ou ne contient qu'un element, L est deja triee
Hypothese de recurrence :
- si L1 et L2 sont issues de la separation de L, on obtient
L triee en triant L1 et L2 et en les fusionnant ensuite
"""
if liste is None or liste.suiv is None:
return liste
liste1, liste2 = separer(liste)
liste1_p = trier(liste1)
liste2_p = trier(liste2)
return fusionner(liste1_p, liste2_p)
def main():
"""
Fonction principale
"""
for taille in range(8):
print(f"-- Taille = {taille} --")
tab = [randint(0, 9) for _ in range(taille)]
print("Tableau initial :", tab)
liste = creer(tab)
print("Liste initiale : ", end="")
afficher(liste)
liste1, liste2 = separer(liste)
print("Listes separees :")
print(" ", end="")
afficher(liste1)
print(" ", end="")
afficher(liste2)
liste = trier(creer(tab))
print("Liste triee : ", end="")
afficher(liste)
print()
# tests de la fonction fusionner avec des listes deja triees
tabs = (([], []), ([], [1]), ([2], []), ([1], [2]), ([1, 3], [2]),
([3], [2, 4]), ([1, 5, 7], [2, 4, 6, 8]))
for tab1, tab2 in tabs:
print(f"Fusion de {tab1} et {tab2} :")
liste = fusionner(creer(tab1), creer(tab2))
print(" liste fusionnee : ", end="")
afficher(liste)
print()
main()
|