NoteBook corrigé de l’activité SUDOKU (lien à venir…)
Exercice supplémentaire
Étant donné deux séquences, trouvez la longueur de la sous-séquence la plus longue présente dans les deux. Une sous-séquence est une séquence qui apparaît dans le même ordre relatif, mais pas nécessairement contiguë. Par exemple, « abc », « abg », « bdf », « aeg », « acefg », .. etc. sont des sous-séquences de « abcdefg ». Ecrire une fonction pour compter la plus longue sous-séquence.
Etudions d’abord l’algorithme de la fusion de 2 listes:
FUSIONNER (`liste_gauche`, `liste_droite`): * On parcourt les deux listes `gauche` et `droite` en même temps, Pour chaque paire d’éléments, on place le plus petit dans liste resultat. * S’il reste des éléments dans `gauche` ou dans `droite` on les place à la fin de liste resultat
Développement graphique:
Soit 2 listes à fusionner:
Liste gauche : [3, 1, 4, 7, 8] et la liste droite : [2, 5, 6]
implémenter sous pyzo la fonction FUSIONNE donc voici le début:
def fusionne(lst1, lst2):
"""
list1 est une liste
list2 est une liste
la fonction retourne une liste resultat fusion des 2 listes list1 et list2
Example
-------
>>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
# listes non ordonnées
[2, 3, 1, 4, 5, 6, 7, 8]
>>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
# listes ordonnées
[1, 2, 3, 4, 5, 6, 7, 8]
"""
Maintenant regardons l’algorithme de la fonction TRI FUSION
TRI FUSION (liste): • Si liste est de taille <= 1 on ne fait rien. • Sinon, On sépare liste en 2 parties gauche et droite, • On appelle Tri fusion sur gauche et sur droite • On fusionne gauche et droite dans liste
Développement graphique :
Soit la liste [2, 3, 1, 4, 5, 6, 7, 8] à trier par fusion
on sépare d’abord :
et on fusionne avec la fonction FUSIONNE décrite juste avant:
implémenter cette fonction
def fusionne(lst1, lst2):
"""
list1 est une liste
list2 est une liste
la fonction retourne une liste resultat fusion des 2 listes list1 et list2
Example
-------
>>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
# listes non ordonnées
[2, 3, 1, 4, 5, 6, 7, 8]
>>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
# listes ordonnées
[1, 2, 3, 4, 5, 6, 7, 8]
"""
def tri_fusion(lst):
'''lst est une liste non triées
Elle est coupé en 2 listes gauche et droite par le milieu (ou presque si taille impaire),
puis la fonction tri_fusion est rappelée pour chaque liste gauche et droite, jusqu'à n'obtenir des listes de taille 1.
en fin on applique la fonction fusionne les listes gauche et droite dans une liste que la fonction renvoie.
Exemple:
>>> tri_fusion([2, 3, 1, 4, 5, 6, 7, 8])
[1, 2, 3, 4, 5, 6, 7, 8]'''''
voici un programme pour créer des listes triées ou aléatoire pour faire des tests:
import random
def liste_triee(nb):#Création d'une liste trièe dans l'ordre croissant de nb valeur
nmax=nb
L=[]
for i in range(0,nmax):
L.append(i)
return L
def liste_aleatoire(nb):# fabrication d'une liste de nb valeurs aléatoires
nmax=nb
L=[]
for i in range(0,nmax):
L.append(random.randint(0,nmax))
return L
fonction chercher : (tableau, clé) —-> booléen 1. Pour un tableau de taille 1, il contient la clé si valeur est la clé 2. On sépare le tableau en deux parties sensiblement de même taille (gauche et droite) 3. Le tableau contient la clé si chercher(gauche, clé) ou chercher(droite, clé) est vrai.
Exemple tableau = [4, 10, 20, 5] clé = 10 A-t-on clé dans tableau ? Exemple clé = 10 [4, 10, 20, 5]
diviser [4, 10] [20, 5]
diviser [4] [10] [20] [5]
combiner Faux ou Vrai Faux ou Faux
combiner Vrai ou Faux
combiner Vrai
Implémenter cette fonction sous python.
Exercice 2: Calcul y puissance x
On souhaite calculer N=752. La méthode basique consiste à multiplier le nombre 7 par lui-même 52 fois… Ce qui n’est pas très rapide !
L’idée consiste donc à diviser le problème en 2 : on va calculer 726× 726, c’est-à-dire( 726)2. Là, il n’y a plus que 26 + 1 opérations (26 multiplications pour calculer 726, et une dernière pour faire le carré du résultat.
On recommence ensuite avec 726 : on le calcule en faisant (713)2.
N se calcule alors en 13+1+1 opérations au lieu de 52 initialement.
On ne s’arrête pas là, bien entendu : on continue tant que l’on peut utiliser ce principe :
N=752
=(726)2
=((713)2)2
=[[(76)2×7]2]2
=[[((73)2)2×7]2]2
=[[((72×7)2)2×7]2]2
Le principe est, vous l’avez peut-être remarqué, récursif.
Implémentation en Python du “diviser pour régner”
Nous allons écrire une fonction “puissance(x,n)” basée sur ce paradigme, où x et n sont deux entiers (positif pour n). Pour cela, nous allons prendre en compte que:
Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :
On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l’idée étant que les « petits problèmes » seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les « petits problèmes résolus » afin d’obtenir la solution du problème de départ.
Le paradigme « diviser pour régner » repose donc sur 3 étapes :
DIVISER : le problème d’origine est divisé en un certain nombre de sous-problèmes
RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d’origine)
COMBINER : les solutions des sous-problèmes sont combinées afin d’obtenir la solution du problème d’origine.
Les algorithmes basés sur le paradigme « diviser pour régner » sont très souvent des algorithmes récursifs.
Nous allons maintenant étudier un de ces algorithmes basés sur le principe diviser pour régner : le tri-fusion
Tri-fusion
Nous avons déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection. Nous allons maintenant étudier une nouvelle méthode de tri, le tri-fusion. Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie, le même tableau, mais trié.
À faire vous-même 1
Étudiez cet algorithme :
TRI FUSION (tableau):
• Si tableau est de taille <= 1 on ne fait rien.
• Sinon, On sépare tableau en 2 parties gauche et droite,
• On appelle Tri fusion sur gauche et sur droite
• On fusionne gauche et droite dans tableau
FUSIONNER (`tableau`, `gauche`, `droite`):
* On parcourt les deux tableaux `gauche` et `droite` en même temps,
Pour chaque paire d'éléments, on place le plus petit dans tableau.
* S'il reste des éléments dans `gauche` ou dans `droite` on les place à la fin
de tableau
Pour trier un tableau A, on fait l’appel initial TRI-FUSION(A, 1, A.longueur)
Rappel : Attention, en algorithmique, les indices des tableaux commencent à 1
Cet algorithme est un peu difficile à appréhender, on notera qu’il est composé de deux fonctions FUSIONNER et TRI-FUSION (fonction récursive). La fonction TRI-FUSION assure la phase « DIVISER » et la fonction FUSION assure les phases « RÉGNER » et « COMBINER ».
Voici un exemple d’application de cet algorithme sur le tableau A = [23, 12, 4, 56, 35, 32, 42, 57, 3] :
À faire vous-même 2
Étudiez attentivement le schéma ci-dessous afin de mieux comprendre le principe du tri-fusion (identifiez bien les phases « DIVISER » et « COMBINER »).
On remarque que dans le cas du tri-fusion, la phase « RÉGNER » se réduit à sa plus simple expression, en effet, à la fin de la phase « DIVISER », nous avons à trier des tableaux qui comportent un seul élément, ce qui est évidemment trivial.
À faire vous-même 3
Reprenez tout le raisonnement qui vient d’être fait sur le tableau T = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Vous n’hésiterez pas à faire un schéma et à expliquer la fusion de 2 tableaux triés.
Nous avons vu que le tri par insertion et tri par sélection ont tous les deux une complexité O(n2)
. Qu’en est-il pour le tri-fusion ?
Le calcul rigoureux de la complexité de cet algorithme sort du cadre de ce cours. Mais, en remarquant que la première phase (DIVISER) consiste à « couper » les tableaux en deux plusieurs fois de suite, intuitivement, on peut dire qu’un logarithme base 2 doit intervenir. La deuxième phase consiste à faire des comparaisons entre les premiers éléments de chaque tableau à fusionner, on peut donc supposer que pour un tableau de n éléments, on aura n comparaisons. En combinant ces 2 constations on peut donc dire que la complexité du tri-fusion est en O(n.log(n))
(encore une fois la « démonstration » proposée ici n’a rien de rigoureux).
La comparaison des courbes de la fonction n2 (en rouge) et n.log(n)
(en bleu) :
nous montre que l’algorithme de tri-fusion est plus « efficace » que l’algorithme de tri par insertion ou que l’algorithme de tri par sélection.
Utilisation du tri fusion: Contrairement au tri par sélection ou par insertion, le tri fusion est réellement utilisé en pratique. Il a de nombreux avantages : • complexité optimale (cela ne signifie pas qu’il est le plus rapide) • stable (voir plus bas) • facile à mettre en œuvre Cependant, il est possible d’améliorer la méthode : timsort, le tri natif en Python et Javascript utilise une combinaison du tri fusion et du tri par insertion.
Le but de ce projet est d’implémenter en Python les algorithmes sur les arbres binaires précédemment étudiés. Il sera donc sans doute nécessaire de reprendre ce qui a été vu sur la structure de données « arbre » et sur « les algorithmes sur les arbres binaires ».
Comme nous l’avons déjà dit, Python ne propose pas de structure de données permettant d’implémenter directement les arbres binaires. Il va donc être nécessaire de créer cette structure. Pour programmer ce type de structure, nous allons utiliser le paradigme objet (à voir si pas encore étudier paradigme objet)
Vous trouverez ci-dessous la classe « ArbreBinaire » qui va nous permettre d’implémenter des arbres binaires.
Étudiez attentivement la classe « ArbreBinaire » (méthodes et attributs). Vous pouvez, par exemple, vous interroger sur l’utilité de toutes les méthodes de cette classe.
Voici un exemple d’utilisation de cette classe pour construire un arbre binaire :
Soit l’arbre binaire suivant : Arbre 1
Voici le programme qui va permettre de construire cet arbre à l’aide de la classe « ArbreBinaire » :
class ArbreBinaire:
def __init__(self, valeur):
self.valeur = valeur
self.enfant_gauche = None
self.enfant_droit = None
def insert_gauche(self, valeur):
if self.enfant_gauche == None:
self.enfant_gauche = ArbreBinaire(valeur)
else:
new_node = ArbreBinaire(valeur)
new_node.enfant_gauche = self.enfant_gauche
self.enfant_gauche = new_node
def insert_droit(self, valeur):
if self.enfant_droit == None:
self.enfant_droit = ArbreBinaire(valeur)
else:
new_node = ArbreBinaire(valeur)
new_node.enfant_droit = self.enfant_droit
self.enfant_droit = new_node
def get_valeur(self):
return self.valeur
def get_gauche(self):
return self.enfant_gauche
def get_droit(self):
return self.enfant_droit
#######fin de la classe########
######début de la construction de l'arbre binaire###########
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')
b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')
f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')
c_node = b_node.get_gauche()
c_node.insert_droit('E')
g_node = f_node.get_gauche()
g_node.insert_gauche('I')
h_node = f_node.get_droit()
h_node.insert_droit('J')
######fin de la construction de l'arbre binaire###########
À faire vous-même 2
Étudiez attentivement le programme ci-dessus afin de comprendre le principe de « construction d’un arbre binaire »
Il est possible d’afficher un arbre binaire dans la console Python, pour cela, nous allons écrire une fonction « affiche ». Cette fonction renvoie une série de tuples de la forme (valeur,arbre_gauche, arbre_droite), comme « arbre_gauche » et « arbre_droite » seront eux-mêmes affichés sous forme de tuples, on aura donc un affichage qui ressemblera à : (valeur,(valeur_gauche,arbre_gauche_gauche,arbre_gauche_droite),(valeur_droite,arbre_droite_gauche,arbre_droite_droite)), mais comme « arbre_gauche_gauche » sera lui-même représenté par un tuple… Nous allons donc avoir des tuples qui contiendront des tuples qui eux-mêmes contiendront des tuples…
N.B : la fonction « affiche » n’a pas une importance fondamentale, elle sert uniquement à vérifier que les arbres programmés sont bien corrects.
À faire vous-même 4
Programmez à l’aide de la classe « ArbreBinaire », l’arbre binaire suivant :
Arbre 2
Vérifiez votre programme à l’aide de la fonction « affiche »
Vous allez maintenant pouvoir commencer à travailler sur l’implémentation des algorithmes sur les arbres binaires :
À faire vous-même 5
Programmez la fonction « hauteur » qui prend un arbre binaire T en paramètre et renvoie la hauteur de T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 6
Programmez la fonction « taille » qui prend un arbre binaire T en paramètre et renvoie la taille de T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 7
Programmez la fonction « parcours_infixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours infixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 8
Programmez la fonction « parcours_prefixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours préfixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 9
Programmez la fonction « parcours_suffixe » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours suffixe de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
À faire vous-même 10
Programmez la fonction « parcours_largeur » qui prend un arbre binaire T en paramètre et qui permet d’obtenir le parcours en largeur de l’arbre T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 1 »).
Nous allons maintenant travailler sur les arbres binaires de recherche.
À faire vous-même 11
Programmez, à l’aide de la classe « ArbreBinaire », l’arbre binaire de recherche ci-dessous : Arbre 3
Vérifiez votre réponse à l’aide de la fonction « affichage »
À faire vous-même 12
Afin de vérifier que l’arbre binaire « Arbre 3 » est bien un arbre binaire de recherche, utilisez la fonction « parcours_infixe » programmée dans le « À faire vous-même 7 ».
À faire vous-même 13
Programmez la fonction « arbre_recherche » qui prend un arbre binaire T et un entier k en paramètres et qui renvoie True si k appartient à T et False dans le cas contraire (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec k = 13 et k = 16.
À faire vous-même 14
Programmez la fonction « arbre_recherche_ite » (version itérative de la fonction « arbre_recherche ») qui prend un arbre binaire T et un entier k en paramètres et qui renvoie True si k appartient à T et False dans le cas contraire (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec k = 13 et k = 16.
À faire vous-même 15
Programmez la fonction « arbre_insertion » qui prend T (un arbre binaire) et y (un objet de type « ArbreBinaire ») en paramètres et qui insert y dans T (algorithme correspondant, voir ici)
Testez votre fonction en utilisant l’arbre vu plus haut (schéma « Arbre 3 ») avec y.valeur = 16.
Ces exercices vous permettront de vous entrainer en vue de l’évaluation sur la programmation.
Exercice 1
On dispose de la formule suivante pour convertir les degrés Fahrenheit en degrés Celsius : C = 0,55556 × (F – 32)
où F est une température en degrés Fahrenheit et C la température correspondante en degrés Celsius. 1. Ecrire un programme qui convertit en degrés Celsius une température rentrée au clavier en degrés Fahrenheit. 2. Même question pour la conversion inverse.
Exercice 2
Écrire un programme qui affiche un triangle rempli d’étoiles (*) sur un nombre de lignes donné passé en paramètre, exemple :
• 1ère version : à l’aide de deux boucles for, en imprimant les * une par une.
On remarquera que, par défaut dans l’instruction print() , figure end = ‘\n’, qui fait passer à la ligne.
print(…, end =’’) ne fera donc pas passer à la ligne.
• 2ème version : avec une seul boucle for, et une chaîne de caractères où vous accumulerez des étoiles (pour ceux qui vont un peu plus vite, print(« machin » end= ‘’) évite de passer à la ligne.
Exercice 3
Programmation d’un petit jeu de devinette. L’ordinateur choisit au hasard un nombre compris entre 1 et 100.
Le but du jeu est de le deviner en un nombre d’essai minimal. À chaque tentative, l’ordinateur, indique « gagné », « trop petit » ou « trop grand ». L’utilisateur dispose d’un nombre d’essais limités.
Écrire l’algorithme en « langage naturel ». Programmer le jeu, et le tester.
Remarque : on utilisera la bibliothèque random. Pour cela, on écrit « import random » en début de programme. nombre = random.randint(a, b) renverra un nombre aléatoire tel que a ≤ Nombre ≤ b
Exercice 4
Convertir une note scolaire N quelconque, entrée par l’utilisateur sous forme de points (par exemple 27 sur 85), en une note standardisée suivant le code ci-dessous :
Note N
Appréciation
N >= 80 %
A
80 % > N >= 60 %
B
60 % > N >= 50 %
C
50 % > N >= 40 %
D
N < 40 %
E
Exercice 5
Ecrire un programme qui affiche les carrés des entiers de 1 à 7 .
Exercice 6
Ecrire un programme qui affiche n fois la suite de symboles suivante : A #Si n=1 AA #si n=2 AAA etc…sans utiliser le * comme par exemple print(3* »A »).
n est donné par l’utilisateur.
Exercice 7
Ecrire un programme qui demande un prénom. Si ce prénom est Paul, le programme affiche « enfin c’est toi », sinon le programme redemande un nouveau prénom car ce n’est pas la personne qu’il attend (un genre de mot de passe non ?).
Exercice 8
Ecrire un programme qui additionne tous les nombres que vous entrez (tour à tour) et qui s’arrête lorsque la somme dépasse 100.
On considère deux jeux de 54 cartes à jouer. Pour les mélanger, on créer un troisième paquet en empilant les cartes aléatoirement piochées dans un des deux jeux. Quand l’un des deux jeux est vide, on empile le jeu restant sur le troisième paquet. On modélisera les deux jeux de 54 cartes par deux listes contenant respectivement les entiers de 101 à 154 et de 201 à 254. Écrire une fonction python qui réalise le mélange.
Exercice 2 (Bataille, pile)
On considère un jeu de 52 cartes à jouer (pas de joker) que l’on modélise par une liste contenant quatre fois les entiers de 1 à 13. La valeur d’une carte est égale à son numéro. On distribue ensuite aléatoirement 13 cartes à quatre joueurs qui les empilent consciencieusement devant eux. A chaque tour de jeu, les quatre joueurs posent la carte au sommet de leur pile au milieu. Celui qui a la carte la plus forte remporte le pli, c’est à dire les quatre cartes du tour. S’il y a égalité, on tire au sort le joueur qui gagne rafle le pli. Le joueur qui a la fin a le plus de points gagne la partie. Écrire un programme Python qui simule ce jeu.
Exercice 3 (La bonne syntaxe,pile)
L’analyse syntaxique est une phase indispensable de la compilation des programmes. Les piles sont particulièrement bien adaptées à ce genre de traitements. On va se limiter à la reconnaissance des expressions bien parenthésés. Nous devons écrire un programme qui :—accepte les expressions comme (a), (a b)((c d e)) ou (((a)(b c d))(e)) où a, b, etc. sont des expressions quelconques sans parenthèses—rejette les expressions comme a )(, (a b)((c) ou (((a b)(c d e f))))On remarque d’abord que les expressions a, b, c .. qui apparaissent n’ont aucune importance pour savoir si l’expression est bien parenthésée. On va lire l’expression sous la forme d’une chaine de caractères et utiliser une pile. Lors de la lecture dela chaine, on empile les ”(”. Pour les ”)”, on vérifie d’abord si le sommet de la pile est ”(”, dans ce cas, on dépile. Sinon, on empile le ”(”. A la fin de l’algorithme, si l’expression est bien parenthésée, la pile est vide.Écrire un algorithme utilisant une pile et ses primitives.
Exercice 4 (Évaluation d’une expression arithmétique, pile)
Nous allons voir ici une utilisation des piles pour évaluer des expressions arithmétiques.Par exemple, on souhaite évaluer(3×(5+2×3)+4)×2On se contentera d’évaluer des expressions correctement écrites avec seulement des nombres à un seul chiffre et uniquement des sommes et des produits.
1. On commence par écrire l’expression en notation ”postfixé” ou inverse polonaise Dans cette notation, on écrit les opérations après les nombres plutôt qu’avant.Par exemple,2+3s’écrira2,3,+
Ecrire l’expression(3×(5+2×3)+4)×2 en postfixé.
2. En lisant de gauche à droite l’expression postfixé, on construit une Pile suivant les règles suivantes :—Si on lit un nombre, on l’empile—Si on lit une opération, on dépile deux nombres et on effectue l’opération entre ces deux nombres et on l’empile.
3. Ecrire en pseudo code, une séquence qui permet d’évaluer l’expression.
4. Implémenter l’algorithme en python.
Exercice 5 (file)
Dans un supermarché il y a 5 caisses et une file d’attente commune. Dès qu’une caisse est libre, le client en tête de file y est envoyé. Le temps de passage en caisse est aléatoirement compris entre 3 et 10 minutes. Il y a dix clients dans la file d’attente.
1. Réaliser une simulation de leurs passages en caisses et afficher en combien de minutes tous les clients sont passés.
2. Refaire quelques essais avec plus de clients.
Pour la file d’attente , vous utiliserez une file avec l’objet deque sous python, voir description objet deque ici.
Par exemple voici la liste d’attente:
from collections import deque #import container deque
file_attente=['1','2','3','4','5','6','7','8','9','10'] #la liste d'attente commune avec 10 clients
d = deque(file_attente) #création file client
Retire et renvoie un élément de l’extrémité droite de la deque. S’il n’y a aucun élément, lève une exception IndexError.
popleft()
Retire et renvoie un élément de l’extrémité gauche de la deque. S’il n’y a aucun élément, lève une exception IndexError.
Pour la liste des caisses, vous utiliserez une liste [0,0,0,0,0], premier élément temps caisse 1, ici à 0, puis temps caisse 2 ou un dictionnaire {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, clé 1 = caisse 1 avec sa valeur = temps ici à 0.
Exercice 6
Un poste de contrôle est alimenté en pièces toutes les 7 minutes. Ces pièces sont de quatre types qui nécessitent respectivement
4, 6, 8 et 9 minutes pour être contrôlés. Les fréquences des quatre types sont identiques.
1. A l’aide d’une file, simuler le fonctionnement du poste de contrôle pendant 1 heure, puis 80 heures.
2. Calculer le nombre de pièces en attente de contrôle
3. Déterminer la durée de séjour des pièces dans le poste de contrôle. Afficher celle de la dernière
4. Le contrôleur fait une pause de 15 minutes toutes les 4 heures. Déterminer le nombre d’heures effectives de travail.
Exercice 7
Un restaurant de 50 tables à 2 couverts ouvre ses portes pendant 4 heures chaque soir. L’intervalle de temps entre l’arrivée de deux groupes de clients est d’environ 2 minutes. Les groupes sont constitués aléatoirement de 2 à 6 convives avec des fréquences identiques.
Les tables peuvent être rassemblées pour les groupes de plus de 2 personnes. Lorsqu’un groupe arrive, il attend que des tables en nombre suffisant soient libres.
Une fois assis, le groupe reste pendant une durée aléatoirement comprise entre 60 et 120 minutes.
Simuler le fonctionnement du restaurant pendant une soirée.
Afficher le nombre de clients servis lors d’un service et nombre moyen de clients par table.
Exercice 2 du sujet 10 de l’épreuve pratique de 2021
Faire l’exercice 2 du Sujet n°10 de l’épreuve pratique de 2021
Avant d’entrer dans le vif du sujet (les algorithmes), nous allons un peu approfondir la notion d’arbre binaire :
À chaque nœud d’un arbre binaire, on associe une clé (« valeur » associée au nœud on peut aussi utiliser le terme « valeur » à la place de clé), un « sous-arbre gauche » et un « sous-arbre droit »
Soit l’arbre binaire suivant :
si on prend le nœud ayant pour clé A (le nœud racine de l’arbre) on a :
le sous-arbre gauche est composé du nœud ayant pour clé B, du nœud ayant pour clé C, du nœud ayant pour clé D et du nœud ayant pour clé E
le sous-arbre droit est composé du nœud ayant pour clé F, du nœud ayant pour clé G, du nœud ayant pour clé H, du nœud ayant pour clé I et du nœud ayant pour clé J
si on prend le noeud ayant pour clé B on a :
le sous-arbre gauche est composé du nœud ayant pour clé C et du nœud ayant pour clé E
le sous-arbre droit est uniquement composé du nœud ayant pour clé D
Un arbre (ou un sous-arbre) vide est noté NIL (NIL est une abréviation du latin nihil qui veut dire « rien »)
si on prend le nœud ayant pour clé G on a :
le sous-arbre gauche est uniquement composé du nœud ayant pour clé I
le sous-arbre droit est vide (NIL)
Il faut bien avoir en tête qu’un sous-arbre (droite ou gauche) est un arbre (même s’il contient un seul nœud ou pas de nœud de tout (NIL)).
Soit un arbre T : T.racine correspond au nœud racine de l’arbre T
Soit un nœud x :
x.gauche correspond au sous-arbre gauche du nœud x
x.droit correspond au sous-arbre droit du nœud x
x.clé correspond à la clé du nœud x
Il faut noter que si le nœud x est une feuille, x.gauche et x.droite sont des arbres vides (NIL)
Calculer la hauteur d’un arbre
Nous allons commencer à travailler sur les algorithmes en nous intéressant à l’algorithme qui permet de calculer la hauteur d’un arbre :
À faire vous-même 1
Étudiez cet algorithme :
VARIABLE
T : arbre
x : noeud
DEBUT
HAUTEUR(T) :
si T ≠ NIL :
x ← T.racine
renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
sinon :
renvoyer 0
fin si
FIN
N.B. la fonction max renvoie la plus grande valeur des 2 valeurs passées en paramètre (exemple : max(5,6) renvoie 6)
Cet algorithme est loin d’être simple, n’hésitez pas à écrire votre raisonnement sur une feuille de brouillon. Vous pourrez par exemple essayer d’appliquer cet algorithme sur l’arbre binaire ci-dessous. N’hésitez pas à poser des questions si nécessaire.
Si vraiment vous avez des difficultés à comprendre le fonctionnement de l’algorithme sur l’arbre ci-dessus, vous trouverez ici un petit calcul qui pourrait vous aider.
Comme vous l’avez sans doute remarqué, nous avons dans l’algorithme ci-dessus une fonction récursive. Vous aurez l’occasion de constater que c’est souvent le cas dans les algorithmes qui travaillent sur des structures de données telles que les arbres.
Calculer la taille d’un arbre
Nous allons maintenant étudier un algorithme qui permet de calculer le nombre de nœuds présents dans un arbre.
À faire vous-même 2
Étudiez cet algorithme :
VARIABLE
T : arbre
x : noeud
DEBUT
TAILLE(T) :
si T ≠ NIL :
x ← T.racine
renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
sinon :
renvoyer 0
fin si
FIN
Cet algorithme ressemble beaucoup à l’algorithme étudié au « À faire vous-même 1 », son étude ne devrait donc pas vous poser de problème.
Appliquez cet algorithme à l’exemple suivant :
Il existe plusieurs façons de parcourir un arbre (parcourir un arbre = passer par tous les nœuds), nous allons en étudier quelques-unes :
Parcourir un arbre dans l’ordre infixe
À faire vous-même 3
Étudiez cet algorithme :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-INFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-INFIXE(x.gauche)
affiche x.clé
PARCOURS-INFIXE(x.droit)
fin si
FIN
Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : C, E, B, D, A, I, G, F, H, J
Parcourir un arbre dans l’ordre préfixe
À faire vous-même 4
Étudiez cet algorithme :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-PREFIXE(T) :
si T ≠ NIL :
x ← T.racine
affiche x.clé
PARCOURS-PREFIXE(x.gauche)
PARCOURS-PREFIXE(x.droit)
fin si
FIN
Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : A, B, C, E, D, F, G, I, H, J
Parcourir un arbre dans l’ordre suffixe
À faire vous-même 5
Étudiez cet algorithme :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-SUFFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-SUFFIXE(x.gauche)
PARCOURS-SUFFIXE(x.droit)
affiche x.clé
fin si
FIN
Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : E, C, D, B, I, G, J, H, F, A
Le choix du parcours infixe, préfixe ou suffixe dépend du problème à traiter, on pourra retenir pour les parcours préfixe et suffixe (le cas du parcours infixe sera traité un peu plus loin) que :
dans le cas du parcours préfixe, un nœud est affiché avant d’aller visiter ces enfants
dans le cas du parcours suffixe, on affiche chaque nœud après avoir affiché chacun de ses fils
Parcourir un arbre en largeur d’abord
À faire vous-même 6
Étudiez cet algorithme :
VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)
DEBUT
PARCOURS-LARGEUR(T) :
enfiler(T, f) //on place la racine dans la file
tant que f non vide :
x ← defiler(f)
affiche x.clé
si x.gauche ≠ NIL :
Tg ← x.gauche
enfiler(Tg, f)
fin si
si x.droit ≠ NIL :
Td ← x.droite
enfiler(Td, f)
fin si
fin tant que
FIN
Vérifiez qu’en appliquant l’algorithme ci-dessus, l’arbre ci-dessous est bien parcouru dans l’ordre suivant : A, B, F, C, D, G, H, E, I, J
Selon vous, pourquoi parle-t-on de parcours en largeur ?
Il est important de bien noter l’utilisation d’une file (FIFO) pour cet algorithme de parcours en largeur. Vous noterez aussi que cet algorithme n’utilise pas de fonction récursive.
Arbre binaire de recherche
Un arbre binaire de recherche est un cas particulier d’arbre binaire. Pour avoir un arbre binaire de recherche :
il faut avoir un arbre binaire !
il faut que les clés de nœuds composant l’arbre soient ordonnables (on doit pouvoir classer les nœuds, par exemple, de la plus petite clé à la plus grande)
soit x un noeud d’un arbre binaire de recherche. Si y est un nœud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé. Si y est un nœud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé
À faire vous-même 7
Vérifiez que l’arbre ci-dessus est bien un arbre binaire de recherche.
À faire vous-même 8
Appliquez l’algorithme de parcours infixe sur l’arbre ci-dessous :
Que remarquez-vous ?
Recherche d’une clé dans un arbre binaire de recherche
Nous allons maintenant étudier un algorithme permettant de rechercher une clé de valeur k dans un arbre binaire de recherche. Si k est bien présent dans l’arbre binaire de recherche, l’algorithme renvoie vrai, dans le cas contraire, il renvoie faux.
À faire vous-même 9
Étudiez l’algorithme suivant:
VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE(T,k) :
si T == NIL :
renvoyer faux
fin si
x ← T.racine
si k == x.clé :
renvoyer vrai
fin si
si k < x.clé :
ARBRE-RECHERCHE(x.gauche,k)
sinon :
ARBRE-RECHERCHE(x.droit,k)
fin si
FIN
À faire vous-même 10
Appliquez l’algorithme de recherche d’une clé dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra k = 13.
À faire vous-même 11
Appliquez l’algorithme de recherche d’une clé dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra k = 16.
Cet algorithme de recherche d’une clé dans un arbre binaire de recherche ressemble beaucoup à la recherche dichotomique vue en première. C’est principalement pour cette raison qu’en général, la complexité en temps dans le pire des cas de l’algorithme de recherche d’une clé dans un arbre binaire de recherche est O(log2(n))
À noter qu’il existe une version dite « itérative » (qui n’est pas récursive) de cet algorithme de recherche :
À faire vous-même 12
Étudiez l’algorithme suivant:
VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE_ITE(T,k) :
x ← T.racine
tant que T ≠ NIL et k ≠ x.clé :
x ← T.racine
si k < x.clé :
T ← x.gauche
sinon :
T ← x.droit
fin si
fin tant que
si k == x.clé :
renvoyer vrai
sinon :
renvoyer faux
fin si
FIN
Insertion d’une clé dans un arbre binaire de recherche
Il est tout à fait possible d’insérer un nœud y dans un arbre binaire de recherche (non vide) :
À faire vous-même 13
Étudiez l’algorithme suivant:
VARIABLE
T : arbre
x : noeud
y : noeud
DEBUT
ARBRE-INSERTION(T,y) :
x ← T.racine
tant que T ≠ NIL :
x ← T.racine
si y.clé < x.clé :
T ← x.gauche
sinon :
T ← x.droit
fin si
fin tant que
si y.clé < x.clé :
insérer y à gauche de x
sinon :
insérer y à droite de x
fin si
FIN
À faire vous-même 14
Appliquez l’algorithme d’insertion d’un nœud y dans un arbre binaire de recherche sur l’arbre ci-dessous. On prendra y.clé = 16.
Arbre 1
Arbre 3
