Listes et algorithmes récursifs

Présentation¶

Stocker les données est un problème fondamental en informatique. Étant donné une collection finie de données \(a\), \(b\), \(c\), \(\ldots\), on décide de les stocker de manière séquentielle : le premier élément de la liste est \(a\), le second \(b\), etc. On utilise pour cela la structure de liste.

On peut donner une définition récursive à la structure de liste. En effet, une liste c'est : soit la liste vide ; soit un élément (la tête) suivit d'une liste (la queue).

Dans ce TP, on n'utilisera pas le type list définit par python. On définit le type Liste dans un fichier annexe et on utilisera uniquement les fonctions suivantes pour manipuler les objets de type Liste. Aucune des fonctions de cette interface ne modifient les listes auxquelles elles s'appliquent : les listes sont non mutables ici.

Fonction	Description
`creer_vide()`	Renvoie une liste vide
`est_vide(l)`	Renvoie `True` si et seulement si la liste est vide
`tete(l)`	Renvoie le premier élément de la liste \(l\) (l'élément dit de tête)
`queue(l)`	Renvoie la liste constituée de tous les éléments de \(l\) à l'exception du premier
`ajoute(l, e)`	Renvoie la liste constituée de l'élément \(e\), suivi des éléments de \(l\)
`affiche(l)`	Affiche la liste des éléments de \(l\) sur la sortie standard, séparés par le caractère `-`.
	La liste vide est représentée par `x`.

On suppose instanciée une variable l de type Liste représentant la liste \(l = (1, 8, 5)\).

Que renvoie est_vide(l) ?
Que renvoie tete(l) ?
Que renvoie queue(l) ? Quelle est le type de queue(l) ?
Que renvoie ajoute(l, 93) ?
Que fait l'instruction affiche(l) ?

Interface¶

Exécuter le bloc ci-dessous pour charger l'interface du type Liste.

###

#--- HDR ---#bksl-nlclass Liste:bksl-nl def py-undpy-undinitpy-undpy-und(self, c, n):bksl-nl assert isinstance(c, int), f"Les éléments d'une Liste sont de type int"bksl-nl assert isinstance(n, Liste) or n is None, f"La queue d'une Liste doit être une Liste"bksl-nl self.c = cbksl-nl self.n = nbksl-nlbksl-nldef creerpy-undvide() -> Liste: return Nonebksl-nldef estpy-undvide(l: Liste) -> bool: return l is Nonebksl-nldef ajoute(l: Liste, e: int) -> Liste: return Liste(e, l)bksl-nldef tete(l: Liste) -> int: return l.cbksl-nldef queue(l: Liste) -> Liste: return l.nbksl-nldef affiche(l: Liste) -> None: print("x") if estpy-undvide(l) else (print(tete(l), end = " - "), affiche(queue(l)))bksl-nldef element(l: Liste, i: int) -> int: return tete(l) if i == 0 else element(queue(l), i - 1)bksl-nl#--- HDR ---#bksl-nlbksl-nl# Exécuter ce bloc AVANT de traiter les exercices.bksl-nl# Charge les fonctions suivantes :bksl-nl# creerpy-undvide : () -> Listebksl-nl# estpy-undvide : Liste -> boolbksl-nl# ajoute : Liste, int -> Listebksl-nl# tete : Liste -> intbksl-nl# queue : Liste -> Listebksl-nl# affiche : Liste -> NoneTypebksl-nlbksl-nll = creerpy-undvide()bksl-nlaffiche(l)bksl-nll = ajoute(l, 0)bksl-nlaffiche(l)bksl-nll = ajoute(l, 1)bksl-nlajoute(l, 2)bksl-nlaffiche(l)bksl-nlbksl-nl

D'après l'affichage, à quoi voit-on que la structure de liste proposée est non mutable ?

Premier exemple¶

Écrire les instructions python permettant d'instancier les variables l1, l2, l3, et l4, de type Liste représentant les listes :

\(l_1 = ()\)
\(l_2 = (-1)\)
\(l_3 = (5, 6, 9, -1)\)
\(l_4 = (-5, 9, 4, 9, -5, 9)\).

Vous utiliserez pour cela uniquement les fonctions creer_vide, ajoute.

###

def testpy-undpremierpy-undexemple():bksl-nl """ Tests pour la fonction premierpy-undexemple """bksl-nl print("Tests de premierpy-undexemple passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import premierpy-undexemplebksl-nl# testpy-undpremierpy-undexemple()bksl-nlbksl-nl 5/5

# l1 = creerpy-undvide()bksl-nl# ...bksl-nlbksl-nl

Exercices¶

Vous n'avez pas le droit d'utiliser de boucle for, ou de boucle while.

Liste singleton¶

Écrire une fonction est_singleton qui prend en argument une liste l et qui renvoie True si la liste est constituée d'un seul élément, False dans tous les autres cas.

###

def testpy-undestpy-undsingleton():bksl-nl """ Tests pour la fonction estpy-undsingleton """bksl-nl print("Tests de estpy-undsingleton passés avec succès.")bksl-nl assert estpy-undsingleton(creerpy-undvide()) == Falsebksl-nl assert estpy-undsingleton(ajoute(creerpy-undvide(), 3)) == Truebksl-nl assert estpy-undsingleton(ajoute(ajoute(creerpy-undvide(), 3), 2)) == Falsebksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undsingletonbksl-nltestpy-undestpy-undsingleton()bksl-nlbksl-nl 5/5

def estpy-undsingleton(l):bksl-nl """ Liste -> boolbksl-nl Détermine si la liste est constituée d'un seul élément. """bksl-nl passbksl-nlbksl-nl

Création de liste I¶

Écrire une fonction singleton qui prend en argument un entier n et qui renvoie la liste ayant pour seul élément le nombre n.

###

def testpy-undsingleton():bksl-nl """ Tests pour la fonction singleton """bksl-nl print("Tests de singleton passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import singletonbksl-nl# testpy-undsingleton()bksl-nlbksl-nl 5/5

def singleton(n):bksl-nl """ int -> Listebksl-nl Renvoie la liste (n) """bksl-nl passbksl-nlbksl-nl

Création de liste II¶

On souhaite écrire une fonction récursive nombres qui prend en argument un entier n supérieur à 1 et qui renvoie la liste des entiers de n (inclu) à 1 (inclu) dans l'ordre décroissant.

Pour quelle valeur du paramètre n parle-t-on du cas de base dans ce contexte ? Que doit renvoyer l'instruction nombre(n) dans le cas de base ?
Dans le cas général, lorsque le paramètre n est strictement supérieur à 1 :
1. Quelle instruction doit-on écrire pour affecter à la variable inter le résultat de l'appel récursif ?
2. Quelle liste la variable inter représente-t-elle ?
En déduire le code de la fonction nombres.

###

def testpy-undnombres():bksl-nl """ Tests pour la fonction nombres """bksl-nl print("Tests de nombres passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nombresbksl-nl# testpy-undnombres()bksl-nlbksl-nl 5/5

def nombres(n):bksl-nl """ int -> Listebksl-nl Renvoie la liste (n, n-1, n-2, ..., 3, 2, 1) """bksl-nl passbksl-nlbksl-nl

Création de liste III¶

On se propose dans cet exercice d'écrire une fonction nombresII qui prend en argument un entier n supérieur à 1 et qui renvoie la liste des entiers de 1 (inclu) à n (inclu) dans l'ordre croissant.

Écrire une fonction récursive nombresII_aux qui étant donné deux entiers n et i, renvoie la liste constituée des entiers de i (inclu) à n (inclu) dans l'ordre croissant.

On donne les indications suivantes :
- le cas de base de cette fonction est lorsque n et i sont égaux.
- l'appel récursif est nombresII_aux(n, i + 1)
- En déduire une fonction nombresII (celle-ci n'est pas récursive) qui renvoie la liste dans l'ordre croissant des entiers de 1 à n. Vous appellerez pour cela la fonction nombresII_aux avec des arguments bien choisis.

###

def testpy-undnombresII():bksl-nl """ Tests pour la fonction nombresII """bksl-nl print("Tests de nombresII passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nombresIIbksl-nl# testpy-undnombresII()bksl-nlbksl-nl 5/5

def nombresIIpy-undaux(n, i):bksl-nl """ int, int -> Listebksl-nl Renvoie la liste de nombres (i, i + 1, ..., n-1, n) """bksl-nl passbksl-nlbksl-nldef nombresII(n):bksl-nl """ int, int -> Listebksl-nl Renvoie la liste de nombres (1, 2, ..., n-1, n) """bksl-nl passbksl-nlbksl-nl

Longueur d'une liste¶

On définit la longueur d'une liste comme étant le nombre d'éléments constituant cette liste. Par exemple, si \(l = (0, 1, 5)\), la longueur de \(l\) est 3. Par convention, la longueur de la liste vide est 0.

Écrire une fonction python récursive longueur qui étant donné une liste, en renvoie la longueur.

Pour quelle valeur du paramètre l parle-t-on du cas de base dans ce contexte ? Que doit renvoyer l'instruction longueur(l) dans ce cas ?
1. Dans le cas général, que renvoie l'appel récursif longueur(queue(l)) ?
2. En déduire le code de la fonction longueur.

###

def testpy-undlongueur():bksl-nl """ Tests pour la fonction longueur """bksl-nl print("Tests de longueur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import longueurbksl-nl# testpy-undlongueur()bksl-nlbksl-nl 5/5

def longueur(l):bksl-nl """ Liste -> intbksl-nl Renvoie la longueur de la liste l """bksl-nl passbksl-nlbksl-nl

Somme des éléments d'une liste¶

Écrire une fonction python récursive somme qui étant donnée une liste l d'entiers non vide en renvoie la somme.

###

def testpy-undsomme():bksl-nl """ Tests pour la fonction somme """bksl-nl print("Tests de somme passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import sommebksl-nl# testpy-undsomme()bksl-nlbksl-nl 5/5

def somme(l):bksl-nl """ Liste -> intbksl-nl Calcule la somme des éléments de la liste l """bksl-nl passbksl-nlbksl-nl

Appartenance à une liste¶

Écrire une fonction python récursive appartient qui étant donné une liste l et un élément e, renvoie True si et seulement si l'élément e est un des éléments de la liste l.

Indication. On utilisera l'appel récursif appartient(queue(l), e).

###

def testpy-undappartient():bksl-nl """ Tests pour la fonction appartient """bksl-nl print("Tests de appartient passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import appartientbksl-nl# testpy-undappartient()bksl-nlbksl-nl 5/5

def appartient(l, e):bksl-nl """ Liste, int -> boolbksl-nl Détermine si l'élément e fait partie de la liste l """bksl-nl passbksl-nlbksl-nl

Nombre d'occurrences¶

Écrire une fonction python récursive nombre_occurrences qui étant donné une liste l et un élément e détermine le nombre d'occurrences de l'élément e dans la liste l.

###

def testpy-undnombrepy-undoccurrences():bksl-nl """ Tests pour la fonction nombrepy-undoccurrences """bksl-nl print("Tests de nombrepy-undoccurrences passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nombrepy-undoccurrencesbksl-nl# testpy-undnombrepy-undoccurrences()bksl-nlbksl-nl 5/5

def nombrepy-undoccurrences(l, e):bksl-nl """ Liste, int -> intbksl-nl Compte le nombre d'occurrences de e dans l """bksl-nl passbksl-nlbksl-nl

Maximum des éléments d'une liste¶

On souhaite écrire une fonction python récursive maximum qui étant donnée une liste l d'entiers non vide en renvoie le plus grand.

Écrire une fonction maximum2 qui étant donné deux entiers a et b renvoie le plus grand entier parmi a et b.
1. Pour quelle(s) valeur(s) du paramètre l parle-t-on du cas de base dans ce contexte ? Que doit renvoyer maximum(l) dans ce cas ?
2. Sans justifier votre réponse, compléter le tableau ci-dessous :
  
  Liste l maximum(queue(l)) maximum(l)
  
  \((3, 5, 6, 1, 4)\) \(6\)
  
  \((8, 5, 6, 1, 4)\)
  
  \((9, 3, 2, 12, 4, 1)\)
  
  \((1, 2, 3, 4, 5, 6, 7, 8)\)
En déduire le code d'une fonction python récursive maximum qui renvoie le plus grand élément de la liste l.

###

def testpy-undmaximum():bksl-nl """ Tests pour la fonction maximum """bksl-nl print("Tests de maximum passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import maximumbksl-nl# testpy-undmaximum()bksl-nlbksl-nl 5/5

def maximum2(a, b):bksl-nl """ int, int -> intbksl-nl Calcule l'élément maximum parmis a et bbksl-nl """bksl-nl passbksl-nlbksl-nldef maximum(l):bksl-nl """ Liste -> intbksl-nl Renvoie le plus grand élément de l """bksl-nl passbksl-nlbksl-nl

Pour aller plus loin¶

Suppression d'un élément¶

Écrire une fonction supprime qui prend en argument une liste l et un entier e, et renvoie la liste des éléments de l dans laquelle la première occurrence de e a été supprimée. On suppose que l'élément e appartient à la liste l. La liste initiale ne sera pas modifiée.

###

def testpy-undsupprime():bksl-nl """ Tests pour la fonction supprime """bksl-nl print("Tests de supprime passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import supprimebksl-nl# testpy-undsupprime()bksl-nlbksl-nl 5/5

def supprime(l, e):bksl-nl """ Liste, int -> Listebksl-nl Supprime la première occurrence de e la liste l """bksl-nl passbksl-nlbksl-nl

Concaténation de deux listes¶

Si \(l_1\) et \(l_2\) sont deux listes, on appelle concaténation de \(l_{1}\) avec \(l_{2}\) la liste constituée des éléments de \(l_1\) suivis des éléments de \(l_2\). Par exemple, la concaténation des listes \(l_1 = (0, 1, 6)\) et \(l_2 = (9, 4, 1)\) est la liste \((0, 1, 6, 9, 4, 1)\) ; par contre la concaténation des listes \(l_{2}\) et \(l_1\) (dans cet ordre) est la liste \((9, 4, 1, 0, 1, 6)\). La concaténation de la liste vide avec la liste \(l_1\) est la liste \((0, 1, 6)\).

Compléter le tableau ci-dessous.

l1 l2 concatene(l1, l2)

\((3, 5, 7)\) \((2, 4, 6)\)

\((2, 4, 6)\) \((3, 5, 7)\)

\((4, 6)\) \((3, 5, 7)\)

La liste vide \((3, 5, 7)\)

2. Écrire une fonction python récursive concatene qui étant donné deux listes l1 et l2 renvoie la concaténation de ces deux listes. Les listes l1 et l2 ne seront pas modifiées. Vous utiliserez comme cas de base le cas où l1 est la liste vide, et l'appel récursif aura la forme concatene(queue(l1), l2).

###

def testpy-undconcatene():bksl-nl """ Tests pour la fonction concatene """bksl-nl print("Tests de concatene passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import concatenebksl-nl# testpy-undconcatene()bksl-nlbksl-nl 5/5

def concatene(l1, l2):bksl-nl """ Liste, Liste -> Listebksl-nl Concatène les deux listes """bksl-nl passbksl-nlbksl-nl

Division de listes¶

Écrire une fonction est_2ton qui prend en argument une liste l et qui renvoie True si et seulement si la liste l est constituée d'exactement deux éléments.
On souhaite écrire une fonction divise qui divise en deux parties "à peu près égales" une liste l. Les longueurs des deux listes résultantes doivent différer au plus d'un, et tous les éléments de la liste l doivent se retrouver dans l'une uniquement des deux listes renvoyées. Ainsi si divise(l), renvoie les listes l1 et l2, on a : concatene(l1, l2) qui contient les mêmes éléments (avec répétition, mais pas forcément le même ordre) que l.
1. l est la liste \((1, 2, 3, 4, 5)\). Parmi les propositions ci-dessous, déterminer celle(s) qui peuve(nt) être renvoyées par l'instruction divise(l) :
  - l1 = (1, 2, 3) et l2 = (3, 4, 5)
  - l1 = (1, 3, 5) et l2 = (2, 4)
  - l1 = (1, 2, 3) et l2 = (5, 4)
  - l1 = (1, 3, 4, 5) et l2 = (2)
  Justifier votre réponse.
2. En déduire une fonction divise qui réponde au problème posé. Pour le cas général, on remarquera que si une liste l est constituée d'au moins trois éléments, on peut la diviser en deux de la manière suivante :
  - on met à part les deux premiers éléments x1 et x2 de la liste l ;
  - on divise récursivement en deux listes l1 et l2 les éléments restants ;
  - on ajoute à l1 l'élément x1 et à l2 l'élément x2.

###

def testpy-unddivise():bksl-nl """ Tests pour la fonction divise """bksl-nl print("Tests de divise passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import divisebksl-nl# testpy-unddivise()bksl-nlbksl-nl 5/5

def divise(l):bksl-nl """ Liste -> Liste, Listebksl-nl Divise la liste l en deux listes """bksl-nl passbksl-nlbksl-nl

Pour les plus fous¶

L'objectif ici est de déterminer l'ensemble des parties d'un ensemble \(E\) à \(n\) éléments, que l'on note \(\mathcal{P}(E)\). Par exemple, si l'ensemble \(E\) est \(\{1, 2, 3\}\), l'ensemble des parties de \(E\) est :

\[ \mathcal{P}(E) = \{ \{\}, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\} \]

On remarquera plusieurs choses :

les éléments de \(\mathcal{P}(E)\) sont des ensembles ;
\(\emptyset \in \mathcal{P}(E)\) (on note parfois l'ensemble vide \(\{\}\) ou \(\emptyset\)) et \(E \in \mathcal{P}(E)\) ;

Si \(E = \emptyset\), que vaut \(\mathcal{P}(E)\) ?
Soit \(E = \{1, 2, 3\}\), et soit \(e = 3\).
1. Déterminer la liste de tous les sous-ensembles de \(E\) qui ne contiennent pas \(e\).
  
  On note cette liste \(E'\). 2. Déterminer la liste de tous les sous-ensembles de \(E\) qui contiennent \(e\).
  
  On note cette liste \(E''\). 3. Écrire \(E\) en fonction de \(E'\) et de \(E''\). Vous utiliserez pour cela les opérations ensemblistes \(\cup\) et \(\cap\). 3. Déduire des questions précédentes une fonction python récursive liste_sous_ensembles qui étant donné un ensemble \(E\), renvoie la liste de tous ses sous-ensembles.
On utilisera le type list pour représenter un ensemble. On rappelle que si E est une liste :
- E.pop() renvoie le premier élément de E en le supprimant de celle-ci ;
- E.append(sE) ajoute l'élément sE à la fin de la liste E ;
- si E1 et E2 sont deux listes, alors E1 + E2 est une liste constituée de la concaténation des éléments de E1 et de E2 ;
- E.copy() renvoie une liste dont les éléments sont les mêmes que ceux de E.
Si \(E\) possède \(n\) éléments, combien d'éléments possède \(\mathcal{P}(E)\) ?

###

def testpy-undlistepy-undsouspy-undensembles():bksl-nl """ Tests pour la fonction listepy-undsouspy-undensembles """bksl-nl print("Tests de listepy-undsouspy-undensembles passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import listepy-undsouspy-undensemblesbksl-nl# testpy-undlistepy-undsouspy-undensembles()bksl-nlbksl-nl 5/5

def listepy-undsouspy-undensembles(E):bksl-nl """ list -> listbksl-nl Renvoie la liste de tous les sous-ensembles de E """bksl-nl passbksl-nlbksl-nl

Liste `l`	`maximum(queue(l))`	`maximum(l)`
\((3, 5, 6, 1, 4)\)		\(6\)
\((8, 5, 6, 1, 4)\)
\((9, 3, 2, 12, 4, 1)\)
\((1, 2, 3, 4, 5, 6, 7, 8)\)

`l1`	`l2`	`concatene(l1, l2)`
\((3, 5, 7)\)	\((2, 4, 6)\)
\((2, 4, 6)\)	\((3, 5, 7)\)
\((4, 6)\)	\((3, 5, 7)\)
La liste vide	\((3, 5, 7)\)