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

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

Scheme - TD n° 9
14 mai 2003

Récursion terminale, représentation des nombres en chiffres romains
  • Exercices : (1h1/2)

    1. Faire en version terminale la fonction (iota n) qui fabrique la liste décroissante (n ... 3 2 1), en utilisant un compteur croissant. 
      (define (iota n)
  (define (aux k res)
    (cond ((> k n) res)
          (else (aux (+ k 1) (cons k res)))))
  (aux 1 '()))
    2. Faire en version terminale la fonction (maximum l) qui calcule le maximum d'une liste de nombres. 
      (define (maximum l)
  (define (aux l var)
    (cond ((null? l) var)
          (else (aux l (max (car l) var)))))
  (aux (cdr l) (car l)))
    3. Faire en version terminale la fonction (our-reverse l) qui inverse une liste. 
      (define (our-reverse l)
  (define (aux l res)
    (cond ((null? l) res)
          (else (aux (cdr l) (cons (car l) res)))))
  (aux l '()))
    4. Faire en version terminale la fonction (enleve x l) qui enlève toutes les occurrences de x dans l. 
      (define (enleve x l)
  (define (aux l res)
    (cond ((null? l) (reverse res))
          (else (aux (cdr l)
                     (if (equal? (car l) x)
                         res
                         (cons x res))))))
  (aux l '()))

(define (enleve x l)
  (define (aux l res)
    (cond ((null? l) res)
          (else (aux (cdr l)
                     (if (equal? (car l) x)
                         res
                         (append res (list x)))))))
  (aux l '()))
    5. Faire en version terminale la fonction (somexp x n) calculant l'expression suivante, sans variable auxiliaire et sans sous-programme (Juin 1992) :

      1 + 1 + 1 + 1 + ... + x
           1!    2!    3!        n! 

      
(define (compter l)
  (define (aux n l1 l2)
    (cond ((and (null? l1) (null? l2)) n)
          ((null? l1) (aux n (car l2) (cdr l2)))
          ((pair? l1) (aux n (car l1) (cons (cdr l1) l2)))
          (else (aux (+ n 1) (car l2) (cdr l2)))))
  (if (null? l) 0 (aux 0 (car l) (cdr l))))
    6. Faire en version terminale la fonction (compter l) qui compte les atomes non vides de la liste l à tous les niveaux : (compter '((a) ((b c) ()))) -> 3 
      
(define (compter l)
  (define (aux n l1 l2)
    (cond ((and (null? l1) (null? l2)) n)
          ((null? l1) (aux n (car l2) (cdr l2)))
          ((pair? l1) (aux n (car l1) (cons (cdr l1) l2)))
          (else (aux (+ n 1) (car l2) (cdr l2)))))
  (if (null? l) 0 (aux 0 (car l) (cdr l))))
  • Avec machines : (1h1/2) Représentation en chiffres romains
    cours  |  td  |  examens  |  doc  |  liens  |  horaires
     Scheme