from sys import version
print(version)
3.5.3 (default, Jan 19 2017, 14:11:04) [GCC 6.3.0 20170118]
Ces exercices sont un peu foireux : les "listes" en Python ne sont pas des listes simplement chaînées !
taille¶from typing import TypeVar, List
_a = TypeVar('alpha')
def taille(liste : List[_a]) -> int:
longueur = 0
for _ in liste:
longueur += 1
return longueur
taille([])
taille([1, 2, 3])
0
3
len([])
len([1, 2, 3])
0
3
concat¶from typing import TypeVar, List
_a = TypeVar('alpha')
def concatene(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
# return liste1 + liste2 # easy solution
liste = []
for i in liste1:
liste.append(i)
for i in liste2:
liste.append(i)
return liste
concatene([1, 2], [3, 4])
[1, 2] + [3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]
Mais attention le typage est toujours optionnel en Python :
concatene([1, 2], ["pas", "entier", "?"])
[1, 2, 'pas', 'entier', '?']
appartient¶from typing import TypeVar, List
_a = TypeVar('alpha')
def appartient(x : _a, liste : List[_a]) -> bool:
for y in liste:
if x == y:
return True # on stoppe avant la fin
return False
appartient(1, [])
appartient(1, [1])
appartient(1, [1, 2, 3])
appartient(4, [1, 2, 3])
False
True
True
False
1 in []
1 in [1]
1 in [1, 2, 3]
4 in [1, 2, 3]
False
True
True
False
Notre implémentation est évidemment plus lente que le test x in liste de la librarie standard...
Mais pas tant :
%timeit appartient(1000, list(range(10000)))
%timeit 1000 in list(range(10000))
173 µs ± 4.68 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 166 µs ± 6.56 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
miroir¶from typing import TypeVar, List
_a = TypeVar('alpha')
def miroir(liste : List[_a]) -> List[_a]:
# return liste[::-1] # version facile
liste2 = []
for x in liste:
liste2.insert(0, x)
return liste2
miroir([2, 3, 5, 7, 11])
[2, 3, 5, 7, 11][::-1]
[11, 7, 5, 3, 2]
[11, 7, 5, 3, 2]
%timeit miroir([2, 3, 5, 7, 11])
%timeit [2, 3, 5, 7, 11][::-1]
968 ns ± 67.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 216 ns ± 8.77 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
alterne¶La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :
from typing import TypeVar, List
_a = TypeVar('alpha')
def alterne(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
liste3 = []
i, j = 0, 0
n, m = len(liste1), len(liste2)
while i < n and j < m: # encore deux
liste3.append(liste1[i])
i += 1
liste3.append(liste2[j])
j += 1
while i < n: # si n > m
liste3.append(liste1[i])
i += 1
while j < m: # ou si n < m
liste3.append(liste2[j])
j += 1
return liste3
alterne([3, 5], [2, 4, 6])
alterne([1, 3, 5], [2, 4, 6])
alterne([1, 3, 5], [4, 6])
[3, 2, 5, 4, 6]
[1, 2, 3, 4, 5, 6]
[1, 4, 3, 6, 5]
La complexité est linéaire en $\mathcal{O}(\max(|\text{liste 1}|, |\text{liste 2}|)$.
nb_occurrences¶from typing import TypeVar, List
_a = TypeVar('alpha')
def nb_occurrences(x : _a, liste : List[_a]) -> int:
nb = 0
for y in liste:
if x == y:
nb += 1
return nb
nb_occurrences(0, [1, 2, 3, 4])
nb_occurrences(2, [1, 2, 3, 4])
nb_occurrences(2, [1, 2, 2, 3, 2, 4])
nb_occurrences(5, [1, 2, 3, 4])
0
1
3
0
pairs¶C'est un filtrage :
filter?
from typing import List
def pairs(liste : List[int]) -> List[int]:
# return list(filter(lambda x : x % 2 == 0, liste))
return [x for x in liste if x % 2 == 0]
pairs([1, 2, 3, 4, 5, 6])
pairs([1, 2, 3, 4, 5, 6, 7, 100000])
pairs([1, 2, 3, 4, 5, 6, 7, 100000000000])
pairs([1, 2, 3, 4, 5, 6, 7, 1000000000000000000])
[2, 4, 6]
[2, 4, 6, 100000]
[2, 4, 6, 100000000000]
[2, 4, 6, 1000000000000000000]
range¶from typing import List
def myrange(n : int) -> List[int]:
liste = []
i = 1
while i <= n:
liste.append(i)
i += 1
return liste
myrange(4)
[1, 2, 3, 4]
from typing import List
def intervale(a : int, b : int=None) -> List[int]:
if b == None:
a, b = 1, a
liste = []
i = a
while i <= b:
liste.append(i)
i += 1
return liste
intervale(10)
intervale(1, 4)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4]
premiers¶Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtration. Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtration (filtrage ? pattern matching)
def racine(n : int) -> int:
i = 1
for i in range(n + 1):
if i*i > n:
return i - 1
return i
racine(1)
racine(5)
racine(102)
racine(120031)
1
2
10
346
from typing import List
def intervale2(a : int, b : int, pas : int=1) -> List[int]:
assert pas > 0
liste = []
i = a
while i <= b:
liste.append(i)
i += pas
return liste
intervale2(2, 12, 1)
intervale2(2, 12, 3)
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[2, 5, 8, 11]
Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.
def estDivisible(n : int, k : int) -> bool:
return (n % k) == 0
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)
True
False
False
True
def estPremier(n : int) -> bool:
return (n == 2) or (n == 3) or not any(map(lambda k: estDivisible(n, k), intervale2(2, racine(n), 1)))
for n in range(2, 20):
print(n, list(map(lambda k: estDivisible(n, k), intervale2(2, racine(n), 1))))
2 [] 3 [] 4 [True] 5 [False] 6 [True] 7 [False] 8 [True] 9 [False, True] 10 [True, False] 11 [False, False] 12 [True, True] 13 [False, False] 14 [True, False] 15 [False, True] 16 [True, False, True] 17 [False, False, False] 18 [True, True, False] 19 [False, False, False]
from typing import List
def premiers(n : int) -> List[int]:
return [p for p in intervale2(2, n, 1) if estPremier(p)]
premiers(10)
[2, 3, 5, 7]
premiers(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Comme ces exercices étaient un peu foireux à écrire avec les "listes" de Python, qui ne sont pas des listes simplement chaînées, je propose une autre solution où l'on va définir une petite classe qui représentera une liste simplement chaînée, et on va écrire les fonctions demandées avec cette classe.
ListeChainee¶On va supposer que les listes que l'on représentera ne contiendront pas la valeur None, qui est utilisée pour représenter l'absence de tête et/ou de queue de la liste.
class ListeChainee():
def __init__(self, hd=None, tl=None):
self.hd = hd
self.tl = tl
def __repr__(self) -> str:
if self.tl is None:
if self.hd is None:
return "[]"
else:
return f"{self.hd} :: []"
else:
return f"{self.hd} :: {self.tl}"
def jolie(self) -> str:
if self.tl is None:
if self.hd is None:
return "[]"
else:
return f"[{self.hd}]"
else:
j = self.tl.jolie()
j = j.replace("[", "").replace("]", "")
if j == "":
return f"[{self.hd}]"
else:
return f"[{self.hd}, {j}]"
# équivalent à :: en OCaml
def insert(hd, tl: ListeChainee) -> ListeChainee:
""" Insère hd en début de la liste chainée tl."""
return ListeChainee(hd=hd, tl=tl)
# liste vide, puis des listes plus grandes
vide = ListeChainee() # []
l_1 = insert(1, vide) # 1 :: [] ~= [1]
l_12 = insert(2, l_1) # 2 :: 1 :: [] ~= [2, 1]
l_123 = insert(3, l_12) # 3 :: 2 :: 1 :: []
print(vide) # []
print(l_1) # 1 :: []
print(l_12) # 2 :: 1 :: []
print(l_123) # 3 :: 2 :: 1 :: []
[] 1 :: [] 2 :: 1 :: [] 3 :: 2 :: 1 :: []
print(vide.jolie()) # []
print(l_1.jolie()) # [1]
print(l_12.jolie()) # [2, 1]
print(l_123.jolie()) # [3, 2, 1]
[] [1] [2, 1] [3, 2, 1]
taille¶Par exemple la longueur sera bien en O(n) si n=taille(liste) avec cette approche récursive :
from typing import Optional
def taille(liste: Optional[ListeChainee]) -> int:
if liste is None:
return 0
elif liste.tl is None:
return 0 if liste.hd is None else 1
return 1 + taille(liste.tl)
print(taille(vide)) # 0
print(taille(l_1)) # 1
print(taille(l_12)) # 2
print(taille(l_123)) # 3
0 1 2 3
concat¶Je vais déjà commencer par écrire une fonction copy qui permet de copier récursivement une liste simplement chaînée, pour être sûr que l'on ne modifie pas en place une des listes données en argument.
def copy(liste: ListeChainee) -> ListeChainee:
if liste.tl is None:
return ListeChainee(hd=liste.hd, tl=None)
else:
return ListeChainee(hd=liste.hd, tl=copy(liste.tl))
On peut vérifier que cela marche en regardant, par exemple, l'id de deux objets si le deuxième est une copie du premier : les id seront bien différents.
print(id(vide))
print(id(copy(vide)))
140493199182984 140493191884136
Et donc pour concaténer deux chaînes, c'est facile :
def concat(liste1: ListeChainee, liste2: ListeChainee) -> ListeChainee:
if taille(liste1) == 0:
return liste2
elif taille(liste2) == 0:
return liste1
# nouvelle liste : comme ça changer queue.tl ne modifie PAS liste1
resultat = copy(liste1)
queue = resultat
while taille(queue.tl) > 0:
queue = queue.tl
assert taille(queue.tl) == 0
queue.tl = ListeChainee(hd=liste2.hd, tl=liste2.tl)
return resultat
print(concat(vide, l_1))
print(vide) # pas modifiée : []
print(l_1) # pas modifiée : 1 :: []
1 :: [] [] 1 :: []
concat(l_1, l_12) # 1 :: 2 :: 1 :: []
1 :: 2 :: 1 :: []
concat(l_1, l_123) # 1 :: 3 :: 2 :: 1 :: []
1 :: 3 :: 2 :: 1 :: []
concat(l_1, vide) # 1 :: []
1 :: []
concat(l_12, vide) # 2 :: 1 :: []
2 :: 1 :: []
concat(l_12, l_1) # 2 :: 1 :: 1 :: []
2 :: 1 :: 1 :: []
concat(l_123, l_123) # 3 :: 2 :: 1 :: 3 :: 2 :: 1 :: []
3 :: 2 :: 1 :: 3 :: 2 :: 1 :: []
appartient¶C'est en complexité linéaire dans le pire des cas.
def appartient(x, liste: ListeChainee) -> bool:
if liste.hd is None:
return False
else:
if liste.hd == x:
return True
else:
return appartient(x, liste.tl)
assert appartient(0, vide) == False
assert appartient(0, l_1) == False
assert appartient(0, l_12) == False
assert appartient(0, l_123) == False
assert appartient(1, l_1) == True
assert appartient(1, l_12) == True
assert appartient(1, l_123) == True
assert appartient(2, l_1) == False
assert appartient(2, l_12) == True
assert appartient(2, l_123) == True
assert appartient(3, l_1) == False
assert appartient(3, l_12) == False
assert appartient(3, l_123) == True
miroir¶Ce sera en temps quadratique, à cause de toutes les recopies :
def miroir(liste: ListeChainee) -> ListeChainee:
if taille(liste) <= 1:
return copy(liste)
else:
hd, tl = liste.hd, copy(liste.tl) # O(n)
juste_hd = ListeChainee(hd=hd, tl=None) # O(1)
return concat(miroir(tl), juste_hd) # O(n^2) + O(n) à cause de concat
print(miroir(vide)) # [] => []
print(miroir(l_1)) # [1] => [1]
print(miroir(l_12)) # [2, 1] => [1, 2]
print(miroir(l_123)) # [3, 2, 1] => [1, 2, 3]
[] 1 :: [] 1 :: 2 :: [] 1 :: 2 :: 3 :: []
alterne¶La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :
def alterne(liste1: ListeChainee, liste2: ListeChainee) -> ListeChainee:
if taille(liste1) == 0:
return copy(liste2) # on recopie pour ne rien modifier
if taille(liste2) == 0:
return copy(liste1) # on recopie pour ne rien modifier
h1, t1 = liste1.hd, liste1.tl
h2, t2 = liste2.hd, liste2.tl
return insert(h1, insert(h2, alterne(t1, t2)))
print(alterne(l_1, l_12)) # [1, 2, 1]
print(alterne(l_12, l_1)) # [2, 1, 1]
print(alterne(l_123, l_1)) # [3, 1, 2, 1]
print(alterne(l_123, l_12)) # [3, 2, 2, 1, 1]
print(alterne(l_123, l_123)) # [3, 3, 2, 2, 1, 1]
print(alterne(l_12, l_123)) # [2, 3, 1, 2, 1]
print(alterne(l_1, l_123)) # [1, 3, 2, 1]
1 :: 2 :: 1 :: [] 2 :: 1 :: 1 :: [] 3 :: 1 :: 2 :: 1 :: [] 3 :: 2 :: 2 :: 1 :: 1 :: [] 3 :: 3 :: 2 :: 2 :: 1 :: 1 :: [] 2 :: 3 :: 1 :: 2 :: 1 :: [] 1 :: 3 :: 2 :: 1 :: []
La complexité est quadratique en $\mathcal{O}((\max(|\text{liste 1}|, |\text{liste 2}|)^2)$ à cause des recopies.
nb_occurrences¶Ce sera en temps linéaire, dans tous les cas.
def nb_occurrences(x, liste: ListeChainee) -> int:
if liste is None or liste.hd is None:
return 0
else:
count = 1 if x == liste.hd else 0
if liste.tl is None:
return count
else:
return count + nb_occurrences(x, liste.tl)
assert nb_occurrences(1, vide) == 0
assert nb_occurrences(1, l_1) == 1
assert nb_occurrences(1, l_12) == 1
assert nb_occurrences(2, l_12) == 1
assert nb_occurrences(1, l_123) == 1
assert nb_occurrences(2, l_123) == 1
assert nb_occurrences(3, l_123) == 1
assert nb_occurrences(1, concat(l_1, l_1)) == 2
assert nb_occurrences(2, concat(l_1, l_12)) == 1
assert nb_occurrences(3, concat(l_12, l_1)) == 0
assert nb_occurrences(1, concat(l_12, l_12)) == 2
assert nb_occurrences(2, concat(l_12, l_12)) == 2
assert nb_occurrences(1, concat(l_123, concat(l_1, l_1))) == 3
assert nb_occurrences(2, concat(l_123, concat(l_1, l_12))) == 2
assert nb_occurrences(3, concat(l_123, concat(l_12, l_1))) == 1
assert nb_occurrences(3, concat(l_123, concat(l_12, l_12))) == 1
On peut facilement écrire une variante qui sera récursive terminale ("tail recursive") :
def nb_occurrences(x, liste: ListeChainee, count=0) -> int:
if liste is None or liste.hd is None:
return count
else:
count += 1 if x == liste.hd else 0
if liste.tl is None:
return count
else:
return nb_occurrences(x, liste.tl, count=count)
pairs¶C'est un filtrage par le prédicat x % 2 == 0.
Autant écrire la fonction de filtrage générique :
def filtrer(liste: ListeChainee, predicate) -> ListeChainee:
if liste is None or liste.hd is None: # liste de taille 0
return ListeChainee(hd=None, tl=None)
elif liste.tl is None: # liste de taille 1
if predicate(liste.hd): # on renvoie [hd]
return ListeChainee(hd=liste.hd, tl=None)
else: # on renvoie []
return ListeChainee(hd=None, tl=None)
else: # liste de taille >= 2
if predicate(liste.hd):
return insert(liste.hd, filtrer(liste.tl, predicate))
else:
return filtrer(liste.tl, predicate)
Et donc c'est rapide :
def pairs(liste: ListeChainee) -> ListeChainee:
def predicate(x):
return (x % 2) == 0
# aussi : predicate = lambda x: (x % 2) == 0
return filtrer(liste, predicate)
def impairs(liste: ListeChainee) -> ListeChainee:
def predicate(x):
return (x % 2) == 1
return filtrer(liste, predicate)
print(pairs(vide)) # []
print(pairs(l_1)) # []
print(pairs(l_12)) # [2]
print(pairs(l_123)) # [2]
print(pairs(insert(4, insert(6, insert(8, l_123))))) # [4, 6, 8, 2]
print(pairs(insert(5, insert(6, insert(8, l_123))))) # [6, 8, 2]
[] [] 2 :: [] 2 :: [] 4 :: 6 :: 8 :: 2 :: [] 6 :: 8 :: 2 :: []
print(impairs(vide)) # []
print(impairs(l_1)) # [1]
print(impairs(l_12)) # [1]
print(impairs(l_123)) # [3, 1]
print(impairs(insert(4, insert(6, insert(8, l_123))))) # [3, 1]
print(impairs(insert(5, insert(6, insert(8, l_123))))) # [5, 3, 1]
[] 1 :: [] 1 :: [] 3 :: 1 :: [] 3 :: 1 :: [] 5 :: 3 :: 1 :: []
range¶Ce sera de complexité temporelle linéaire :
def myrange(n: int) -> ListeChainee:
if n <= 0:
return ListeChainee(hd=None, tl=None)
elif n == 1:
return ListeChainee(hd=1, tl=None)
# return insert(1, vide)
else:
return ListeChainee(hd=n, tl=myrange(n-1))
print(myrange(1)) # [1]
print(myrange(2)) # [1, 2]
print(myrange(3)) # [1, 2, 3]
print(myrange(4)) # [1, 2, 3, 4]
1 :: [] 2 :: 1 :: [] 3 :: 2 :: 1 :: [] 4 :: 3 :: 2 :: 1 :: []
Si on veut les avoir dans l'ordre croissant, il faudrait utiliser miroir qui est quadratique.
Autant écrire directement une fonction intervale(a, b) qui renvoie la liste simplement chaînée contenant a :: (a+1) :: ... :: b :
def intervale(a: int, b: Optional[int]=None) -> ListeChainee:
if b is None:
a, b = 1, a
n = b - a
if n < 0: # [a..b] = []
return ListeChainee(hd=None, tl=None)
elif n == 0: # [a..b] = [a]
return ListeChainee(hd=a, tl=None)
else: # [a..b] = a :: [a+1..b]
return ListeChainee(hd=a, tl=intervale(a+1, b))
print(intervale(10)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(intervale(1, 4)) # [1, 2, 3, 4]
print(intervale(13, 13)) # [13]
print(intervale(13, 10)) # []
1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: 8 :: 9 :: 10 :: [] 1 :: 2 :: 3 :: 4 :: [] 13 :: [] []
Une autre approche est d'écrire la fonction mymap et de dire que
intervale_bis(a, b) = miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))
from typing import Callable
def mymap(fonction: Callable, liste: ListeChainee) -> ListeChainee:
if liste is None or liste.hd is None: # liste de taille 0
return ListeChainee(hd=None, tl=None)
elif liste.tl is None: # liste de taille 1
return ListeChainee(hd=fonction(liste.hd), tl=None)
else: # liste de taille >= 2
return ListeChainee(hd=fonction(liste.hd), tl=mymap(fonction, liste.tl))
print(myrange(10))
print(mymap(lambda x: x, myrange(10)))
10 :: 9 :: 8 :: 7 :: 6 :: 5 :: 4 :: 3 :: 2 :: 1 :: [] 10 :: 9 :: 8 :: 7 :: 6 :: 5 :: 4 :: 3 :: 2 :: 1 :: []
def intervale_bis(a: int, b: int) -> ListeChainee:
return miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))
print(intervale_bis(1, 10)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(intervale_bis(1, 4)) # [1, 2, 3, 4]
print(intervale_bis(13, 13)) # [13]
print(intervale_bis(13, 10)) # []
1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: 8 :: 9 :: 10 :: [] 1 :: 2 :: 3 :: 4 :: [] 13 :: [] []
premiers¶Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtrage. Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtrage.
On a besoin des fonctions suivantes :
def racine(n: int) -> int:
i = 1
for i in range(n + 1):
if i*i > n:
return i - 1
return i
print(racine(1)) # 1
print(racine(5)) # 2
print(racine(102)) # 10
print(racine(120031)) # 346
1 2 10 346
def intervale2(a: int, b: Optional[int]=None, pas: int=1) -> ListeChainee:
if b is None:
a, b = 1, a
n = b - a
if n < 0: # [a..b::p] = []
return ListeChainee(hd=None, tl=None)
elif n == 0: # [a..b::p] = [a]
return ListeChainee(hd=a, tl=None)
else: # [a..b::p] = a :: [a+p..b::p]
return ListeChainee(hd=a, tl=intervale2(a + pas, b=b, pas=pas))
print(intervale2(1, 10, 2)) # [1, 3, 5, 7, 9]
print(intervale2(1, 4, 2)) # [1, 3]
print(intervale2(13, 13, 2)) # [13]
print(intervale2(13, 10, 2)) # []
1 :: 3 :: 5 :: 7 :: 9 :: [] 1 :: 3 :: [] 13 :: [] []
Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.
def estDivisible(n: int, k: int) -> bool:
return (n % k) == 0
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)
True
On est prêt à écrire estPremier :
def estPremier(n : int) -> bool:
return taille(filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k))) == 0
En effet il suffit de construire d'abord la liste des entiers impairs de 2 à $\lfloor \sqrt{n} \rfloor$, de les filtrer par ceux qui divisent $n$, et de vérifier si on a aucun diviseur (taille(..) == 0) auquel cas $n$ est premier, ou si $n$ a au moins un diviseur auquel cas $n$ n'est pas premier.
for n in range(2, 20):
print("Petits diviseurs de", n, " -> ", filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k)))
Petits diviseurs de 2 -> [] Petits diviseurs de 3 -> [] Petits diviseurs de 4 -> 2 :: [] Petits diviseurs de 5 -> [] Petits diviseurs de 6 -> 2 :: [] Petits diviseurs de 7 -> [] Petits diviseurs de 8 -> 2 :: [] Petits diviseurs de 9 -> 3 :: [] Petits diviseurs de 10 -> 2 :: [] Petits diviseurs de 11 -> [] Petits diviseurs de 12 -> 2 :: 3 :: [] Petits diviseurs de 13 -> [] Petits diviseurs de 14 -> 2 :: [] Petits diviseurs de 15 -> 3 :: [] Petits diviseurs de 16 -> 2 :: 4 :: [] Petits diviseurs de 17 -> [] Petits diviseurs de 18 -> 2 :: 3 :: [] Petits diviseurs de 19 -> []
On voit dans l'exemple ci dessus les nombres premiers comme ceux n'ayant aucun diviseurs, et les nombres non premiers comme ceux ayant au moins un diviseur.
def premiers(n : int) -> ListeChainee:
return filtrer(intervale2(2, n, 1), estPremier)
premiers(10) # [2, 3, 5, 7]
2 :: 3 :: 5 :: 7 :: []
premiers(100) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
2 :: 3 :: 5 :: 7 :: 11 :: 13 :: 17 :: 19 :: 23 :: 29 :: 31 :: 37 :: 41 :: 43 :: 47 :: 53 :: 59 :: 61 :: 67 :: 71 :: 73 :: 79 :: 83 :: 89 :: 97 :: []
On fera les tris en ordre croissant.
test = [3, 1, 8, 4, 5, 6, 1, 2]
from typing import TypeVar, List
_a = TypeVar('alpha')
def insere(x : _a, liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return [x]
else:
t, q = liste[0], liste[1:]
if x <= t:
return [x] + liste
else:
return [t] + insere(x, q)
def tri_insertion(liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return []
else:
t, q = liste[0], liste[1:]
return insere(t, tri_insertion(q))
tri_insertion(test)
[1, 1, 2, 3, 4, 5, 6, 8]
Complexité en temps $\mathcal{O}(n^2)$.
from typing import TypeVar, List, Callable
_a = TypeVar('alpha')
def insere2(ordre : Callable[[_a, _a], bool], x : _a, liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return [x]
else:
t, q = liste[0], liste[1:]
if ordre(x, t):
return [x] + liste
else:
return [t] + insere2(ordre, x, q)
def tri_insertion2(ordre : Callable[[_a, _a], bool], liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return []
else:
t, q = liste[0], liste[1:]
return insere2(ordre, t, tri_insertion2(ordre, q))
ordre_croissant = lambda x, y: x <= y
tri_insertion2(ordre_croissant, test)
[1, 1, 2, 3, 4, 5, 6, 8]
ordre_decroissant = lambda x, y: x >= y
tri_insertion2(ordre_decroissant, test)
[8, 6, 5, 4, 3, 2, 1, 1]
from typing import TypeVar, List, Tuple
_a = TypeVar('alpha')
def selectionne_min(liste : List[_a]) -> Tuple[_a, List[_a]]:
if len(liste) == 0:
raise ValueError("Selectionne_min sur liste vide")
else:
def cherche_min(mini : _a, autres : List[_a], reste : List[_a]) -> Tuple[_a, List[_a]]:
if len(reste) == 0:
return (mini, autres)
else:
t, q = reste[0], reste[1:]
if t < mini:
return cherche_min(t, [mini] + autres, q)
else:
return cherche_min(mini, [t] + autres, q)
t, q = liste[0], liste[1:]
return cherche_min(t, [], q)
test
selectionne_min(test)
[3, 1, 8, 4, 5, 6, 1, 2]
(1, [2, 1, 6, 5, 4, 8, 3])
(On voit que la liste autre a été inversée)
def tri_selection(liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return []
else:
mini, autres = selectionne_min(liste)
return [mini] + tri_selection(autres)
tri_selection(test)
[1, 1, 2, 3, 4, 5, 6, 8]
Complexité en temps : $\mathcal{O}(n^2)$.
from typing import TypeVar, List, Tuple
_a = TypeVar('alpha')
def separe(liste : List[_a]) -> Tuple[List[_a], List[_a]]:
if len(liste) == 0:
return ([], [])
elif len(liste) == 1:
return ([liste[0]], [])
else:
x, y, q = liste[0], liste[1], liste[2:]
a, b = separe(q)
return ([x] + a, [y] + b)
([3, 8, 5, 1], [1, 4, 6, 2])
test
separe(test)
[3, 1, 8, 4, 5, 6, 1, 2]
([3, 8, 5, 1], [1, 4, 6, 2])
def fusion(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
if (len(liste1), len(liste2)) == (0, 0):
return []
elif len(liste1) == 0:
return liste2
elif len(liste2) == 0:
return liste1
else: # les deux sont non vides
x, a = liste1[0], liste1[1:]
y, b = liste2[0], liste2[1:]
if x <= y:
return [x] + fusion(a, [y] + b)
else:
return [y] + fusion([x] + a, b)
fusion([1, 3, 7], [2, 3, 8])
[1, 2, 3, 3, 7, 8]
def tri_fusion(liste : List[_a]) -> List[_a]:
if len(liste) <= 1:
return liste
else:
a, b = separe(liste)
return fusion(tri_fusion(a), tri_fusion(b))
tri_fusion(test)
[1, 1, 2, 3, 4, 5, 6, 8]
Complexité en temps $\mathcal{O}(n \log n)$.
%timeit tri_insertion(test)
%timeit tri_selection(test)
%timeit tri_fusion(test)
11.8 µs ± 463 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 52.9 µs ± 5.31 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 32.1 µs ± 1.14 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
from sys import setrecursionlimit
setrecursionlimit(100000)
# nécessaire pour tester les différentes fonctions récursives sur de grosses listes
import random
def test_random(n : int) -> List[int]:
return [random.randint(-1000, 1000) for _ in range(n)]
for n in [10, 100, 1000]:
print("\nFor n =", n)
for tri in [tri_insertion, tri_selection, tri_fusion]:
print(" and tri = {}".format(tri.__name__))
%timeit tri(test_random(n))
For n = 10
and tri = tri_insertion
33.2 µs ± 4.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
and tri = tri_selection
85.8 µs ± 4.57 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
and tri = tri_fusion
59.6 µs ± 5.57 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
For n = 100
and tri = tri_insertion
2.01 ms ± 93.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
and tri = tri_selection
4.32 ms ± 123 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
and tri = tri_fusion
1.12 ms ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
For n = 1000
and tri = tri_insertion
758 ms ± 18.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
and tri = tri_selection
1.54 s ± 43.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
and tri = tri_fusion
26.1 ms ± 631 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
applique¶from typing import TypeVar, List, Callable
_a, _b = TypeVar('_a'), TypeVar('_b')
def applique(f : Callable[[_a], _b], liste : List[_a]) -> List[_b]:
# Triche :
return list(map(f, liste))
# 1ère approche :
return [f(x) for x in liste]
# 2ème approche :
fliste = []
for x in liste:
fliste.append(f(x))
return fliste
# 3ème approche
n = len(liste)
if n == 0: return []
fliste = [liste[0] for _ in range(n)]
for i in range(n):
fliste[i] = f(liste[i])
return fliste
def premiers_carres_parfaits(n : int) -> List[int]:
return applique(lambda x : x * x, list(range(1, n + 1)))
premiers_carres_parfaits(12)
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144]
itere¶from typing import TypeVar, List, Callable
_a = TypeVar('_a')
def itere(f : Callable[[_a], None], liste : List[_a]) -> None:
for x in liste:
f(x)
print_int = lambda i: print("{}".format(i))
def affiche_liste_entiers(liste : List[int]) -> None:
print("Debut")
itere(print_int, liste)
print("Fin")
affiche_liste_entiers([1, 2, 4, 5, 12011993])
Debut 1 2 4 5 12011993 Fin
qqsoit et ilexiste¶from typing import TypeVar, List, Callable
_a = TypeVar('_a')
# Comme all(map(f, liste))
def qqsoit(f : Callable[[_a], bool], liste : List[_a]) -> bool:
for x in liste:
if not f(x): return False # arret preliminaire
return True
# Comme any(map(f, liste))
def ilexiste(f : Callable[[_a], bool], liste : List[_a]) -> bool:
for x in liste:
if f(x): return True # arret preliminaire
return False
qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
False
True
%timeit qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
%timeit all(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))
368 ns ± 14.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 495 ns ± 44.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
%timeit any(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))
395 ns ± 41.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 641 ns ± 32.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
appartient version 2¶def appartient_curry(x : _a) -> Callable[[List[_a]], bool]:
return lambda liste: ilexiste(lambda y: x == y, liste)
def appartient(x : _a, liste : List[_a]) -> bool:
return ilexiste(lambda y: x == y, liste)
def toutes_egales(x : _a, liste : List[_a]) -> bool:
return qqsoit(lambda y: x == y, liste)
appartient_curry(1)([1, 2, 3])
appartient(1, [1, 2, 3])
appartient(5, [1, 2, 3])
toutes_egales(1, [1, 2, 3])
toutes_egales(5, [1, 2, 3])
True
True
False
False
False
Est-ce que notre implémentation peut être plus rapide que le test x in liste ?
Non, mais elle est aussi rapide. C'est déjà pas mal !
%timeit appartient(random.randint(-10, 10), [random.randint(-1000, 1000) for _ in range(1000)])
%timeit random.randint(-10, 10) in [random.randint(-1000, 1000) for _ in range(1000)]
1.17 ms ± 25.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 1.1 ms ± 10.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
filtre¶from typing import TypeVar, List, Callable
_a = TypeVar('_a')
# Comme list(filter(f, liste))
def filtre(f : Callable[[_a], bool], liste : List[_a]) -> List[_a]:
# return [x for x in liste if f(x)]
liste2 = []
for x in liste:
if f(x):
liste2.append(x)
return liste2
filtre(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
filtre(lambda x: (x % 2) != 0, [1, 2, 3, 4, 5])
[2, 4]
[1, 3, 5]
Je vous laisse trouver pour premiers.
pairs = lambda liste: filtre(lambda x: (x % 2) == 0, liste)
impairs = lambda liste: filtre(lambda x: (x % 2) != 0, liste)
pairs(list(range(10)))
impairs(list(range(10)))
[0, 2, 4, 6, 8]
[1, 3, 5, 7, 9]
reduit¶from typing import TypeVar, List, Callable
_a = TypeVar('_a')
# Comme list(filter(f, liste))
def reduit_rec(f : Callable[[_a, _b], _a], acc : _a, liste : List[_b]) -> _a:
if len(liste) == 0:
return acc
else:
h, q = liste[0], liste[1:]
return reduit(f, f(acc, h), q)
# Version non récursive, bien plus efficace
def reduit(f : Callable[[_a, _b], _a], acc : _a, liste : List[_b]) -> _a:
acc_value = acc
for x in liste:
acc_value = f(acc_value, x)
return acc_value
Très pratique pour calculer des sommes, notamment.
somme, produit¶from operator import add
somme_rec = lambda liste: reduit_rec(add, 0, liste)
somme = lambda liste: reduit(add, 0, liste)
somme_rec(list(range(10)))
somme(list(range(10)))
sum(list(range(10)))
45
45
45
%timeit somme_rec(list(range(10)))
%timeit somme(list(range(10)))
%timeit sum(list(range(10)))
1.59 µs ± 16.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 1.42 µs ± 85.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 644 ns ± 7.56 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Pour de petites listes, la version récursive est aussi efficace que la version impérative. Chouette !
%timeit somme_rec(list(range(1000)))
%timeit somme(list(range(1000)))
%timeit sum(list(range(1000)))
84.8 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 83.1 µs ± 2.27 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 19.9 µs ± 1.05 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
from operator import mul
produit = lambda liste: reduit(mul, 1, liste)
produit(list(range(1, 6))) # 5! = 120
120
Bonus :
def factorielle(n : int) -> int:
return produit(range(1, n + 1))
for n in range(1, 15):
print("{:>7}! = {:>13}".format(n, factorielle(n)))
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
miroir version 2¶miroir = lambda liste: reduit(lambda l, x : [x] + l, [], liste)
miroir([2, 3, 5, 7, 11])
[11, 7, 5, 3, 2]
Attention en Python, les listes ne sont PAS simplement chainées, donc lambda l, x : [x] + l est en temps linéaire en $|l| = n$, pas en $\mathcal{O}(1)$ comme en Caml/OCaml pour fun l x -> x :: l.
/!\ Les deux dernières parties sont bien plus difficiles en Python qu'en Caml.
from typing import Dict, Optional, Tuple
# Impossible de définir un type récursivement, pas comme en Caml
arbre_bin = Dict[str, Optional[Tuple[Dict, Dict]]]
from pprint import pprint
arbre_test = {'Noeud': (
{'Noeud': (
{'Noeud': (
{'Feuille': None},
{'Feuille': None}
)},
{'Feuille': None}
)},
{'Feuille': None}
)}
pprint(arbre_test)
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
Avec une syntaxe améliorée, on se rapproche de très près de la syntaxe de Caml/OCaml :
Feuille = {'Feuille': None}
Noeud = lambda x, y : {'Noeud': (x, y)}
arbre_test = Noeud(Noeud(Noeud(Feuille, Feuille), Feuille), Feuille)
pprint(arbre_test)
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
Compte le nombre de feuilles et de sommets.
def taille(a : arbre_bin) -> int:
# Pattern matching ~= if, elif,.. sur les clés de la profondeur 1
# du dictionnaire (une seule clé)
if 'Feuille' in a:
return 1
elif 'Noeud' in a:
x, y = a['Noeud']
return 1 + taille(x) + taille(y)
taille(arbre_test) # 7
7
def hauteur(a : arbre_bin) -> int:
if 'Feuille' in a:
return 0
elif 'Noeud' in a:
x, y = a['Noeud']
return 1 + max(hauteur(x), hauteur(y))
hauteur(arbre_test) # 3
3
Bonus. (Écrivez une fonction testant si un arbre étiqueté par des entiers est tournoi.)
Après quelques exercices manipulant cette structure de dictionnaire, écrire la suite n'est pas trop difficile.
from typing import TypeVar, Union, List
F = TypeVar('F')
N = TypeVar('N')
element_parcours = Union[F, N]
parcours = List[element_parcours]
def parcours_prefixe(a : arbre_bin) -> parcours:
if 'Feuille' in a:
return [F]
elif 'Noeud' in a:
g, d = a['Noeud']
return [N] + parcours_prefixe(g) + parcours_prefixe(d)
parcours_prefixe(arbre_test)
[~N, ~N, ~N, ~F, ~F, ~F, ~F]
def parcours_postfixe(a : arbre_bin) -> parcours:
if 'Feuille' in a:
return [F]
elif 'Noeud' in a:
g, d = a['Noeud']
return parcours_postfixe(g) + parcours_postfixe(d) + [N]
parcours_postfixe(arbre_test)
[~F, ~F, ~N, ~F, ~N, ~F, ~N]
def parcours_infixe(a : arbre_bin) -> parcours:
if 'Feuille' in a:
return [F]
elif 'Noeud' in a:
g, d = a['Noeud']
return parcours_infixe(g) + [N] + parcours_infixe(d)
parcours_infixe(arbre_test)
[~F, ~N, ~F, ~N, ~F, ~N, ~F]
Pourquoi ont-ils une complexité quadratique ? La concaténation (@ en OCaml, + en Python) ne se fait pas en temps constant mais linéaire dans la taille de la plus longue liste.
On ajoute une fonction auxiliaire et un argument vus qui est une liste qui stocke les élements observés dans l'ordre du parcours
def parcours_prefixe2(a : arbre_bin) -> parcours:
def parcours(vus, b):
if 'Feuille' in b:
vus.insert(0, F)
return vus
elif 'Noeud' in b:
vus.insert(0, N)
g, d = b['Noeud']
return parcours(parcours(vus, g), d)
p = parcours([], a)
return p[::-1]
parcours_prefixe2(arbre_test)
[~N, ~N, ~N, ~F, ~F, ~F, ~F]
def parcours_postfixe2(a : arbre_bin) -> parcours:
def parcours(vus, b):
if 'Feuille' in b:
vus.insert(0, F)
return vus
elif 'Noeud' in b:
g, d = b['Noeud']
p = parcours(parcours(vus, g), d)
p.insert(0, N)
return p
p = parcours([], a)
return p[::-1]
parcours_postfixe2(arbre_test)
[~F, ~F, ~N, ~F, ~N, ~F, ~N]
def parcours_infixe2(a : arbre_bin) -> parcours:
def parcours(vus, b):
if 'Feuille' in b:
vus.insert(0, F)
return vus
elif 'Noeud' in b:
g, d = b['Noeud']
p = parcours(vus, g)
p.insert(0, N)
return parcours(p, d)
p = parcours([], a)
return p[::-1]
parcours_infixe2(arbre_test)
[~F, ~N, ~F, ~N, ~F, ~N, ~F]
Pour utiliser une file de priorité (priority queue), on utilise le module collections.deque.
from collections import deque
def parcours_largeur(a : arbre_bin) -> parcours:
file = deque()
# fonction avec effet de bord sur la file
def vasy() -> parcours:
if len(file) == 0:
return []
else:
b = file.pop()
if 'Feuille' in b:
# return [F] + vasy()
v = vasy()
v.insert(0, F)
return v
elif 'Noeud' in b:
g, d = b['Noeud']
file.insert(0, g)
file.insert(0, d)
# return [N] + vasy()
v = vasy()
v.insert(0, N)
return v
file.insert(0, a)
return vasy()
parcours_largeur(arbre_test)
[~N, ~N, ~F, ~N, ~F, ~F, ~F]
En remplaçant la file par une pile (une simple list), on obtient le parcours en profondeur, avec la même complexité.
def parcours_profondeur(a : arbre_bin) -> parcours:
pile = []
# fonction avec effet de bord sur la file
def vasy() -> parcours:
if len(pile) == 0:
return []
else:
b = pile.pop()
if 'Feuille' in b:
# return [F] + vasy()
v = vasy()
v.append(F)
return v
elif 'Noeud' in b:
g, d = b['Noeud']
pile.append(g)
pile.append(d)
# return [N] + vasy()
v = vasy()
v.insert(0, N)
return v
pile.append(a)
return vasy()
parcours_profondeur(arbre_test)
[~N, ~N, ~N, ~F, ~F, ~F, ~F]
test_prefixe = parcours_prefixe2(arbre_test)
test_prefixe
[~N, ~N, ~N, ~F, ~F, ~F, ~F]
L'idée de cette solution est la suivante : j'aimerais une fonction récursive qui fasse le travail; le problème c'est que si on prend un parcours prefixe, soit il commence par F et l'arbre doit être une feuille; soit il est de la forme N::q où q n'est plus un parcours prefixe mais la concaténation de DEUX parcours prefixe, on ne peut donc plus appeler la fonction sur q. On va donc écrire une fonction qui prend une liste qui contient plusieurs parcours concaténé et qui renvoie l'arbre correspondant au premier parcours et ce qui n'a pas été utilisé :
from typing import Tuple
def reconstruit_prefixe(par : parcours) -> arbre_bin:
def reconstruit(p : parcours) -> Tuple[arbre_bin, parcours]:
if len(p) == 0:
raise ValueError("parcours invalide pour reconstruit_prefixe")
elif p[0] == F:
return (Feuille, p[1:])
elif p[0] == N:
g, q = reconstruit(p[1:])
d, r = reconstruit(q)
return (Noeud(g, d), r)
# call it
a, p = reconstruit(par)
if len(p) == 0:
return a
else:
raise ValueError("parcours invalide pour reconstruit_prefixe")
reconstruit_prefixe([F])
{'Feuille': None}
reconstruit_prefixe(test_prefixe)
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
Et cet exemple va échouer :
reconstruit_prefixe([N, F, F] + test_prefixe) # échoue
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-25-1df0bb84a92a> in <module>() ----> 1 reconstruit_prefixe([N, F, F] + test_prefixe) # échoue <ipython-input-22-c1349393389b> in reconstruit_prefixe(par) 16 return a 17 else: ---> 18 raise ValueError("parcours invalide pour reconstruit_prefixe") ValueError: parcours invalide pour reconstruit_prefixe
Ce n'est pas évident quand on ne connait pas. L'idée est de se servir d'une file pour stocker les arbres qu'on reconstruit peu à peu depuis les feuilles. La file permet de récupérer les bons sous-arbres quand on rencontre un noeud
largeur_test = parcours_largeur(arbre_test)
largeur_test
[~N, ~N, ~F, ~N, ~F, ~F, ~F]
from collections import deque
def reconstruit_largeur(par : parcours) -> arbre_bin:
file = deque()
# Fonction avec effets de bord
def lire_element(e : element_parcours) -> None:
if e == F:
file.append(Feuille)
elif e == N:
d = file.popleft()
g = file.popleft() # attention à l'ordre !
file.append(Noeud(g, d))
# Applique cette fonction à chaque élement du parcours
for e in reversed(par):
lire_element(e)
if len(file) == 1:
return file.popleft()
else:
raise ValueError("parcours invalide pour reconstruit_largeur")
largeur_test
reconstruit_largeur(largeur_test)
arbre_test
[~N, ~N, ~F, ~N, ~F, ~F, ~F]
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
Le même algorithme (enfin presque, modulo interversion de g et d) avec une pile donne une autre version de la reconstruction du parcours prefixe.
from collections import deque
def reconstruit_prefixe2(par : parcours) -> arbre_bin:
pile = deque()
# Fonction avec effets de bord
def lire_element(e : element_parcours) -> None:
if e == F:
pile.append(Feuille)
elif e == N:
g = pile.pop()
d = pile.pop() # attention à l'ordre !
pile.append(Noeud(g, d))
# Applique cette fonction à chaque élement du parcours
for e in reversed(par):
lire_element(e)
if len(pile) == 1:
return pile.pop()
else:
raise ValueError("parcours invalide pour reconstruit_prefixe2")
prefixe_test = parcours_prefixe2(arbre_test)
prefixe_test
[~N, ~N, ~N, ~F, ~F, ~F, ~F]
reconstruit_prefixe2(prefixe_test)
arbre_test
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}
{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
{'Feuille': None})},
{'Feuille': None})}