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

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

Scheme - TD n° 10
21 mai 2003

Récursions terminales (suite), map et lambda




  • Exercices : (1h1/2)

    1. Evaluer les expressions suivantes :
      > ((lambda (x) (+ x 1)) 3) 
      4
      
      > ((lambda (x y) (list x y y x)) 3 4) 
      (3 4 4 3)
      
      > (map (lambda (x) (+ x 1)) '(3 4 5)) 
      (4 5 6)
      
      > (map (lambda (x) (list x (* 2 x))) '(3 4 5)) 
      ((3 6) (4 8) (5 10))
      
      > ((lambda (f) (f 2)) (lambda (x) (+ x 1))) 
      3
      
      > ((lambda (f) (f 2)) sqrt) 
      1.4142135623731
      
      > (map sqrt ((lambda (x y z) (list z x y)) 4 9 16)) 
      (4 2 3)
      
      > (map (lambda (f) (f 2)) (list sqrt log log sqrt)) 
      (1.4142135623731
       0.69314718055995
       0.69314718055995
       1.4142135623731)
      
    2. La méthode de Newton consiste à calculer:

      yn = 1 ( yn-1 +  x  )
             2            yn-1

      avec un premier terme quelconque y0. Faire (newton n x y0) en version terminale.

      (define (newton n x y0)
        (cond ((= n 0) y0)
              (else (newton (- n 1) x (/ (+ y0 (/ x y0)) 2)))))

    3. On veut calculer le premier terme tel que yn2 - x en valeur absolue < eps. Modifier la fonction en conséquence.
      (define (newton x y0 eps)
        (cond ((< (abs (- (* y0 y0) x)) eps) y0)
              (else (newton x (/ (+ y0 (/ x y0)) 2) eps))))
      
    4. On veut calculer le premier terme tel que yn- yn-1 en valeur absolue < eps. Modifier la fonction en conséquence.
      (define (newton x y eps)
        (let ((z (/ (+ y (/ x y)) 2)))
          (cond ((< (abs (- z y)) eps) z)
                (else (newton x z eps)))))
      
    5. Faire en version terminale la fonction (moyenne liste) qui calcule la moyenne d'une liste de nombres.
      
      (define (moyenne liste)
        (define (aux l s)
          (cond ((null? l) (/ s (length liste)))
                (else (aux (cdr l) (+ s (car l))))))
        (if (null? liste) '() (aux liste 0))) 
      
      (define (moyenne liste)
        (define (aux l s n)
          (cond ((null? l) (/ s n))
                (else (aux (cdr l) (+ s (car l)) (+ n 1)))))
        (if (null? liste) '() (aux liste 0 0)))
      
    6. Faire en version terminale la fonction (som-prod liste) qui calcule la somme et le produit d'une liste de nombres.
      (define (som-prod liste)
        (define (aux l s p)
          (cond ((null? l) (list s p))
                (else (aux (cdr l) (+ s (car l)) (* p (car l))))))
        (if (null? liste) '() (aux liste 0 1)))
      
      (define (som-prod liste)
        (define (aux l res op)
          (cond ((null? l) res)
                (else (aux (cdr l) (op res (car l)) op))))
        (if (null? liste)
            '()
            (list (aux liste 0 +) (aux liste 1 *))))
      
    7. Faire en version terminale la fonction (exporap x n) qui calcule xn avec l'algorithme rapide
      xn = x*xn-1 si n est impair, et
      xn=(xn/2)2 si n est pair.
      
      (define (exprap x n)
        (define (aux a y n)
          (cond ((= n 0) a)
                ((even? n) (aux a (* y y) (/ n 2)))
                (else (aux (* a y) y (- n 1)))))
        (aux 1 x n))
      
      

  • Avec machines : (1h1/2) Évaluation du tp noté


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