Épreuve pratique n°1

Pile/File, Diviser pour régner

1 heure

Exercice 1 (10 pts)

Une pile est une structure de données linéaire de type LIFO (Last In, First Out) : le dernier élément ajouté est le premier à être retiré.

On souhaite implémenter une classe Pile en Python à l'aide d'une liste sous-jacente stockée dans l'attribut contenu.

L'interface de la classe Pile doit proposer les quatre méthodes suivantes :

• __init__(self) : initialise une pile vide en créant l'attribut contenu (liste vide) ;
• est_vide(self) : renvoie True si la pile est vide, False sinon ;
• empiler(self, v) : ajoute la valeur v au sommet de la pile ;
• depiler(self) : retire et renvoie l'élément situé au sommet de la pile. Si la pile est vide au moment de dépiler, une assertion doit lever une erreur avec le message "Pile vide".

Écrire le code de la classe Pile.

Exemple d'utilisation dans la console :

	>>> p = Pile()
	>>> p.est_vide()
	True
	>>> p.empiler(12)
	>>> p.empiler(5)
	>>> p.empiler(8)
	>>> p.est_vide()
	False
	>>> p.depiler()
	8
	>>> p.depiler()
	5
	>>> p.depiler()
	12
	>>> p.est_vide()
	True
	>>> p.depiler()
	AssertionError: Pile vide

Exercice 2 (10 pts)

La recherche dichotomique applique le principe « diviser pour régner » pour chercher un élément dans un tableau trié en divisant à chaque étape la zone de recherche par deux.

On donne ci-dessous le squelette de la fonction récursive recherche_dichotomique(tab, x, debut, fin). Elle prend en paramètres un tableau d'entiers trié tab, la valeur cherchée x, ainsi que les indices bornant la zone de recherche debut et fin.

Elle doit renvoyer l'indice de x dans tab s'il est présent, ou None sinon.

Traduire les commentaires en code Python pour rendre la fonction opérationnelle :

def recherche_dichotomique(tab, x, debut, fin):
    """
    Recherche récursivement x dans tab entre les indices debut et fin.
    Renvoie l'indice de x ou None si x est absent.
    """
    # 1. Cas de base : la zone de recherche est vide (debut dépasse fin)
    # -> renvoyer None
    if ...:
        return ...

    # 2. Diviser : calculer l'indice du milieu de la zone
    milieu = ...

    # 3. Régner : comparer la valeur au milieu avec x
    if tab[milieu] == x:
        # Valeur trouvée au milieu -> renvoyer l'indice
        return ...
    elif ...:
        # La valeur cherchée est plus petite -> chercher dans la moitié gauche
        return recherche_dichotomique(...)
    else:
        # La valeur cherchée est plus grande -> chercher dans la moitié droite
        return recherche_dichotomique(...)

Exemples de tests :

>>> tab = [2, 5, 8, 12, 16, 23, 38, 42, 50]
>>> recherche_dichotomique(tab, 16, 0, len(tab) - 1)
4
>>> recherche_dichotomique(tab, 2, 0, len(tab) - 1)
0
>>> recherche_dichotomique(tab, 50, 0, len(tab) - 1)
8
>>> recherche_dichotomique(tab, 15, 0, len(tab) - 1)
None