cours  |  td  |  examens  |  doc  |  liens  |  horaires
 Scheme

Université de Caen - UFR de Sciences
Deug MIAS-MASS
Marc Chemillier

Scheme - TD supplémentaire

Représentation des ensembles




  • Exercices : (1h1/2)

    1. Faire la fonction (adjoindre x l) qui ajoute un élément à un ensemble. Faire (union l1 l2) et (inter l1 l2).
      (define (adjoindre x l)
        (define (aux l res) 
          (cond ((null? l) (cons x res))
                ((equal? x (car l)) (append res l))
                (else (aux (cdr l) (cons (car l) res)))))
        (aux l '()))
      
      (define (adjoindre2 x l)
        (define (aux laux)
          (cond ((null? laux) (cons x l))
                ((equal? x (car laux)) l)
                (else (aux (cdr laux)))))
        (aux l))
      
      (define (adjoindre3 x l) (if (member x l) l (cons x l)))
      
      (define (union l1 l2)
        (cond ((null? l1) l2)
              ((member (car l1) l2) (union (cdr l1) l2))
              (else (union (cdr l1) (cons (car l1) l2)))))
      
      (define (union2 l1 l2)
        (cond ((null? l1) l2)
              (else (union2 (cdr l1) (adjoindre (car l1) l2)))))
      
      (define (inter l1 l2)
        (define (aux l1 res)
          (cond ((null? l1) res)
                ((member (car l1) l2) 
                 (aux (cdr l1) (cons (car l1) res)))
                (else (aux (cdr l1) res))))
        (aux l1 '()))
      
    2. Représentation par des listes ordonnées.
      Faire (union l1 l2) et (inter l1 l2).
      (define (union-bis l1 l2)
        (define (aux l1 l2 res)
          (cond ((null? l1) (append (reverse res) l2))
                ((null? l2) (append (reverse res) l1))
                ((< (car l1) (car l2)) 
                 (aux (cdr l1) l2 (cons (car l1) res)))
                ((= (car l1) (car l2)) 
                 (aux (cdr l1) (cdr l2) (cons (car l1) res)))
                (else (aux l2 l1 res))))
        (aux l1 l2 '()))
      
      (define (inter-bis l1 l2)
        (define (aux l1 l2 res)
          (cond ((or (null? l1) (null? l2)) (reverse res))
                ((< (car l1) (car l2)) (aux (cdr l1) l2 res))
                ((= (car l1) (car l2)) 
                 (aux (cdr l1) (cdr l2) (cons (car l1) res)))
                (else (aux l2 l1 res))))
        (aux l1 l2 '()))
      

  • Avec machines : (1h1/2) Recherche de zéros


  • Parcours de labyrinthe


    cours  |  td  |  examens  |  doc  |  liens  |  horaires
     Scheme