Marc Chemillier - Cours de Scheme

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)

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)

La méthode de Newton consiste à calculer:
y_n = 1 ( y_n-1 + x )
2 y_n-1
avec un premier terme quelconque y₀. 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)))))
```

On veut calculer le premier terme tel que y_n² - 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))))

On veut calculer le premier terme tel que y_n- y_n-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)))))

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)))

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 *))))

Faire en version terminale la fonction (exporap x n) qui calcule xⁿ avec l'algorithme rapide
xⁿ = x*x^n-1 si n est impair, et
xⁿ=(x^n/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é

Scheme