É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.

Les tests suivants doivent être réussis, c’est-à-dire que vous ne devez pas avoir d’erreur en exécutant le code ci-dessous :


	p = Pile()
	assert p.est_vide(), "est_vide ne fonctionne pas"

	p.empiler(12)
	p.empiler(5)
	p.empiler(8)
	assert p.contenu == [12, 5, 8], "empiler ne fonctionne pas"
	assert not p.est_vide(), "est_vide ne fonctionne pas"
	assert p.depiler() == 8, "dépiler ne fonctionne pas"
	assert p.depiler() == 5, "dépiler ne fonctionne pas"
	assert p.depiler() == 12, "dépiler ne fonctionne pas"
	assert p.est_vide(), "est_vide ne fonctionne pas"

	try: p.depiler()
	except AssertionError: print("Assertion sur pile vide OK")
	finally: print("Tous les tests OK")

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(...)

Les tests suivants doivent être réussis, c’est-à-dire que vous ne devez pas avoir d’erreur en exécutant le code ci-dessous :


	tab = [2, 5, 8, 12, 16, 23, 38, 42, 50]
	assert recherche_dichotomique(tab, 16, 0, len(tab) - 1) == 4
	assert recherche_dichotomique(tab, 2, 0, len(tab) - 1) == 0
	assert recherche_dichotomique(tab, 50, 0, len(tab) - 1) == 8
	assert recherche_dichotomique(tab, 15, 0, len(tab) - 1) is None
	print("Tous les tests OK")

Correction

Exercice 1

Le code ci-dessous est une implémentation possible.


		class Pile:
			def __init__(self):
				self.contenu = []

			def est_vide(self):
				return len(self.contenu) == 0

			def empiler(self, v):
				self.contenu.append(v)

			def depiler(self):
				assert not self.est_vide(), "Pile vide"
				return self.contenu.pop()

Si votre code est différent mais qu’il passe tous les tests, c’est 100 % correct.

Exercice 2


		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 debut > fin : return None

			# 2. Diviser : calculer l'indice du milieu de la zone
			milieu = (debut + fin) // 2

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