class Node:
def __init__ (self, value, next=None):
self.valeur = value
self.suivant = next
def __str__ (self):
return f"({', '.join(map(str, self.to_list()))})"
def to_list(self) -> list:
if self.suivant is None:
return [self.valeur]
return [self.valeur] + self.suivant.to_list()
Sujet de 14h45
1. genAlea
from random import randint
def genAlea(nb_val: int) -> Node:
"""Retourner une liste chaînée de nbVal entiers aléatoires entre 1 et 100.
Args:
nb_val (int): Le nombre d'entiers à générer
Returns:
Node: La liste de nb_val
"""
= None
res for _ in range(nb_val):
= Node(randint(1, 100), res)
res return res
print("12 nombres aléatoires :", genAlea(12))
12 nombres aléatoires : (4, 57, 32, 41, 80, 80, 14, 30, 95, 72, 5, 97)
2. compteSup
def compteSup(L: Node, seuil) -> int:
"""Retourne le nombre de valeurs de L strictement supérieures à seuil.
Args:
L (Node): La liste chaînée.
seuil (comparable): La valeur de seuil (on compte les valeurs strictement supérieures au seuil).
Returns:
int: Le nombre de valeurs strictement supérieurs au seuil.
"""
= 0
nb_vals_sup while L is not None:
if L.valeur > seuil:
+= 1
nb_vals_sup = L.suivant
L return nb_vals_sup
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9, Node(2)))))))
L = 4
seuil print(L, "contient", compteSup(L, seuil), "valeurs strictement supérieures à", seuil)
(3, 1, 4, 1, 5, 9, 2) contient 2 valeurs strictement supérieures à 4
3. dansIntervalle
récursivement
def dansIntervalle(L: Node, a, b) -> Node:
"""Créer une nouvelle liste à partir de L en ne gardant que les éléments dans l'intervalle [a, b].
Args:
L (Node): La liste chaînée de départ.
a (comparable): Le minimum de l'intervalle
b (comparable): Le maximum de l'intervalle
Returns:
Node: Une nouvelle liste pour laquelle on a gardé seulement les élément qui sont dans l'intervalle [a, b].
"""
if a > b:
raise ValueError("a doit être inférieur ou égal à b.")
##### ajouter/enlever un # devant la ligne suivante pour changer d'implémentation #####
if L is None: return None
if a <= L.valeur <= b:
# on garde le node actuel
return Node(L.valeur, dansIntervalle(L.suivant, a, b))
return dansIntervalle(L.suivant, a, b)
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9, Node(2, Node(6, Node(5, Node(3, Node(5, Node(8, Node(9, Node(7, Node(9, Node(3, Node(2, Node(3))))))))))))))))))
L print(dansIntervalle(L, 2, 4))
(3, 4, 2, 3, 3, 2, 3)
4. dansIntervalle
avec un itérateur fonctionnel
def dansIntervalle(L: Node, a, b) -> Node:
"""Créer une nouvelle liste à partir de L en ne gardant que les éléments dans l'intervalle [a, b].
Args:
L (Node): La liste chaînée de départ.
a (comparable): Le minimum de l'intervalle
b (comparable): Le maximum de l'intervalle
Returns:
Node: Une nouvelle liste pour laquelle on a gardé seulement les élément qui sont dans l'intervalle [a, b].
"""
if a > b:
raise ValueError("a doit être inférieur ou égal à b.")
# avec un itérateur fonctionnel
return Lfilter(L, lambda x: a <= x <= b)
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9, Node(2, Node(6, Node(5, Node(3, Node(5, Node(8, Node(9, Node(7, Node(9, Node(3, Node(2, Node(3))))))))))))))))))
L print(dansIntervalle(L, 2, 4))
(3, 4, 2, 3, 3, 2, 3)
Sujet de 15h30
1. genRandom
def genRandom(nbVal: int) -> Node:
"""Créer une liste de nbVal nombres aléatoires entre 0 et 20
Args:
nbVal (int): Le nombre de nombres aléatoires à générer.
Returns:
Node: Une liste chaînée qui contient `nbVal` nombre
aléatoires entre 0 et 20.
"""
if nbVal <= 0:
return None
return Node(randint(0, 20), genRandom(nbVal - 1))
= genRandom(10)
L print(L)
(3, 18, 15, 4, 14, 3, 3, 14, 5, 20)
2. compteInf
def compteInf(L: Node, seuil) -> int:
"""Compter le nombre de valeurs strictement inférieures à `seuil` dans L.
Args:
L (Node): La liste dans laquelle on compte.
seuil: La valeur utilisée pour les comparaisons.
Returns:
int: Le nombre de valeurs dans `L` qui sont
strictement inférieures à `seuil`.
"""
= 0
res while L is not None:
if L.valeur < seuil:
+= 1
res = L.suivant
L return res
print(compteInf(L, 10))
5
3. horsIntervalle
récursivement
def horsIntervalle(L: Node, a, b) -> Node:
"""Retirer les éléments de L qui sont dans [a, b].
Args:
L (Node): La liste que l'on veut filtrer.
a: La valeur minimale de l'intervalle exclue.
b: La valeur maximale de l'intervalle exclue.
Returns:
Node: Une nouvelle liste qui est L sans les élément
de L qui sont compris entre a et b inclus.
"""
if a > b or L is None:
return None
# Si la valeur dépasse en dessous de a ou au dessus de b
if L.valeur < a or L.valeur > b :
# on garde la valeur dan la nouvelle liste
return Node(L.valeur, horsIntervalle(L.suivant, a, b))
# sinon on no garde pas la valeur
return horsIntervalle(L.suivant, a, b)
print(horsIntervalle(L, 5, 10))
(3, 18, 15, 4, 14, 3, 3, 14, 20)
4. horsIntervalleFonc
avec un itérateur fonctionnel
def horsIntervalleFonc(L: Node, a, b) -> Node:
"""Retirer les éléments de L qui sont dans [a, b].
Args:
L (Node): La liste que l'on veut filtrer.
a: La valeur minimale de l'intervalle exclue.
b: La valeur maximale de l'intervalle exclue.
Returns:
Node: Une nouvelle liste qui est L sans les élément
de L qui sont compris entre a et b inclus.
"""
if a > b:
raise ValueError("a doit être inférieur ou égal à b.")
return Lfilter(L, lambda x: x < a or x > b)
print(horsIntervalleFonc(L, 5, 10))
(3, 18, 15, 4, 14, 3, 3, 14, 20)