Aller au contenu

Listes et algorithmes récursifs

Présentation

Stocker les données est un problème fondamental en informatique. Nous verrons au cours de cette année différentes manières de le faire. Étant donné une collection finie de valeurs \(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. Si \(l\) est une liste de nombres, on dispose alors des fonctions suivantes :

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 considère la liste \(l = (0, 1, 42, "Bonjour", \pi)\).

  1. Que renvoie est_vide(l) ?
  2. Que renvoie tete(l) ?
  3. Que renvoie queue(l) ? Quelle est le type de queue(l) ?
  4. Que renvoie ajoute(l, 93) ?
  5. Que fait l'instruction affiche(l) ?

Remarque. On peut donner une définition récursive de 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).

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

Commenter l'affichage réalisé.

Premier exemple

Écrire les instructions python permettant de stocker les listes

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

Vous utiliserez uniquement les fonctions creer_vide, ajoute. Vous n'avez pas le droit d'utiliser des tableaux.

###
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

Toutes les questions suivantes doivent être traitées en utilisant uniquement les fonctions décrites dans le paragraphe d'introduction. Vous n'avez pas le droit d'utiliser les tableaux. Vous n'avez pas non plus 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

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

###
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 (inclus) à n (inclu) dans l'ordre croissant.

  • Écrire une fonction nombresII_aux qui étant donné deux entiers n et i, renvoie la liste constituée des entiers de i à n dans l'ordre croissant.
  • En déduire une fonction nombresII 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, -59)\), la longueur de \(l\) est 4. 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.

###
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

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.

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

Quelle est l'avantage de l'instruction appartient(l, e) par rapport à l'instruction nombre_occurrences(l, e) == 0 pour déterminer si l'élément e appartient à 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

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

Maximum des éléments d'une liste

Écrire une fonction maximum2 qui étant donné deux entiers a et b renvoie le plus grand entier parmi a et b.

En déduire une fonction python récursive maximum qui étant donnée une liste d'entiers non vide en renvoie le plus grand.

###
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

Insérer dans une liste

Écrire une fonction insere qui étant donné une liste l, un élément e et un entier i renvoie la liste constituée des éléments de l dans lequel l'élément e a pour indice i. On supposera que i est un entier tel que \(0 \leq i \leq \texttt{len}(l)\). Aucun comportement particulier n'est attendu dans le cas où i ne vérifierait pas ces conditions. La liste initiale l ne sera pas modifiée.

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

def insere(l, e, i):bksl-nl """ Liste, int, int -> Listebksl-nl Insère l'élément e dans la liste l à l'indice i """bksl-nl passbksl-nlbksl-nl

Concaténation de deux listes

Si \(l_1\) et \(l_2\) sont deux listes, on appelle concaténation de \(l1\) avec \(l2\) la liste constituée des éléments de \(l_1\) puis 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)\).

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

###
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

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

  2. On souhaite écrire une fonction divise qui divise en deux 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 de sortie. Ainsi si divise(l), renvoie les listes l1 et l2, on a : concatene(l1, l2) qui contient les mêmes éléments que l.

    1. l est la liste \((1, 2, 3, 4, 5)\). Parmi les propositions ci-dessous, déterminer celle qui peuvent-être renvoyées par l'instruction divise(l) :

      • l1 = (1, 2, 3), l2 = (3, 4, 5)
      • l1 = (1, 3, 5), l2 = (2, 4)
      • l1 = (1, 3), l2 = (2, 4)
      • l1 = (1, 3, 4, 5), 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)\) ;
  1. Si \(E = \emptyset\), que vaut \(\mathcal{P}(E)\) ?
  2. 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''\). On pourra utiliser les opérations ensemblistes \(\cup\) et \(\cap\).
  3. Déduire des fonctions suivantes une fonction python liste_sous_ensembles qui étant donné un ensemble \(E\), détermine la liste de tous ses sous-ensembles. On utilisera pour cela le type python list, ainsi que les méthodes pop, et append. On supposera que tous les éléments des listes manipulées sont uniques.
  4. 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

Documents