Informatique T4 - Page des travaux pratiques - Environnement de développement - Syntaxe de Oz |
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.
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.
{Length Xs}
renvoie la longueur de la liste
Xs
. La liste vide a une longueur nulle.
{Browse {Length [r a p h]}} % affiche 4 {Browse {Length [[r a p] h]}} % affiche 2 {Browse {Length [[r a p h]]}} % affiche 1
{Member X Ys}
renvoie true
si X
est un élément de la liste Ys
,
false
sinon.
{Browse {Member p [r a p h]}} % affiche true {Browse {Member c [r a p h]}} % affiche false {Browse {Member p [r [a p] h]}} % affiche false
{Append Xs Ys}
renvoie la concaténation des
listes Xs
et Ys
.
{Browse {Append [r a] [p h]}} % affiche [r a p h] {Browse {Append [r [a]] [p h]}} % affiche [r [a] p h] {Browse {Append [r a] [[p h]]}} % affiche [r a [p h]]
{Nth Xs N}
renvoie le N
ème élément
de la liste Xs
.
{Browse {Nth [r a p h] 3}} % affiche p {Browse {Nth [r [a p] h] 3}} % affiche h {Browse {Nth [[r a p h]] 3}} % quel est le resultat?
{Take Xs N}
renvoie une liste contenant les
N
premiers éléments de la liste Xs
.
{Browse {Take [r a p h] 2}} % affiche [r a] {Browse {Take [r a p h] 7}} % affiche [r a p h] {Browse {Take [r [a p] h] 2}} % quel est le resultat?
{Drop Xs N}
renvoie la liste Xs
sans ses N
premiers éléments.
{Browse {Drop [r a p h] 2}} % affiche [p h] {Browse {Drop [r a p h] 7}} % affiche nil {Browse {Drop [r [a p] h] 2}} % quel est le resultat?
{TakeDrop Xs N Ys Zs}
est une
procédure qui généralise les fonctions Take
et
Drop
.
Après appel, Ys
contient les N
premiers
éléments de Xs
, le reste de Xs
étant lié à
Zs
.
local Ys Zs in {TakeDrop [r a p h] 2 Ys Zs} {Browse Ys} % affiche [r a] {Browse Zs} % affiche [p h] end
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
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]
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]
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
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:
{AddDigits D1 D2 CI}
, qui prend trois chiffres binaires
D1
, D2
et CI
, et renvoie une
liste de deux chiffres binaires représentant leur somme. Le bit
CI
et le premier chiffre du résultat est un chiffre de
report. Exemples:
{Browse {AddDigits 1 0 0}} % affiche [0 1] {Browse {AddDigits 1 1 0}} % affiche [1 0] {Browse {AddDigits 1 0 1}} % affiche [1 0] {Browse {AddDigits 1 1 1}} % affiche [1 1]
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
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
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]]
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]
.
Tri par insertion. Il consiste à prendre les éléments de la liste un à un, et de les insérer au bon endroit dans une liste triée. A la fin, la seconde liste contient tous les éléments dans l'ordre. Conseil : Définissez une fonction qui calcule le résultat de l'insertion d'une valeur x dans une liste triée ys. Voir la figure gauche ci-dessous.
Tri par sélection. Il consiste à retirer de la liste l'élément le plus petit, le mettre dans le résultat, et de recommencer avec la liste restante. Les éléments sont donc retirés de la liste initiale exactement dans l'ordre du résultat final. Conseil : Définissez une fonction qui renvoie l'élément minimum d'une liste, ainsi qu'une fonction qui calcule le résultat de la suppression d'une valeur x d'une liste ys. Voir la figure droite ci-dessous.
Exemple de tri par insertion |
Exemple de tri par sélection |
Tri à bulles. Il consiste à parcourir la liste en échangeant les paires d'éléments consécutifs qui ne sont pas dans l'ordre. On effectue autant de parcours que des échanges sont nécessaires. Autrement dit, on arrête dès qu'un parcours n'a fait aucun échange. Voir la figure gauche ci-dessous.
Tri rapide (quicksort). Cette méthode consiste à choisir une valeur pivot, et séparer les éléments de la liste en deux parties : ceux inférieurs au pivot, et ceux supérieurs au pivot. Les deux parties sont alors triées, puis concaténées (la partie inférieure avant la partie supérieure). Pour le pivot, on peut prendre le premier élément de la liste à trier. Voir la figure droite ci-dessous.
Exemple de tri à bulles |
Exemple de tri rapide |
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.