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

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

Scheme - TD n° 6
2 avril 2003

Récursions numériques (suite)




  • Exercices : (1h1/2)

    1. Faire une fonction (tous-egaux? n) qui donne #t si n n'a qu'un chiffre ou si tous ses chiffres sont égaux, et #f sinon (Partiel 1996).
      (define (tous-egaux? n)
       (cond ((< n 10) #t)
             (else (let ((q (quotient n 10)))
                     (and (tous-egaux? q)
                          (= (remainder q 10) (remainder n 10)))))))
      
      
    2. Suite de Conway :

      Calculer la suite définie par u0 quelconque, et un = un-1 / 2 si un-1 pair,    = 3 * un-1 + 1 sinon.

      (define (conway u0 n)
       (cond ((= n 0) u0)
             (else (calcul (conway u0 (- n 1))))))
      
      (define (calcul x) 
       (display x) (display " ")
       (if (even? x) (/ x 2) (+ (* 3 x) 1)))
      
    3. Faire une fonction (leibniz n) qui calcule la somme :

      1 - 1 + 1 - 1 + ... + (-1)n  1 
           3    5    7                2n+1

      Remarque : Cette somme converge vers pi sur 4

      > (* 4 (leibniz 2000)) 
      3.14209240368353
      
      
      (define (leibniz n)
       (cond ((= n 0) 1)
             ((even? n) (+ (f n) (leibniz (- n 1))))
             (else (+ (- (f n)) (leibniz (- n 1))))))
      
      (define (f n) (/ 1 (+ (* 2 n) 1)))
      
      
      (define (leibniz n)
       (cond ((= n 0) 1)
             (else (+ (f n) (leibniz (- n 1))))))
      
      (define (f n)
       (if (even? n) (/ 1 (+ (* 2 n) 1)) (- (/ 1 (+ (* 2 n) 1)))))
      
      
      (define (leibniz n)
       (cond ((= n 0) 1)
             (else ((if (even? n) + -) (leibniz (- n 1)) (f n)))))
      
    4. Faire une fonction qui calcule l'expression :

      racine-somme 1

      Indication : Faire une fonction (racine-somme p n) qui calcule

      racine-somme 2

      (define (racine-somme p n)
       (cond ((= p n) (sqrt n))
            (else (sqrt (+ p (racine-somme (+ p 1) n))))))
      
    5. Faire une fonction (compter a n) qui calcule le nombre de façons de faire la monnaie de la somme a avec n sortes de pièces et/ou billets. Par exemple, pour a = 10 euros avec 4 sortes de pièces et/ou billets (1 2, 5 ou 10 euros), il y a 10 solutions :
      5+5, 5+2+2+1, 5+2+1+1+1, 5+1+1+1+1+1, 2+2+2+2+2, 2+2+2+2+1+1, 2+2+2+1+1+1+1, 2+2+1+1+1+1+1+1, 2+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1
      (define (compter a n)
       (cond ((= a 0) 1)
             ((< a 0) 0)
             ((= n 0) 0)
            (else (+ (compter (- a (piece-max n)) n)
                     (compter a (- n 1))))))
      
      (define (piece-max n)
        (cond ((= n 1) 1)
              ((= n 2) 2)
              ((= n 3) 5)
              ((= n 4) 10)))
      
      


  • Avec machines : (1h1/2) Jeu du piquet


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