SERIES DEXERCICES ET CORRIGE
TD1 : RECURSIVITE
Exercice 1
Ecrire une fonction snoc qui ajoute un l ment la fin dune liste.
Exercice 2
Ecrire une fonction rdc qui retourne une liste amput de son dernier l ment.
Exercice 3
Ecrire une fonction rac qui retourne le dernier l ment dune liste.
Exercice 4
Ecrire une fonction rac qui retourne le dernier l ment dune liste.
Exercice 5
Ecrire une fonction ajoutN qui ajoute un l ment la ni me position dune liste.
Exercice 6
Ecrire une fonction rech qui cherche si un l ment e se trouve la position p dune liste l.
Corrig
(de rech (l e p)
(cond
((> p (length l)) 'position non trouv e)
((= p 1) (if (eq (car l) e) (print "element trouv ") (print "element non trouv ")))
(t (rech (cdr l) e (- p 1)))))
Exercice 6
Ecrire une fonction inverser qui permet dinverser une liste l.
Corrig
(de inverser (l)(if (null l) nil
(append (inverser (cdr l)) (list (car l)))))
Programmation fonctionnelle
1
ENSI
TD2 : Programmation imp rative
Exercice 1
Ecrire une fonction it rative qui cherche si un l ment saisi au clavier se trouve une position saisie
au clavier dune liste pass e en param tre.
Corrig
(de chercher (l)
(let ((x (read)) (y (read))) (;;;;;;;;;code iteratif
)))
Exercice 2
Ecrire une fonction it rative qui retourne n puissance p.
Corrig
(de puissance (n p)(let ((resultat 1))
(while (> p 0)(setq resultat (* n resultat))(setq p (- p 1))) (print resultat))
)
(de puiss()
(let ((n (read)) (p (read))) (print n "puissance" p "egal ") (puissance n p)))
Exercice 3
Ecrire la version it rative de la fonction factorielle.
Corrig
(de factorielle (n)(let (( resultat 1)) (while (> n 1)
(setq resultat (* resultat n) n (- n 1))) (print resultat)))
Programmation fonctionnelle
2
ENSI
TD3 : LES ENSEMBLES
Exercice 1
Ecrire une fonction qui cherche si un l ment appartient un ensemble.
(de member (x liste)
(cond((null liste) ())
((equal (car liste) x) liste)
(t (member x (cdr liste) ) )))
Exercice 2
Ecrire une fonction qui cherche si une liste est un ensemble.
(de ensemble (liste)
(cond
((null liste) t)
((member (car liste) (cdr liste)) ())
(t (ensemble (cdr liste) ) ))
Exercice 3
Ecrire une fonction UNIQUE qui transforme une liste en un ensemble (sans doublons).
(de unique (liste)
(cond((null liste) ())
((member (car liste) (cdr liste))(unique (cdr liste)))
(t (cons (car liste) (unique (cdr liste)))))
Exercice 4
Ecrire une fonction INCLUS qui teste si tous les l ments d'une liste se trouvent dans une autre.
(de inclus (liste1 liste2)
(cond
((null liste1) t)
((member (car liste1) liste2)(inclus (cdr liste1) liste2))
(t ())))
Programmation fonctionnelle
3
ENSI
Exercice 5
Ecrire une fonction INTER qui cr un ensemble constitu des l ments communs.
(de inter (liste1 liste2)
(cond
((null liste1) ())
((member (car liste1) liste2)(unique(cons (car liste1) (inter (cdr liste1) liste2))))
(t (inter (cdr liste1) liste2))))
Programmation fonctionnelle
4
ENSI
TD4 : LES FONCTIONNELLES
Exercice 1
(de filtre (test l)
(cond
((null l) ())
((funcall test (car l)) (cons (car l) (filtre test (cdr l))))
(t (filtre test (cdr l)))))
(de petits (a l)
(filtre (lambda (x) (< x a)) l))
Exercice 2
(de pair (l)
Advertisement
(filtre (lambda (x) (= ( modulo x 2) 0)) l))
(de impair (l)
(filtre (lambda (x) (= ( modulo x 2) 1)) l))
Exercice 3
Ecrire une fonction qui retourne la liste des valeurs absolues des l ments dune liste.
(de list-abs-mapcar (l)
"liste des vals abs"
(mapcar 'abs l))
(list-abs-mapcar '(-1 2 -3 4 -5 6))
; --> (1 2 3 4 5 6)
Exercice 4
Programmation fonctionnelle
5
ENSI
1. Ecrire une fonction qui retourne f(1).
2. Appliquer cette fonction avec f(x)=3x +2
(de f-de-un (f)
(funcall f 1))
(de f1 (x)
(+ 2 (* 3 x x)))
Exercice 5
Ecrire une variante de la fonction mapcar mapcar-fill (f l1 l2) o f est une fonction, l1 et l2 des listes
et qui retourne la m me chose que mapcar si les deux listes sont de m me longueur et une liste dont
les premiers l ments sont les m mes que ce qui est renvoy par mapcar et le reste des l ments
sont les l ments suppl mentaires de la liste la plus longue. Exemples :
; (mapcar-fill + (1 5 8) (3 4 2))
;(4 9 10)
; (mapcar-fill + (1 5 8) (3 4 2 6 7 4 2))
;(4 9 10 6 7 4 2)
(de mapcar-fill (fun l1 l2)
(cond ((null l1) l2)
((null l2) l1)
(t (cons (funcall fun (car l1) (car l2))
(mapcar-fill fun (cdr l1) (cdr l2))))))
(mapcar-fill (lambda (x y) (- ( 3 x) ( 2 y))) (1 5 8) (3 4 2 6 7 4 2))
Exercice 6
crire une fonction mappend (fun list) qui applique la fonction fun chaque l ment de la liste list (et
dont le r sultat doit tre une autre liste) puis renvoie la concat nation des r sultats ainsi obtenus.
Exemple :
? (mappend (lambda (x) (list x (1+ x))) (5 3 9 2 5))
=(5 6 3 4 9 10 2 3 5 6)
Programmation fonctionnelle
6
ENSI
?(mapcar (lambda (x) (list x (1+ x))) (5 3 9 2 5))
= ((5 6) (3 4) (9 10) (2 3) (5 6))
(de mappend (fun l)
(if (null l) ()
(append (funcall fun (car l))
(mappend fun (cdr l)))))
Exercice 7
Ecrire une fonction combien qui retourne le nombre d'elements de la liste verifiant pred
(combien 'evenp '(1 5 7 6 2))
=2
(combien 'numberp '(2 3 4 a b 5 t + 8))
=5
(combien (lambda (x) (= ( modulo x 2) 0)) '(1 5 7 6 2))
(de combien (pred l)
(if (null l)
0
(+ (combien pred (cdr l))
(if (funcall pred (car l))
1
0))))
(de combien (pred l)
Programmation fonctionnelle
7
ENSI
(cond
((null l) 0)
((funcall pred (car l)) (+ 1(combien pred (cdr l))))
(t (combien pred (cdr l)))))
Exercice 8
(de next-line (l)
(mapcar + (cons 0 l) (append l (list 0))))
1. Tester la fonction next-line en lappliquant n fois la liste (1).
2. En utilisant la fonction next-line, crire une fonction triangle (n) qui construit une liste contenant
les listes correspondant aux lignes du triangle de Pascal dordre n.
(triangle 0)
((1))
(triangle 1)
((1) (1 1))
(triangle 2)
((1) (1 1) (1 2 1))
(triangle 3)
((1) (1 1) (1 2 1) (1 3 3 1))
(triangle 4)
((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))
(next-line (next-line (next-line (next-line '(1)))))
(de nfois-nl (n)
(if (= n 1) (next-line '(1))
(next-line (nfois-nl (- n 1)))))
Programmation fonctionnelle
8
ENSI
(de triangle (n)
(cond
((= n 0) '((1)))
(t (append (triangle (- n 1) ) (list (nfois-nl n))))))
Programmation fonctionnelle
9
ENSI
Exercice 1
Advertisement
TD 5 : Fonctions de TRI
Ecrire une fonction TRI qui affiche un menu permettant lutilisateur de choisir un algorithme de tri
appliquer. La liste trier est saisie au clavier.
TRI RAPIDE
(de petit (l a)
(cond
((null l) ())
((< (car l) a) (cons (car l) (petit (cdr l) a)))
(t (petit (cdr l) a))))
(de grand (l a)
(cond
((null l) ())
((>= (car l) a) (cons (car l) (grand (cdr
l) a)))
(t (grand (cdr l) a))))
(de trirapide (l)
(if (NULL l) ()
(append (trirapide (petit (cdr l) (car l))) (list (car l)) (trirapide (grand (cdr l) (car l))))))
TRI PAR INSERTION
(de tri_inser (l)
(cond
((null l) () )
((= (length l) 1) l)
(t (cons (min l) (tri_inser (supp l (min l)))))))
; min
(de min (l)
Programmation fonctionnelle
10
ENSI
(cond
((null l) (print "n existe pas"))
((< (car l) (min (cdr l))) (car l))
(t (min (cdr l)))))
; supp:
(de supp (l x)
(if (= (car l) x) (cdr l)
(cons (car l) (supp (cdr l) x))))
(de tri()
(let ((l))
;saisie de la liste l ment par l ment
(print "introduire le nombre d'element")
(setq nbel (read))
(print "introduire les elements de la liste")
(while (> nbel 0)
(newl l (read))
(setq nbel (- nbel 1))
)
(print "1.Tri_Rapide")
(print "2.Tri_insertion")
(print "3.Tri_a_bulles")
(setq choix (read))
(cond
((= choix 1) (setq l (trirapide l)))
((= choix 2) (setq l (tri_inser l))) ;
(t (print V rifier votre choix))
)
Programmation fonctionnelle
11
ENSI
l ; pour retourner la liste r sultat
)
)
Ou pour la saisie de la liste en une seule fois
(de tri()
(let ((l))
(print "introduire la liste")
(setq l (read))
(print "1.Tri_Rapide")
(print "2.Tri_insertion")
(print "3.Tri_a_bulles")
(setq choix (read))
(cond
((= choix 1) (setq l (trirapide l)))
((= choix 2) (setq l (tri_inser l))) ;
(t (print V rifier votre choix))
)
l
)
)
Programmation fonctionnelle
12
ENSI
TD6 : ARBRE BINAIRE DE RECHERCHE
Un arbre binaire peut tre d fini en LISP par
(racine fils_gauche fils_droite)
O racine est un atome et fils_gauche et fils_droite sont deux listes qi repr sentent respectivement
le sous-arbre gauche et le sous-arbre droite de racine
Exercice 1 :
Ecrire une fonction qui permet dins rer un l ment dans un arbre binaire de recherche sa bonne
position.
(de inserer(l e)
(cond
((null l) (list e))
((< e (car l)) (append (list (car l)) (list (inserer (cadr l) e))(list (caddr l))))
(t (append (list (car l)) (list (cadr l)) (list (inserer (caddr l) e))))))
Exercice 2 :
Ecrire une fonction qui permet de transformer une liste d l ments sous forme dun arbre binaire de
recherche en se servant de la fonction inserer. La racine de larbre sera le dernier l ment de la liste.
(de transArbre (l)
(if (null l) nil
(ins (transArbre (cdr l)) (car l))))
Exercice 3 :
Ecrire une fonction qui permet de transformer directement une liste d l ments sous forme dun
Advertisement
arbre binaire de recherche (sans se servir de la fonction inserer). La racine de larbre sera le premier
l ment de la liste.
(de arbre(l)
(cond
((null l) ())
(t (append (list (car l)) (list (arbre (petit (cdr l) (car l))))
(list (arbre (grand (cdr l) (car l))))))))
Programmation fonctionnelle
13
ENSI
Exercice 4 :
Ecrire une fonction qui permet de transformer une liste d l ments sous forme dun arbre binaire de
recherche quilibr . La racine de larbre sera donc choisie parmi les l ments de la liste.
Principe : Prendre chaque appel r cursif la racine l l ment au milieu de la liste tri e
(de arbreEquilib(l)
(cond
((null l) ())
(t (append (list (racine l)) (list (arbreEquilib (petit (supprime (racine l) l) (racine l))))
(list (arbreEquilib (grand (supprime (racine l) l) (racine l))))))))
(de racine (l) ;retourne la racine qui est l' l ment au milieu de la liste tri e
(if (null l) ()
(pos (tri l)(+ 1(div (lenght l) 2)))))
;(pos l n) retourne l' l ment en position n dans la liste l
;(supprime a l) supprime a de la liste l
Programmation fonctionnelle
14
ENSI
TD 7 D rivation dExpressions Alg briques
(de deriv (exp var)
(cond ((numberp exp) 0)
((atom exp) (if (equal exp var) 1 0))
((equal (car exp) '+)
(list '+ (deriv (cadr exp) var) (deriv (caddr exp) var)))
((equal (car exp) '*)
(list '+ (list '* (cadr exp) (deriv (caddr exp) var))
(list '* (deriv (cadr exp) var) (caddr exp))))
(t 'bof)
)
)
(de simplif (exp)
(cond ((null exp) ())
((atom exp) exp)
((equal (car exp) '+)
(simplif_plus (cadr exp) (caddr exp)))
((equal (car exp) '*)
(simplif_mult (cadr exp) (caddr exp)))
(t erreur)
)
)
(de simplif_plus (A1 A2)
(cond ((equal A1 0) (simplif A2))
((equal A2 0) (simplif A1))
Programmation fonctionnelle
15
ENSI
(t (list + (simplif A1) (simplif A2)))))
(de simplif_mult (A1 A2)
(cond ((or (equal A1 0) (equal A2 0)) 0)
((equal A1 1) (simplif A2))
((equal A2 1) (simplif A1))
(t (list * (simplif A1) (simplif A2)))))
Fonction SIMPLIFIER
Applique r cursivement le processus de simplification jusqu'
l'obtention d'une expression irr ductible.
(de simplifier (exp)
(let ((dexp (simplif exp)))
(if (equal exp dexp) exp (simplifier dexp))))
(de deriver (exp var)
(simplifier (deriv exp var)))
Programmation fonctionnelle
16
ENSI
TD8 Les Macro-fonctions
Exercice 1
D finir une macro myPow telle que l valuation dune expression de la forme (myPow nom n)
d finisse la fonction nom comme l l vation la puissance n dun nombre :
?( myPow cube 3)
=cube
? (cube 4)
=64
?( myPow carre 2)
=carre
? (carre 5)
=25
Une simple macro qui ne consid re que les cas n = 2 et n = 3 :
(dmd myPow (nom n)
`(de ,nom (x)
(cond
((equal ,n 2)(* x x ))
((equal,n 3)(* x x x))
)))
Ou pour nimporte quelle valeur de n on peut faire appel la fonction puissance d finie
pr c demment ou la red finir dans la macro :
(dmd myPow (nom n)
`(de ,nom (x)
(puissance x ,n))
Programmation fonctionnelle
17
ENSI
TD 9 : Exploration des Arborescences
Recherche en profondeur
Exercice 1 :
Ecrire une fonction qui permet de chercher une solution s dans un arbre E en effectuant un parcours
Advertisement
en profondeur
(de rech_prof (E s)
(cond
((null E) ())
((atom E) (progn (print E) (if (= E s) s)))
(t (progn (print (car E))
(cond
((= (car E) s) s)
((rech_prof (cadr E) s) s)
(t (rech_prof(caddr E) s) ))))))
Exercice 2 :
Ecrire une fonction qui permet de chercher le maximum des nSuds dans un arbre E en effectuant un
parcours en profondeur. Nous supposons que tous les nSuds sont des nombres positifs.
(de max_prof (E)
(cond
((null E) 0)
((atom E) (progn (print E) E))
(t (progn (print (car E)) (let (( mg (max_prof (cadr E))) ( md (max_prof (caddr E))))
(cond
((< (car E) mg) (if (< mg md ) md mg))
( t (if(> (car E) md) (car E) md) )
))))))
Programmation fonctionnelle
18
ENSI
Recherche en largeur
Exercice 1 :
Ecrire une fonction qui permet de chercher une solution s dans un arbre E en effectuant un parcours
en largeur.
(de RL (E s)
(rech_larg (list E) s))
(de rech_larg (E s)
(cond
((null E) E)
((null (car E)) (rech_larg (cdr E) s))
((atom E) (progn (print (car E) ) (if (= E s) E)))
((atom (car E)) (progn (print (car E) ) (if (= (car E) s) s (rech_larg (cdr E) s))))
(t (progn (print (caar E))
(cond
((equal s (caar E)) (caar E))
(t (rech_larg (append (cdr E) (list (cadar E)) (list (caddar E))) s))
)))))
Programmation fonctionnelle
19
ENSI
TD 10 : Base de connaissances
; Base = un ensemble de personnes (nom, pr nom, ville o elles habitent,
; ge et nombre de livres poss d s)
(setq Base '( (Tounsi Ali Mednine 45 150)
(Tounsi Meriem Nabeul 32 200)
(Tounsi Saleh Mednine 69 20)
(Ben Mohamed Sami Tunis 28 500)
(Ben Mohamed Tarek Nabeul 55 60)
(Ben Mohamed Fatma Sfax 19 180)
))
(de nom (u) (car u))
(de prenom (u) (cadr u))
(de ville (u) (caddr u))
(de age (u) (car (cdddr u)))
(de nb-livres (u) (cadr (cdddr u)))
afficher toutes les personnes
afficher les personnes qui s'appellent Ben Mohamed
afficher les personnes qui habitent Mednine
afficher les personnes dont le nom est un argument
rechercher la premi re personne qui a X ans (X = un argument)
rechercher la premi re personne qui poss de moins de 100 livres
rechercher la premi re personne habitant Mednine qui a plus de 50 ans
calculer la somme des livres poss d s par toutes les personnes
calculer la somme des livres poss d s par les personnes habitant Mednine
calculer la somme des livres poss d s par les membres de la famille X
calculer la moyenne des ges de toutes les personnes
calculer la moyenne des ges des personnes de la famille X
construire une copie de la base
construire une copie de la base sans indication du nombre de livres poss d s
rechercher toutes les personnes qui habitent Mednine
rechercher toutes les personnes qui n'habitent pas Nabeul
rechercher toutes les personnes qui portent le nom X
rechercher toutes les personnes qui portent le nom X et qui habitent Y
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
Programmation fonctionnelle
20
ENSI