2-01. Structures de données linéaires

On souhaite implémenter des listes chaînées en Python.

			class Node:
				"""Représente un nœud dans une liste chaînée."""
				def __init__(self, data=None):
					self.data = data   # Donnée stockée
					self.next = None   # Nœud suivant (class Node ou None)
				
				def __str__(self):
					return str(self.data)

			class ChainList:
				"""Implémentation d'une liste chaînée en Python."""
				def __init__(self):
					self.head = None  # Premier élément = None à l’instantiation
					self.size = 0     # Nombre d'éléments dans la liste
				
				def is_empty(self):
					"""Vérifie si la liste est vide."""
					return self.head is None
				
				def _navigate_to(self, index):
					"""méthode "privée" renvoyant l’élément se trouvant à l’index spécifié"""
					if index < 0 or index > self.size-1:
						raise IndexError("Index hors limites")
					
					current = self.head # on part du 1er nœud
					for _ in range (index):
						current = current.next # on navigue jusqu’au nœud cible
					return current
				
				def append(self, data):
					"""Ajoute un élément à la fin de la liste."""
					new_node = Node(data)
					if self.is_empty():
						self.head = new_node
					else:
						last_node = self._navigate_to(self.size-1)
						last_node.next = new_node
					self.size += 1
				
				def prepend(self, data):
					"""Ajoute un élément au début de la liste."""
					new_node = Node(data)
					new_node.next = self.head
					self.head = new_node
					self.size += 1
				
				def insert_at(self, index, data):
					"""Insère un élément à une position donnée."""
					if index == 0:
						self.prepend(data)
					else:
						new_node = Node(data)
						node_before_insertion = self._navigate_to(index-1)
						new_node.next = node_before_insertion.next
						node_before_insertion.next = new_node
						self.size += 1
				
				def remove_at(self, index):
					"""Supprime l'élément à la position donnée."""
				# À compléter ... ☺️
				
				def get_at(self, index):
					target_node = self._navigate_to(index)
					return target_node.data
				
				def __len__(self):
					"""Retourne la taille de la liste."""
					return self.size
				
				def __str__(self):
					"""Retourne une représentation en string de la liste."""
					if self.is_empty():
						return "[]"
					result = []
					current = self.head
					while current:
						result.append(str(current.data))
						current = current.next
					return "[" + ", ".join(result) + "]"
		

1. Expliquer comment fonctionne la méthode _navigate_to. En quoi cela entraîne une complexité en O(n) ?

2. Compléter la méthode remove_at en vous inspirant de la méthode insert_at.

3. Quel peut être l’intérêt de cette implémentation par rapport à la gestion de la mémoire ?

On veut écrire un script permettant de simuler la gestion des files de clients aux caisses d’un supermarché.

Les règles sont les suivantes :

• Il y a toujours au moins une caisse ouverte.
• Il y a au plus trois caisses ouvertes en même temps. Chaque caisse a sa propre file d’attente.
• Si la caisse n a plus de 10 clients, la caisse n+1, si elle existe, ouvre. Les clients ne changent pas de file pour simplifier le problème.
• Les clients arrivant en caisse choisissent toujours la caisse ouvert avec la file la plus petite.
• Chaque client est traité par une caisse en 1 à 3 minutes.
• Si une caisse a une file de 2 clients ou moins et que la caisse précédente a moins de 6 clients, elle ne prend plus de nouveau client. Elle traite les clients en cours puis ferme quand elle n’en a plus. La caisse n°1 reste cependant toujours ouverte.
• Le flux de clients arrivant chaque minute n’est pas nécessairement un entier. S’il y a par exemple un flux de 3,2 on considère que 3 clients arrivent chaque minute, avec une probabilité de 20 % d’en avoir un supplémentaire.

1. Écrire une fonction prenant en paramètre le nombre de clients arrivant en caisse chaque minute et la durée de la simulation, en minutes. Cette simulation doit montrer, minute par minute, l’évolution des clients en attente, caisse par caisse.

2. Quel doit être le flux de client pour qu’une caisse puisse suffire indéfiniment ?

3. Le magasin peut-il faire face indéfiniment à un flux de 4 clients par minutes ? Si non, combien de temps peut-il gérer un tel afflux, si on considère que plus de 30 clients en attente est inacceptable ?

