Séance 3
Programmation récursive avec des listes

Cette séance poursuit l'utilisation de la récursivité comme technique de programmation. Nous allons l'utiliser sur des listes. N'oubliez pas de spécifier les fonctions que vous écrivez, et d'utiliser des invariants pour garantir leur correction.

Enoncés des exercices

  1. Quelques fonctions générales sur les listes. Voici une liste de fonctions à implémenter, avec quelques exemples de leur utilisation. Choisissez-en quelques-unes et programmez-les en raisonnant de manière inductive sur la structure des listes.

  2. Multiplions. Écrivez une fonction MultList telle que {MultList L} renvoie le résultat de la multiplication des éléments de la liste L. Par exemple,

       {Browse {MultList [1 2 3 4]}}   % affiche 24
    

  3. Nombres factoriels. Écrivez une fonction Fact telle que {Fact N} renvoie la liste des N premiers nombres factoriels dans l'ordre croissant. Par exemple,

       {Browse {Fact 4}}   % affiche [1 2 6 24]
    

  4. Mettons les listes à plat. Écrivez une fonction Flatten prenant une liste L en paramètre. Les éléments de L peuvent eux-même être des listes, dont les éléments peuvent aussi être des listes, et ainsi de suite. L'appel {Flatten L} renvoie la liste ``aplatie'', c'est-à-dire les éléments de L et des listes contenues dans L qui ne sont pas des listes. Exemple:

       {Browse {Flatten [a [b [c d]] e [[[f]]]]}}   % affiche [a b c d e f]
    

  5. Occurrences d'une sous-liste. Écrivez une fonction FindString telle que {FindString S T} renvoie la liste des occurrences de la succession de caractères S dans le texte T. Chaque occurrence est identifiée par la position de son premier caractère dans T. Par exemple,

       {Browse {FindString [a b a b] [a b a b a b]}}   % affiche [1 3]
       {Browse {FindString [a] [a b a b a b]}}         % affiche [1 3 5]
       {Browse {FindString [c] [a b a b a b]}}         % affiche nil
    

    Conseil: commencez par écrire une fonction Prefix telle que {Prefix L1 L2} renvoie true si L1 est un préfixe de L2, false sinon. Par exemple,

       {Browse {Prefix [1 2 1] [1 2 3 4]}}   % affiche false
       {Browse {Prefix [1 2 3] [1 2 3 4]}}   % affiche true
    

  6. Représentation binaire d'entiers avec des listes. Écrivez une fonction Add telle que {Add B1 B2} renvoie le résultat de l'addition des nombres binaires B1 et B2. Un nombre binaire est représenté par une liste de chiffres binaires (0 ou 1). Le chiffre le plus significatif est le premier élément de la liste. Par exemple,

       {Browse {Add [1 1 0 1 1 0] [0 1 0 1 1 1]}}   % affiche [1 0 0 1 1 0 1]
    

    Quelques remarques:

  7. Comptage d'occurrences. Écrivez une fonction Count telle que {Count L1 L2} renvoie une liste avec le nombre de fois que chaque élément de L2 apparaît L1. La valeur retournée est une liste de paires E#N, où E est un élément de L2 et N est le nombre de fois que E apparaît dans L1. On suppose qu'aucun élément n'apparaît deux fois dans L2. Par exemple,

       {Browse {Count [a b a d b c d e] [b c d]}}   % affiche [b#2 c#1 d#2]
       {Browse {Count [a b a d b c d e] [a g d]}}   % affiche [a#2 g#0 d#2]
       {Browse {Count [a b a d b c d e] nil}}       % affiche nil
    

  8. Enlevons les intrus. Écrivez une fonction FilterList telle que {FilterList L1 L2} renvoie la liste résultant de L1 après avoir supprimé tous les éléments qui apparaissent dans L2. Par exemple,

    	
       {Browse {FilterList [1 2 1 4 2 3 4 5] [2 3 4]}}       % affiche [1 1 5]
       {Browse {FilterList [1 2 1 4 2 3 4 5] [20 2 3 4]}}    % affiche [1 1 5]
       {Browse {FilterList [1 2 1 4 2 3 4 5] [20 30 40]}}    % affiche [1 2 1 4 2 3 4 5]
       {Browse {FilterList [1 2 1 4 2 3 4 5] [1 2 3 4 5]}}   % affiche nil
    

  9. Qui fait quoi? Nous voulons écrire un programme pour assigner automatiquement des problèmes à nos étudiants. Au départ, nous disposons d'une liste de problèmes [P1 ... PN] et une liste d'étudiants, où chaque étudiant est représenté par une liste de la forme [Email Nom]. Il y a plus d'étudiants que de problèmes, et nous voulons assigner chaque problème au même nombre d'étudiants. Vous pouvez supposer que le nombre d'étudiants est un multiple du nombre de problèmes.

    Écrivez une fonction AssignProblems telle que {AssignProblems Problems Students} renvoie une liste de listes de la forme [Email Problem] représentant l'assignation des problèmes aux étudiants. Par exemple,

       declare
       Pbs = [p1 p2]
    
       Stds = [['Roland Dyens' 'rdyens@foo.boo']
               ['Yngwie Malmsteen' 'ymalmste@foo.boo']
               ['Steve Morse' 'smorse@foo.boo']
               ['Muza Rubackyte' 'mrubacky@foo.boo']
               ['Tarja Turunen' 'tturunen@foo.boo']
               ['Frank Zappa' 'fzappa@foo.boo']]
    
       {Browse {AssignProblems Pbs Stds}}
       % affiche la liste
       % [['rdyens@foo.boo' p1]
       %  ['ymalmste@foo.boo' p2]
       %  ['smorse@foo.boo' p1]
       %  ['mrubacky@foo.boo' p2']
       %  ['tturunen@foo.boo' p1]
       %  ['fzappa@foo.boo' p2]]
    

  10. Je trie, tu tries, il trie... Cet exercice consiste à implémenter des algorithmes dans le modèle déclaratif. Les algorithmes ci-dessous sont tous des algorithmes de tri. Vous devez donc implémenter autant de fonctions qui trient une liste d'entiers. Chacun des algorithmes est illustré avec la liste [5 1 7 2 6 4 3].

Exercice individuel (échéance: le 28 octobre 2004)

Remplissez le formulaire avec votre réponse, ensuite sélectionnez votre tuteur dans la liste. Une fenêtre apparaîtra avec le contenu d'un e-mail que vous devrez envoyer.

Sélectionnez maintenant le nom de votre tuteur dans la liste :


Luis Quesada et Raphaël Collet - 20 octobre 2004