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
|
def est_dans(tab: list[int], val: int) -> bool:
"""
Recherche la présence de val dans tab.
"""
trouve = False
i = 0
while i < len(tab) and not trouve:
if val == tab[i]:
trouve = True
i += 1
return trouve
def est_dans_rec(tab: list[int], n: int, i: int = 0) -> bool:
"""
Recherche si la valeur n est présente au moins une fois
dans le tableau tab.
Algorithme récursif, i est l'indice de recherche.
"""
if i == len(tab):
return False
elif tab[i] == n:
return True
else:
return est_dans_rec(tab, n, i + 1)
def insere(tab: list[int], n: int, i: int) -> None:
"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm itératif et en place.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
l'algorithme se contente de décaler les valeurs vers
la droite.
"""
dernier_indice = len(tab) - 1
if tab[dernier_indice] != None:
raise Exception("Tableau plein !")
k = dernier_indice
while k > i:
tab[k] = tab[k - 1]
k -= 1
#for k in range(dernier_indice, i, -1):
# tab[k] = tab[k - 1]
tab[i] = n
def insere_rec(tab: list[int], n: int, i: int, k: int) -> None:
"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm récursif et en place. k est l'indice de
recherche.
Sa première valeur doit être len(tab) - 1.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas
assurée, l'algorithme se contente de décaler
les valeurs vers la droite.
"""
dernier_indice = len(tab) - 1
if tab[dernier_indice] != None and k == dernier_indice:
raise Exception("Tableau plein !")
elif k == i:
tab[i] = n
return None
else:
tab[k] = tab[k - 1]
return insere_rec(tab, n, i, k - 1)
if __name__ == "__main__":
tab = [i for i in range(20)]
assert est_dans(tab, 12) == True
assert est_dans(tab, 0) == True
assert est_dans(tab, 20) == False
assert est_dans_rec(tab, 12) == True
assert est_dans_rec(tab, 0) == True
assert est_dans_rec(tab, 20) == False
print("Insertion itérative")
tab = [1, 1, 2, 3, 4, 5, None, None, None]
print(tab)
insere(tab, 7, 0)
print(tab)
insere(tab, 7, 0)
print(tab)
insere(tab, 7, 0)
print(tab)
#insere(tab, 7, 0)
#print(tab)
print()
print("Insertion récursive")
tab = [1, 1, 2, 3, 4, 5, None, None, None]
print(tab)
insere_rec(tab, 7, 0, len(tab) - 1)
print(tab)
insere_rec(tab, 7, 0, len(tab) - 1)
print(tab)
insere_rec(tab, 7, 0, len(tab))
print(tab)
|