Libre à vous de vous aider de la trame de code ci-dessous.

			import random
			import time

			def meilleur_choix(caisses):
				"""renvoie la première caisse ouverte avec la file la plus courte"""
				# À compléter

			def traitement_clients(caisses):
				"""pour chaque caisse, si elle est occupée, décroît le temps d’attente de 1, sinon prend un nouveau client"""
				for caisse in caisses.values():
					if caisse["attente"] > 0:
						...
					elif len(caisse["file"]) > 0:
						caisse["attente"] = random.randint(0,2)
						...

			def evolution(caisses):
				"""gère les ouvertures et fermetures selon la taille des files"""
				for key, caisse in caisses.items():

					# si la caisse n a plus de 10 clients en attente, ouvrir la caisse suivante
					...
						
					# si la dernière caisse a plus de 10 clients, les caisses sont débordées !
					...
						
					# si la caisse a moins de 3 clients et la caisse précédente a moins de 6 clients
					# elle ferme. Elle traite les clients en cours mais n’en accepte plus de nouveau
					...

			def simulation_file_attente(duree_simulation = 60, flux_clients = 2.5):

				caisses = {
					1: {"file": [], "ouverte": True, "attente": 0},
					2: {"file": [], "ouverte": False, "attente": 0},
					3: {"file": [], "ouverte": False, "attente": 0}
				}

				temps = 0
				id_client = 1
				
				while temps < duree_simulation:
					
					# Nombre de clients arrivant durant cette minute
					nb_nouveaux_clients = int(flux_clients) + (1 if random.random() < flux_clients % 1 else 0)
					
					for _ in range(nb_nouveaux_clients):
						# caisse attirant le nouveau client
						...
						# ouverture ou fermeture de caisses
						...
						id_client += 1
						
					# ouverture et fermeture de caisses même si aucun nouveau client n’arrive	
					... 
					
					# Nombre de clients traités durant cette minutes
					traitement_clients(caisses)
					
					print(caisses)
					temps += 1
					time.sleep(0.15)  # Pour ralentir la simulation et la rendre lisible
		

				import random
				import time

				def meilleur_choix(caisses):
					"""renvoie la première caisse ouverte avec la file la plus courte"""
					min = 1000
					index = 0
					for i, c in caisses.items():
						if len(c["file"]) < min and c["ouverte"]:
							min = len(c["file"])
							index = i
					return caisses[index]

				def traitement_clients(caisses):
					"""pour chaque caisse, si elle est occupée, décroît le temps d’attente de 1, sinon prend un nouveau client"""
					for caisse in caisses.values():
						if caisse["attente"] > 0:
							caisse["attente"] -= 1
						elif len(caisse["file"]) > 0:
							caisse["attente"] = random.randint(0,2)
							caisse["file"].pop(0)

				def evolution(caisses):
					"""gère les ouvertures et fermetures selon la taille des files"""
					for key, caisse in caisses.items():

						# si la caisse n a plus de 10 clients en attente, ouvrir la caisse suivante
						if len(caisse["file"]) > 10 and caisses.get(key+1):
							caisses.get(key+1)["ouverte"] = True
							
						# si la dernière caisse a plus de 10 clients, les caisses sont débordées !
						elif len(caisse["file"]) > 10 and not caisses.get(key+1):
							print("caisses débordées ! 😣")
							
						# si la caisse a moins de 3 clients et la caisse précédente a moins de 6 clients
						# la caisse n’accepte plus de nouveau client
						elif len(caisse["file"]) < 3 and key != 1 and len(caisses.get(key-1)["file"]) < 6:
							caisse["ouverte"] = False

				def simulation_file_attente(duree_simulation = 60, flux_clients = 2.5):

					caisses = {
						1: {"file": [], "ouverte": True, "attente": 0},
						2: {"file": [], "ouverte": False, "attente": 0},
						3: {"file": [], "ouverte": False, "attente": 0}
					}

					temps = 0
					id_client = 1
					
					while temps < duree_simulation:
						
						# Nombre de clients arrivant durant cette minute
						if temps > 30 : flux_clients = 0
						nb_nouveaux_clients = int(flux_clients) + (1 if random.random() < flux_clients % 1 else 0)
						
						for _ in range(nb_nouveaux_clients):
							# caisse attirant le nouveau client
							meilleur_choix(caisses)["file"].append(id_client)
							# ouverture ou fermeture de caisses
							evolution(caisses)
							id_client += 1
							
						evolution(caisses)
						
						# Nombre de clients traités durant cette minutes
						traitement_clients(caisses)
						
						print(caisses)
						temps += 1
						time.sleep(0.15)  # Pour ralentir la simulation et la rendre lisible
					
				simulation_file_attente()
			

Objectif : Vérifier si une expression mathématique ou un code source a ses parenthèses, crochets et accolades correctement équilibrés.

Principe de l’algorithme : on passe à l’algorithme une chaîne de caractères. Celui-ci doit vérifier si la succession de parenthèse (), de crochets [] et d’accolades {} éventuellement présente est cohérente. C’est-à-dire que chaque signe ouvrant "(", "[" et "{" possède bien sa contrepartie fermante. Et bien sûr il ne peut pas y avoir de sections croisées.
Chaque fois qu’on trouve un signe ouvrant, on l’ajoute à une pile. Chaque fois qu’on trouve un signe fermant, on vérifie que le signe ouvrant équivalent est au sommet de la pile et on le dépile.

Exemples d’expressions

Proposez une implémentation de la fonction est_equilibree remplissant l’objectif demandé.

				def est_equilibre(expression):
					"""Vérifie si les parenthèses, crochets et accolades sont équilibrés"""
					pile = []
					correspondances = {')': '(', ']': '[', '}': '{'}
					
					for caractere in expression:
						if caractere in '([{':
							pile.append(caractere)
						elif caractere in ')]}':
							if not pile or pile.pop() != correspondances[caractere]:
								return False
					
					return len(pile) == 0