Programmation fonctionnelle 1, chapitre 1 : exercices

Ces exercices accompagnent PF1 - Chapitre 1 - Cours. Tout a été vérifié dans Racket 8.10.

Mode d'emploi

D'abord sur papier. Le DST se fait sur papier, avec la cheatsheet imprimée pour seul document (slide 5). Entraîne-toi dans ces conditions : une feuille, un crayon, la cheatsheet, et DrRacket fermé.
Ensuite, vérifie. Pour les parties A à C, tape les expressions dans la zone d'interactions. Pour les parties D à I, utilise le fichier PF1-ch1-autocorrection.rkt (voir ci-dessous).
Enfin seulement, les indices et les solutions, repliés. Ouvre un indice à la fois et recommence à chercher entre deux.
Niveaux : 1 = application directe du cours ; 2 = il faut réfléchir ; 3 = niveau DST exigeant.
Contrat avant le code. Pour chaque fonction à écrire, commence par noter sur ta feuille ce qu'elle prend, ce qu'elle renvoie, et deux exemples. Par exemple : ;; carre : nombre -> nombre, (carre 3) vaut 9. Tu sauras quoi tester, et un correcteur voit tout de suite que tu as compris la question.
Tiens un carnet d'erreurs dans Obsidian : chaque erreur, avec la règle qui l'aurait évitée (« (remainder -9 4) vaut −1 : remainder prend le signe du dividende »). Relis-le avant le DST.

Le fichier d'autocorrection PF1-ch1-autocorrection.rkt

Ouvre-le dans DrRacket. Chaque fonction à écrire y est déjà déclarée, avec un corps provisoire (error ...).
Remplace ce corps par ton code (le nom et les paramètres sont imposés).
Tout en bas du fichier, seule la ligne de la partie D est active au départ. Enlève le ; devant la ligne de la partie que tu travailles (et remets-en un devant les parties terminées, pour alléger le bilan), puis clique sur Run.
Lis le bilan : n success(es) 0 failure(s) 0 error(s) veut dire que tout passe. Pour chaque test raté, DrRacket affiche la valeur obtenue (actual) et la valeur attendue (expected).

Les tests vérifient les résultats, pas le style : c'est à toi de contrôler qu'une fonction demandée « terminale » l'est vraiment.

AÉvaluer à la main

Pour chaque expression, écris ce qu'affiche DrRacket, ou « erreur » avec la raison en quelques mots. Cours : parties 3 à 6.

A1. Échauffement (niveau 1)

(+ 1 2 3)
(- 10 4 3)
(* 2 (+ 3 4))
(/ 12 4)
(/ 10 4)
(/ 10 4.0)
(quotient 17 5)
(modulo 17 5)
(expt 2 10)
(sqrt 49)
(max 4 9 2)
(abs (- 3 8))

Réponses A1

Racket

(+ 1 2 3)       ; → 6
(- 10 4 3)      ; → 3
(* 2 (+ 3 4))   ; → 14
(/ 12 4)        ; → 3
(/ 10 4)        ; → 5/2
(/ 10 4.0)      ; → 2.5
(quotient 17 5) ; → 3
(modulo 17 5)   ; → 2
(expt 2 10)     ; → 1024
(sqrt 49)       ; → 7
(max 4 9 2)     ; → 9
(abs (- 3 8))   ; → 5

Les deux à surveiller : le 5, une fraction exacte simplifiée et non 2.5, et le 6, où un seul flottant suffit à rendre le résultat inexact.

A2. Les pièges (niveau 2)

(quotient -22 4)
(remainder -22 4)
(modulo -22 4)
(- 7)
(/ 1 3 2)
(+ 1/2 1/3)
(* 2 0.5)
(= 3 3.0)
(equal? 3 3.0)
(< 1 5 3)
(and 5 #t "fin")
(or #f 0)
(not (not 7))
(if (- 3 3) "oui" "non")
(+1 2)
((* 2 3))
(+ 1 (* 2 3) (- 4))
(max 1 2.0)

Réponses A2

Racket

(quotient -22 4)           ; → -5
(remainder -22 4)          ; → -2
(modulo -22 4)             ; → 2
(- 7)                      ; → -7
(/ 1 3 2)                  ; → 1/6
(+ 1/2 1/3)                ; → 5/6
(* 2 0.5)                  ; → 1.0
(= 3 3.0)                  ; → #t
(equal? 3 3.0)             ; → #f
(< 1 5 3)                  ; → #f
(and 5 #t "fin")           ; → "fin"
(or #f 0)                  ; → 0
(not (not 7))              ; → #t
(if (- 3 3) "oui" "non")   ; → "oui"
(+1 2)                     ; → erreur : application: not a procedure
((* 2 3))                  ; → erreur : application: not a procedure
(+ 1 (* 2 3) (- 4))        ; → 3
(max 1 2.0)                ; → 2.0

1 à 3 : −22/4 = −5,5. quotient tronque vers zéro (−5) ; remainder prend le signe de −22 : −22 = 4 × (−5) + (−2) ; modulo prend le signe de 4 : −22 = 4 × (−6) + 2.
5 : (/ 1 3 2) calcule 1 / 3 / 2.
11 et 12 : and renvoie sa dernière valeur si aucune n'est #f ; or renvoie la première valeur vraie, et 0 est vrai en Racket.
13 : (not 7) vaut #f (7 est vrai), donc (not #f) vaut #t.
14 : (- 3 3) vaut 0, et 0 est vrai : c'est le piège de la partie 5.4.
15 : +1 est lu comme le nombre 1. 16 : Racket calcule 6, puis essaie de l'appliquer.
17 : 1 + 6 + (−4).

A3. Avec des définitions (niveau 2)

On a tapé ceci dans la zone de définitions :

Racket

(define A 5)
(define (double x) (* 2 x))
(define (carre x) (* x x))
(define (h x y) (- (carre x) (double y)))

(double A)
(carre (double 3))
(h 3 2)
(h 2 3)
(double (h A 1))
double
(carre 2 3)
(h A)
Écris la trace complète, par substitution, de (h (double 1) A).

Réponses A3

Racket

(define A 5)
(define (double x) (* 2 x))
(define (carre x) (* x x))
(define (h x y) (- (carre x) (double y)))
(double A)           ; → 10
(carre (double 3))   ; → 36
(h 3 2)              ; → 5
(h 2 3)              ; → -2
(double (h A 1))     ; → 46
double               ; → #<procedure:double>
(carre 2 3)          ; → erreur : carre: arity mismatch
(h A)                ; → erreur : h: arity mismatch
(h (double 1) A)     ; → -6

La trace de la question 9 :

(h (double 1) A)
(h (* 2 1) A)
(h 2 5)
(- (carre 2) (double 5))
(- (* 2 2) (double 5))
(- 4 (double 5))
(- 4 (* 2 5))
(- 4 10)
-6

Au DST, une ligne par étape : on évalue d'abord les arguments, puis on remplace l'appel par le corps de la fonction.

A4. Portée, conditions et let (niveau 3)

Racket

(define x 10)
(define (f x) (+ x 1))
(define (g y) (+ x y))

(f 3)
(g 3)
(let ([x 1]) (g x))
(let ([x 2] [y x]) (+ x y))
(let* ([x 2] [y x]) (+ x y))
(if (> x 5) (f x) (g x))
(cond [(< x 5) "petit"] [(< x 50) "moyen"] [else "grand"])
(cond [(> x 5) 1] [(> x 8) 2] [else 3])
(and (> x 5) (f x))
(let ([a 5]) (let ([b (* a 2)]) (let ([a 1]) (+ a b))))
(let* ([a 2] [a (* a a)] [a (* a a)]) a)
(let ([a 1] [b 2]) (let ([a b] [b a]) (- a b)))

Indice

Pour chaque x, demande-toi : de quel x s'agit-il ? Celui du paramètre, celui d'un let, ou le x global ? Et regarde où la fonction a été écrite, pas d'où elle est appelée (partie 8.4 du cours).

Réponses A4

Racket

(define x 10)
(define (f x) (+ x 1))
(define (g y) (+ x y))
(f 3)                                                         ; → 4
(g 3)                                                         ; → 13
(let ([x 1]) (g x))                                           ; → 11
(let ([x 2] [y x]) (+ x y))                                   ; → 12
(let* ([x 2] [y x]) (+ x y))                                  ; → 4
(if (> x 5) (f x) (g x))                                      ; → 11
(cond [(< x 5) "petit"] [(< x 50) "moyen"] [else "grand"])    ; → "moyen"
(cond [(> x 5) 1] [(> x 8) 2] [else 3])                       ; → 1
(and (> x 5) (f x))                                           ; → 11
(let ([a 5]) (let ([b (* a 2)]) (let ([a 1]) (+ a b))))       ; → 11
(let* ([a 2] [a (* a a)] [a (* a a)]) a)                      ; → 16
(let ([a 1] [b 2]) (let ([a b] [b a]) (- a b)))               ; → 1

1 : le paramètre x de f masque le x global.
3 : g a été écrite là où x vaut 10 ; le x du let ne la concerne pas. (g 1) vaut 11.
4 : dans un let, l'expression de y est calculée avant que le nouveau x existe : y vaut 10, donc 2 + 10. En 5, avec let*, y vaut 2.
8 : la deuxième ligne est du code mort, puisque tout nombre supérieur à 8 est supérieur à 5.
9 : and renvoie la valeur de sa dernière expression, 11, et non #t.
10 : b est calculé avec a = 5, puis le a intérieur (1) masque l'extérieur : 1 + 10.
11 : let* permet de relier plusieurs fois le même nom : 2, puis 4, puis 16.
12 : le let intérieur étant parallèle, les deux expressions sont calculées avec les anciennes valeurs : le nouveau a vaut 2, le nouveau b vaut 1. C'est un échange de valeurs.

BTraduire

Cours : parties 3.1 et 3.2.

B1. Des maths vers Racket (niveau 1)

Traduis en Racket (a, b, x, y et n sont supposés définis) :

$5x^3 - x + 4$
$\frac{a - b}{a + b}$
$\sqrt{x^2 + y^2}$
$1 + 2 \times 3 - \frac{4}{2}$ (et donne sa valeur)
$\frac{1}{1 + \frac{1}{x}}$
$2^{n+1} - 1$
$|a - b| < 0{,}01$
$\frac{x + y}{2} \geq \sqrt{xy}$

Réponses B1

Avec x = 2, y = 8, a = 3, b = 1 et n = 4 pour vérifier :

Racket

(define x 2)
(define y 8)
(define a 3)
(define b 1)
(define n 4)
(+ (* 5 x x x) (- x) 4)                ; → 42
(/ (- a b) (+ a b))                    ; → 1/2
(sqrt (+ (* x x) (* y y)))             ; → 8.246211251235321
(- (+ 1 (* 2 3)) (/ 4 2))              ; → 5
(/ 1 (+ 1 (/ 1 x)))                    ; → 2/3
(- (expt 2 (+ n 1)) 1)                 ; → 31
(< (abs (- a b)) 0.01)                 ; → #f
(>= (/ (+ x y) 2) (sqrt (* x y)))      ; → #t

Pour la première, (+ (- (* 5 (expt x 3)) x) 4) est tout aussi juste. La dernière est un booléen : l'inégalité entre moyenne arithmétique et moyenne géométrique, vraie pour tous x, y ≥ 0.

B2. De Python vers Racket (niveau 1)

max(a, b) - min(a, b)
abs(x - y) <= 1
a % 2 == 0 and b % 2 == 0
x if x > 0 else -x
def perimetre(l, h): return 2 * (l + h)
n // 10, pour n ≥ 0. Question piège : pour n < 0, (quotient n 10) donne-t-il la même chose que n // 10 ?

Réponses B2

Racket

(define a 7)
(define b 4)
(define x 3)
(define y 5)
(- (max a b) (min a b))                       ; → 3
(<= (abs (- x y)) 1)                          ; → #f
(and (= (modulo a 2) 0) (= (modulo b 2) 0))   ; → #f
(and (even? a) (even? b))                     ; → #f
(if (> x 0) x (- x))                          ; → 3
(define (perimetre l h) (* 2 (+ l h)))
(perimetre 3 4)                               ; → 14
(quotient 2026 10)                            ; → 202
(quotient -7 10)                              ; → 0

Pour n < 0, non : en Python, -7 // 10 vaut −1 (arrondi vers le bas), alors que (quotient -7 10) vaut 0 (troncature vers zéro). L'équivalent exact serait (floor (/ n 10)), avec floor (arrondi vers le bas), hors programme.

B3. De Racket vers les maths (niveau 1)

(/ (+ a b c) 3)
(- (* 2 x) (/ 1 x))
(* (+ x 1) (- x 1))
(+ 1 (/ 1 (+ 1 (/ 1 2)))), et sa valeur
(sqrt (- (* b b) (* 4 a c)))

Réponses B3

$\frac{a + b + c}{3}$ , la moyenne des trois nombres.
$2x - \frac{1}{x}$ .
$(x + 1)(x - 1)$ , c'est-à-dire $x^2 - 1$ .
$1 + \cfrac{1}{1 + \cfrac{1}{2}}$ , qui vaut 5/3 :

Racket

(+ 1 (/ 1 (+ 1 (/ 1 2))))   ; → 5/3

$\sqrt{b^2 - 4ac}$ , la racine du discriminant $\Delta$ de ton cours de maths.

B4. Le mystère du 1.05 (niveau 3)

On te donne ces deux lignes :

;; ... 1+2*3/4+5*6 s'écrit usuellement 1+((2*3)/4)+(5*6)
(exact->inexact (+ 1 (+ (/ (* 2 3) 4 (* 5 6)))))

DrRacket affiche 1.05, alors que 1 + 2 × 3/4 + 5 × 6 vaut 32,5.

Dessine l'arbre de l'expression telle qu'elle est écrite.
Explique le 1.05.
Corrige l'expression pour obtenir 32.5, puis écris-en une version plus courte.

Indice 1

Compte les arguments de chaque opération. Combien en reçoit / ? Et le + intérieur ?

Indice 2

(/ a b c) calcule a / b / c, et (+ x) vaut x (partie 4.2 du cours).

Solution B4

exact->inexact
      |
      +
     / \
    1   +
        |
        /
      / | \
     *  4  *
    / \   / \
   2   3 5   6

La parenthèse qui devait fermer (/ (* 2 3) 4) a glissé après (* 5 6). La division reçoit donc trois arguments et calcule 6 / 4 / 30 = 1/20 ; le + intérieur n'a plus qu'un argument et vaut 1/20 ; le total vaut 1 + 1/20 = 21/20, soit 1,05.

Racket

(/ (* 2 3) 4 (* 5 6))                               ; → 1/20
(exact->inexact (+ 1 (+ (/ (* 2 3) 4 (* 5 6)))))    ; → 1.05
(exact->inexact (+ 1 (+ (/ (* 2 3) 4) (* 5 6))))    ; → 32.5
(exact->inexact (+ 1 (/ (* 2 3) 4) (* 5 6)))        ; → 32.5

La version courte utilise le fait que + accepte trois arguments. En Racket, une parenthèse mal placée ne provoque pas forcément d'erreur, elle peut changer le calcul en silence.

CTrouver et corriger l'erreur

Pour chaque code : l'erreur apparaît-elle avant l'exécution (au Run) ou pendant ? Quel message affiche DrRacket (le début suffit) ? Comment corriger ? Attention, certains codes ne provoquent aucun message et sont faux quand même. Cours : parties 3, 6, 7, 9 et 12.

C1 (niveau 1)

Racket

;; code à corriger
(define (triple x) (x * 3))
(triple 4)

Correction C1

Pendant l'exécution, à l'appel : application: not a procedure, avec given: 4. (x * 3) est une notation infixe : Racket essaie d'appliquer 4 aux arguments * et 3.

Racket

(define (triple x) (* x 3))
(triple 4)   ; → 12

C2 (niveau 1)

Racket

;; code à corriger
(define (moyenne a b) (/ (+ a b) 2)

Correction C2

Avant l'exécution, à la lecture : read-syntax: expected a `)` to close `(` . Il manque la parenthèse qui ferme le define.

Racket

(define (moyenne a b) (/ (+ a b) 2))
(moyenne 4 7)   ; → 11/2

C3 (niveau 1)

Racket

;; code à corriger
(define (positif x) (if (> x 0) x))

Correction C3

Avant l'exécution : if: missing an "else" expression. Il faut décider de ce que la fonction renvoie quand x ≤ 0, par exemple 0 :

Racket

(define (positif x) (if (> x 0) x 0))
(positif 5)    ; → 5
(positif -2)   ; → 0

C4 (niveau 1)

Racket

;; code à corriger
(define (fact n) (if (= n 0) 1 (* n (fact n-1))))

Correction C4

Avant l'exécution : n-1: unbound identifier. n-1 est un seul nom (partie 3.4 du cours).

Racket

(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
(fact 5)   ; → 120

C5 (niveau 1)

Racket

;; code à corriger
(define (aire-disque r) (* PI r r))
(aire-disque 2)

Correction C5

Avant l'exécution : PI: unbound identifier. Racket fournit pi en minuscules, et distingue majuscules et minuscules. Deux corrections possibles : utiliser pi, ou définir la constante PI soi-même.

Racket

(define (aire-disque r) (* pi r r))
(aire-disque 2)   ; → 12.566370614359172

C6 (niveau 2)

Racket

;; code à corriger
(define (distance x1 y1 x2 y2)
  (let ([dx (- x2 x1)]
        [dy (- y2 y1)]
        [d2 (+ (* dx dx) (* dy dy))])
    (sqrt d2)))

Correction C6

Avant l'exécution : dx: unbound identifier. Dans un let, d2 ne peut pas utiliser dx et dy, qui ne sont pas encore liés (partie 8.2 du cours). Il faut un let* :

Racket

(define (distance x1 y1 x2 y2)
  (let* ([dx (- x2 x1)]
         [dy (- y2 y1)]
         [d2 (+ (* dx dx) (* dy dy))])
    (sqrt d2)))
(distance 0 0 3 4)   ; → 5

C7 (niveau 1)

Racket

;; code à corriger
(define carre (x) (* x x))

Correction C7

Avant l'exécution : define: bad syntax (multiple expressions after identifier). Pour définir une fonction, le nom et les paramètres vont ensemble entre parenthèses.

Racket

(define (carre x) (* x x))
(carre 3)   ; → 9

C8 (niveau 2)

Racket

;; code à corriger
(define (categorie age)
  (cond [(>= age 18) "adulte"]
        [(>= age 65) "senior"]
        [else "mineur"]))

Correction C8

Aucun message, mais la fonction est fausse : « senior » n'est jamais renvoyé, car toute personne de 65 ans ou plus a déjà été classée « adulte » par la première ligne. C'est du code mort (partie 7.2 du cours). La condition la plus restrictive passe en premier :

Racket

(define (categorie age)
  (cond [(>= age 65) "senior"]
        [(>= age 18) "adulte"]
        [else "mineur"]))
(categorie 70)   ; → "senior"
(categorie 30)   ; → "adulte"
(categorie 12)   ; → "mineur"

C9 (niveau 2)

Racket

;; code à corriger
(define (somme n)
  (if (= n 0)
      0
      (+ n (somme n))))
(somme 3)

Correction C9

Pendant l'exécution : DrRacket finit par afficher Interactions disabled; out of memory. L'argument ne diminue jamais, donc le cas de base n'est jamais atteint, et chaque appel laisse une addition en attente (récursivité enveloppée infinie).

Racket

(define (somme n)
  (if (= n 0)
      0
      (+ n (somme (- n 1)))))
(somme 3)   ; → 6

C10 (niveau 1)

Racket

;; code à corriger
(define (double x) (* 2 x))
(double)

Correction C10

Pendant l'exécution : double: arity mismatch, avec expected: 1 et given: 0. Il faut passer un argument : (double 5).

C11 (niveau 1)

Racket

;; code à corriger
(define (suivant x) ((+ x 1)))
(suivant 2)

Correction C11

Pendant l'exécution : application: not a procedure, avec given: 3. La paire de parenthèses en trop autour de (+ x 1) demande d'appliquer 3.

Racket

(define (suivant x) (+ x 1))
(suivant 2)   ; → 3

C12 (niveau 3)

Racket

;; code à corriger
(define (pair? n)
  (if (= (modulo n 2) 0) #t #f))

Correction C12

Aucun message, mais deux défauts. Le style d'abord : (if condition #t #f) s'écrit simplement condition (partie 5.5 du cours). Le nom ensuite : pair? existe déjà en Racket, il teste tout autre chose (une paire, un objet des prochains chapitres sur les listes). Le définir soi-même le masque dans tout le fichier, ce qui peut casser du code qui en a besoin. Choisis un nom libre, ou utilise even?.

Racket

(define (est-pair? n) (= (modulo n 2) 0))
(est-pair? 10)   ; → #t
(est-pair? 7)    ; → #f

DÉcrire des fonctions simples

Cours : parties 5 à 7. Pour chaque fonction, le nom et les paramètres sont imposés (ce sont ceux du fichier d'autocorrection). Écris le contrat et deux exemples avant le code.

D1. Carré et cube (niveau 1)

Écris (carre x), puis (cube x) en réutilisant carre.

Indice

x³ = x × x².

Solution D1

Racket

(define (carre x) (* x x))
(define (cube x) (* x (carre x)))
(carre -4)   ; → 16
(cube 3)     ; → 27
(cube -2)    ; → -8

Réutiliser carre n'est pas obligatoire ici, mais c'est le bon réflexe : chaque fonction fait une chose, et les suivantes s'appuient dessus.

D2. Moyenne de trois nombres (niveau 1)

Écris (moyenne3 a b c). Que vaut (moyenne3 1 2 2) ? Pourquoi pas 1.6666666666666667 ?

Solution D2

Racket

(define (moyenne3 a b c) (/ (+ a b c) 3))
(moyenne3 1 2 3)                    ; → 2
(moyenne3 1 2 2)                    ; → 5/3
(exact->inexact (moyenne3 1 2 2))   ; → 1.6666666666666667

Avec trois entiers, la division donne une fraction exacte (partie 4.1 du cours). Pour obtenir un flottant, on convertit avec exact->inexact.

D3. Conversion de température (niveau 1)

Écris (celsius->fahrenheit c), sachant que $F = \frac{9}{5}C + 32$ . Le -> dans le nom est la convention de Racket pour les conversions (number->string, exact->inexact, slide 17). Que vaut (celsius->fahrenheit 37) ?

Solution D3

Racket

(define (celsius->fahrenheit c) (+ (* 9/5 c) 32))
(celsius->fahrenheit 100)   ; → 212
(celsius->fahrenheit 37)    ; → 493/5
(celsius->fahrenheit -40)   ; → -40

493/5, c'est 98,6 °F, en fraction exacte. Et −40 est la seule température identique dans les deux échelles.

D4. Un dé (niveau 1)

Écris (de), une fonction d'arité 0 qui renvoie un entier au hasard entre 1 et 6. Pourquoi ne pas écrire plutôt une constante (define DE (+ 1 (random 6))) ?

Solution D4

Racket

(define (de) (+ 1 (random 6)))
(de)   ; → (aléatoire) un entier entre 1 et 6

(random 6) renvoie un entier entre 0 et 5 ; on ajoute 1. Une constante serait tirée une seule fois, au moment de sa définition, et vaudrait ensuite toujours la même chose : c'est la leçon MYR contre (myr) de la slide 18 (partie 6.3 du cours).

D5. Trois prédicats (niveau 1)

Sans utiliser if :

(multiple? a b) : a est-il un multiple de b ? (b est non nul)
(meme-signe? a b) : a et b sont-ils tous les deux strictement positifs, ou tous les deux strictement négatifs ?
(ordonne? a b c) : a est-il inférieur ou égal à b, lui-même inférieur ou égal à c ?

Indice 1

Pour multiple?, pense à modulo. Pour ordonne?, souviens-toi que les comparaisons acceptent plus de deux arguments.

Indice 2

Pour meme-signe?, il y a une version directe avec or et and, et une version courte : quel est le signe de a × b quand a et b ont le même signe ?

Solution D5

Racket

(define (multiple? a b) (= (modulo a b) 0))
(define (meme-signe? a b) (> (* a b) 0))
(define (ordonne? a b c) (<= a b c))
(multiple? 12 4)      ; → #t
(multiple? 12 5)      ; → #f
(multiple? 0 7)       ; → #t
(meme-signe? -3 -5)   ; → #t
(meme-signe? -3 5)    ; → #f
(meme-signe? 0 5)     ; → #f
(ordonne? 2 2 3)      ; → #t
(ordonne? 1 3 2)      ; → #f

La version directe de meme-signe? : (or (and (> a 0) (> b 0)) (and (< a 0) (< b 0))). Elle est plus longue, mais elle ne demande aucune astuce : au DST, les deux sont justes.

D6. Année bissextile (niveau 2)

Une année est bissextile si elle est divisible par 4 sans l'être par 100, ou si elle est divisible par 400. Écris (bissextile? annee) sans if. Vérifie : 2024 oui, 2026 non, 1900 non, 2000 oui.

Indice 1

Traduis d'abord chaque morceau de phrase en prédicat : « divisible par 4 », « pas divisible par 100 », « divisible par 400 ». Une fonction auxiliaire (divisible? a b) rend le tout lisible.

Indice 2

La phrase a la forme « (A et B) ou C ».

Solution D6

Racket

(define (divisible? a b) (= (modulo a b) 0))
(define (bissextile? annee)
  (or (and (divisible? annee 4) (not (divisible? annee 100)))
      (divisible? annee 400)))
(bissextile? 2024)   ; → #t
(bissextile? 2026)   ; → #f
(bissextile? 1900)   ; → #f
(bissextile? 2000)   ; → #t

1900 est divisible par 4 et par 100, mais pas par 400 : pas bissextile. 2000 est divisible par 400 : bissextile. Ces deux années sont les tests qui départagent une solution juste d'une solution approximative.

D7. Tarif de cinéma (niveau 2)

Moins de 4 ans : gratuit (0 €) ; moins de 18 ans : 6 € ; 65 ans et plus : 7 € ; sinon 10 €. Écris (tarif age) avec un cond, puis teste les valeurs frontières : 3, 4, 17, 18, 64 et 65.

Indice

Un enfant de 2 ans a aussi moins de 18 ans : quelle condition doit passer en premier ?

Solution D7

Racket

(define (tarif age)
  (cond [(< age 4) 0]
        [(< age 18) 6]
        [(>= age 65) 7]
        [else 10]))
(tarif 3)    ; → 0
(tarif 4)    ; → 6
(tarif 17)   ; → 6
(tarif 18)   ; → 10
(tarif 64)   ; → 10
(tarif 65)   ; → 7

Les valeurs frontières sont l'endroit où se cachent les confusions entre < et <= : teste-les toujours.

D8. Jours dans un mois (niveau 2)

Écris (jours-mois m) pour une année non bissextile : février a 28 jours ; avril, juin, septembre et novembre en ont 30 ; les autres mois en ont 31.
Écris (jours-mois-annee m a), qui tient compte des années bissextiles, en réutilisant jours-mois et bissextile?.

Indice

or accepte autant d'arguments qu'on veut : (or (= m 4) (= m 6) ...).

Solution D8

Racket

(define (divisible? a b) (= (modulo a b) 0))
(define (bissextile? annee)
  (or (and (divisible? annee 4) (not (divisible? annee 100)))
      (divisible? annee 400)))
(define (jours-mois m)
  (cond [(= m 2) 28]
        [(or (= m 4) (= m 6) (= m 9) (= m 11)) 30]
        [else 31]))
(define (jours-mois-annee m a)
  (if (and (= m 2) (bissextile? a))
      29
      (jours-mois m)))
(jours-mois 2)              ; → 28
(jours-mois 11)             ; → 30
(jours-mois 12)             ; → 31
(jours-mois-annee 2 2024)   ; → 29
(jours-mois-annee 2 1900)   ; → 28
(jours-mois-annee 5 2024)   ; → 31

jours-mois-annee ne traite que le cas nouveau (février d'une année bissextile) et délègue tout le reste à jours-mois.

D9. Triangle possible (niveau 2)

Trois longueurs strictement positives a, b et c forment un vrai triangle si chacune est strictement inférieure à la somme des deux autres. Écris (triangle? a b c). Teste (3, 4, 5), (1, 2, 3) (un triangle aplati), (1, 1, 5) et (2, 2, 2).

Solution D9

Racket

(define (triangle? a b c)
  (and (< a (+ b c))
       (< b (+ a c))
       (< c (+ a b))))
(triangle? 3 4 5)   ; → #t
(triangle? 1 2 3)   ; → #f
(triangle? 1 1 5)   ; → #f
(triangle? 2 2 2)   ; → #t

D10. Chiffre des centaines (niveau 2)

Écris (chiffre-centaines n) pour n ≥ 0. Que vaut (chiffre-centaines 2026) ?

Indice

(quotient n 100) enlève les deux derniers chiffres (partie 4.3 du cours).

Solution D10

Racket

(define (chiffre-centaines n) (modulo (quotient n 100) 10))
(chiffre-centaines 2026)   ; → 0
(chiffre-centaines 1987)   ; → 9
(chiffre-centaines 45)     ; → 0

2026 donne 20 après le quotient, et le dernier chiffre de 20 est 0.

D11. La valeur du milieu (niveau 3)

Écris (mediane3 a b c), qui renvoie la valeur du milieu parmi trois nombres : (mediane3 3 1 2) vaut 2, (mediane3 5 5 1) vaut 5. Trouve deux méthodes : l'une avec un cond, l'autre en une ligne, avec max, min et une addition.

Indice 1

Avec cond : b est au milieu si a ≤ b ≤ c ou si c ≤ b ≤ a. Même raisonnement pour a et pour c.

Indice 2

En une ligne : que reste-t-il si l'on retire de la somme des trois nombres le plus grand et le plus petit ?

Solution D11

Racket

(define (mediane3 a b c)
  (- (+ a b c) (max a b c) (min a b c)))
(define (mediane3-cond a b c)
  (cond [(or (<= a b c) (<= c b a)) b]
        [(or (<= b a c) (<= c a b)) a]
        [else c]))
(mediane3 3 1 2)         ; → 2
(mediane3 5 5 1)         ; → 5
(mediane3-cond 3 1 2)    ; → 2
(mediane3-cond -1 7 3)   ; → 3

EVariables locales

Cours : partie 8.

E1. Prix final (niveau 1)

Un produit coûte ht euros hors taxe. Le prix TTC vaut ht × 6/5 (TVA à 20 %), puis une remise de remise pour cent s'applique. Écris (prix-final ht remise) avec un let* qui nomme le prix TTC, puis le montant de la remise. Utilise des fractions exactes (6/5 plutôt que 1.2) pour éviter les arrondis. Que vaut (prix-final 19 5) ?

Solution E1

Racket

(define (prix-final ht remise)
  (let* ([ttc (* ht 6/5)]
         [reduction (* ttc (/ remise 100))])
    (- ttc reduction)))
(prix-final 100 10)                    ; → 108
(prix-final 50 0)                      ; → 60
(prix-final 19 5)                      ; → 1083/50
(exact->inexact (prix-final 19 5))     ; → 21.66

Il faut let* et non let : reduction utilise ttc.

E2. Calculer une seule fois (niveau 1)

Écris (polynome x), qui calcule $x^4 + x^2 + 1$ en ne calculant x² qu'une seule fois (c'est l'idée de la slide 26).

Solution E2

Racket

(define (polynome x)
  (let ([x2 (* x x)])
    (+ (* x2 x2) x2 1)))
(polynome 2)   ; → 21
(polynome 0)   ; → 1

x⁴ = x² × x² : une fois x² nommé, tout le reste s'en déduit.

E3. Nombre de racines réelles (niveau 2)

Pour a ≠ 0, l'équation ax² + bx + c = 0 a deux, une ou zéro racines réelles, selon le signe du discriminant Δ = b² − 4ac. Écris (nb-racines a b c) avec un let qui calcule Δ une seule fois.

Solution E3

Racket

(define (nb-racines a b c)
  (let ([delta (- (* b b) (* 4 a c))])
    (cond [(> delta 0) 2]
          [(= delta 0) 1]
          [else 0])))
(nb-racines 1 -3 2)   ; → 2
(nb-racines 1 2 1)    ; → 1
(nb-racines 1 0 1)    ; → 0

Sans le let, il faudrait recopier l'expression de Δ dans chaque ligne du cond, et elle serait recalculée à chaque test.

E4. Encapsulation (niveau 2)

Écris (hypotenuse a b), la longueur de l'hypoténuse d'un triangle rectangle de côtés a et b, avec une fonction carre définie à l'intérieur de hypotenuse. Ensuite : dans un fichier qui ne contient que hypotenuse, que donne (carre 3) ? Pourquoi ?

Solution E4

Racket

(define (hypotenuse a b)
  (define (carre x) (* x x))
  (sqrt (+ (carre a) (carre b))))
(hypotenuse 3 4)    ; → 5
(hypotenuse 5 12)   ; → 13

carre n'existe qu'à l'intérieur de hypotenuse : c'est sa portée (partie 8.4 du cours). Écrit dans le fichier, l'appel est refusé dès le Run :

Racket

(define (hypotenuse a b)
  (define (carre x) (* x x))
  (sqrt (+ (carre a) (carre b))))
(carre 3)   ; → erreur : carre: unbound identifier

Tapé dans la zone d'interactions, le même appel donne carre: undefined; cannot reference an identifier before its definition.

FRécursivité enveloppée

Cours : partie 9. Pour chaque fonction, réponds d'abord par écrit aux quatre questions de la partie 9.3 (cas de base, cas récursif, terminaison, tests), puis écris le code, puis trace le plus petit cas qui n'est pas le cas de base.

F1. Factorielle robuste (niveau 1)

Écris (fact n) avec le cas de base n = 0 (par convention, 0! = 1). Que se passe-t-il avec (fact 0), et avec la factorielle de la slide 33 appelée sur 0 ?

Solution F1

Racket

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))
(fact 0)    ; → 1
(fact 5)    ; → 120
(fact 20)   ; → 2432902008176640000

La version de la slide 33 s'arrête à n = 1 : appelée sur 0, elle descend vers −1, −2… sans jamais s'arrêter (partie 9.4 du cours). Celle-ci couvre 0. (fact 20) montre au passage que les entiers de Racket n'ont pas de taille limite.

F2. Puissance (niveau 1)

Écris (puissance x n), qui calcule xⁿ pour un entier n ≥ 0 par multiplications successives, sans expt. Puis écris la trace de (puissance 2 3).

Indice 1

x⁰ = 1 pour tout x.

Indice 2

xⁿ = x × xⁿ⁻¹.

Solution F2

Racket

(define (puissance x n)
  (if (= n 0)
      1
      (* x (puissance x (- n 1)))))
(puissance 2 10)    ; → 1024
(puissance 3 0)     ; → 1
(puissance 1/2 3)   ; → 1/8
(puissance -2 3)    ; → -8

(puissance 2 3)
(* 2 (puissance 2 2))
(* 2 (* 2 (puissance 2 1)))
(* 2 (* 2 (* 2 (puissance 2 0))))
(* 2 (* 2 (* 2 1)))
(* 2 (* 2 2))
(* 2 4)
8

F3. Somme des impairs (niveau 1)

Écris (somme-impairs n), la somme des n premiers nombres impairs : 1 + 3 + 5 + … + (2n − 1). Calcule-la pour n = 1 à 5 : que remarques-tu ?

Indice

Le n-ième nombre impair est 2n − 1.

Solution F3

Racket

(define (somme-impairs n)
  (if (= n 0)
      0
      (+ (- (* 2 n) 1) (somme-impairs (- n 1)))))
(somme-impairs 1)    ; → 1
(somme-impairs 4)    ; → 16
(somme-impairs 10)   ; → 100

On obtient toujours n² : $1 + 3 + \dots + (2n - 1) = n^2$ . C'est un excellent exercice de récurrence pour ton cours de maths, et la fonction en suit exactement la structure : l'hérédité, c'est $n^2 = (n - 1)^2 + (2n - 1)$ .

F4. Nombre de chiffres (niveau 2)

Écris (nb-chiffres n) pour n ≥ 0. Attention : (nb-chiffres 0) doit valoir 1.

Indice 1

Un nombre inférieur à 10 a un seul chiffre.

Indice 2

(quotient n 10) enlève exactement un chiffre à n.

Solution F4

Racket

(define (nb-chiffres n)
  (if (< n 10)
      1
      (+ 1 (nb-chiffres (quotient n 10)))))
(nb-chiffres 0)         ; → 1
(nb-chiffres 7)         ; → 1
(nb-chiffres 2026)      ; → 4
(nb-chiffres 1000000)   ; → 7

Avec un cas de base (= n 0) qui renverrait 0, (nb-chiffres 0) vaudrait 0 : faux. Le choix du cas de base se vérifie toujours sur le plus petit cas possible.

F5. Somme des chiffres (niveau 2)

Écris (somme-chiffres n) pour n ≥ 0 : (somme-chiffres 2026) vaut 10.

Solution F5

Racket

(define (somme-chiffres n)
  (if (= n 0)
      0
      (+ (modulo n 10) (somme-chiffres (quotient n 10)))))
(somme-chiffres 2026)   ; → 10
(somme-chiffres 999)    ; → 27
(somme-chiffres 0)      ; → 0

Ici, le cas de base (= n 0) est le bon : la somme des chiffres de 0 vaut 0. Compare avec F4.

F6. Multiplier sans multiplier (niveau 2)

Écris (produit a b) pour un entier b ≥ 0, en n'utilisant que + et -. Pourquoi impose-t-on b ≥ 0, et pas a ≥ 0 ?

Solution F6

Racket

(define (produit a b)
  (if (= b 0)
      0
      (+ a (produit a (- b 1)))))
(produit 7 6)    ; → 42
(produit 7 0)    ; → 0
(produit -3 4)   ; → -12

La récursion porte sur b, qui doit descendre jusqu'à 0 ; a peut être n'importe quel nombre.

F7. Diviser par soustractions (niveau 2)

Pour a ≥ 0 et b > 0, écris (quotient-rec a b) et (reste-rec a b) par soustractions successives, sans quotient ni modulo.

Indice 1

Si a < b, le quotient vaut 0 et le reste vaut a.

Indice 2

Sinon, on retire b une fois : le quotient de a par b vaut 1 plus le quotient de a − b par b, et le reste ne change pas.

Solution F7

Racket

(define (quotient-rec a b)
  (if (< a b)
      0
      (+ 1 (quotient-rec (- a b) b))))
(define (reste-rec a b)
  (if (< a b)
      a
      (reste-rec (- a b) b)))
(quotient-rec 17 5)   ; → 3
(reste-rec 17 5)      ; → 2
(quotient-rec 4 5)    ; → 0
(reste-rec 15 5)      ; → 0

Remarque, pour préparer la partie G : reste-rec est déjà terminale (l'appel est directement le résultat), alors que quotient-rec est enveloppée.

F8. Une suite de ton cours de maths (niveau 2)

On pose $u_0 = 2$ et $u_n = 3u_{n-1} - 1$ pour n ≥ 1. Calcule à la main $u_0$ à $u_3$ , puis écris (suite-u n).

Solution F8

Racket

(define (suite-u n)
  (if (= n 0)
      2
      (- (* 3 (suite-u (- n 1))) 1)))
(suite-u 0)                ; → 2
(suite-u 1)                ; → 5
(suite-u 3)                ; → 41
(/ (+ (expt 3 4) 1) 2)     ; → 41

2, 5, 14, 41… La dernière ligne teste une conjecture : $u_n = \frac{3^{n+1} + 1}{2}$ . Démontre-la par récurrence en maths ; la fonction te permet de la vérifier sur autant de valeurs que tu veux avant de te lancer.

F9. Fibonacci (niveau 3)

F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2). Écris (fibo n). Combien d'appels à fibo déclenche (fibo 5) ? Dessine l'arbre des appels.

Indice 1

Il y a deux cas de base. Une seule ligne peut les couvrir tous les deux : que vaut F(n) quand n < 2 ?

Indice 2

Chaque appel qui n'est pas un cas de base en déclenche deux autres : dessine l'arbre de (fibo 5) et compte ses nœuds.

Solution F9

Racket

(define (fibo n)
  (if (< n 2)
      n
      (+ (fibo (- n 1)) (fibo (- n 2)))))
(fibo 10)   ; → 55
(fibo 20)   ; → 6765

                      fibo 5
              /                  \
         fibo 4                   fibo 3
        /      \                 /      \
    fibo 3    fibo 2         fibo 2    fibo 1
    /    \     /    \        /    \
 fibo 2 fibo 1 fibo 1 fibo 0 fibo 1 fibo 0
 /    \
fibo 1 fibo 0

15 appels pour (fibo 5), et 2 692 537 pour (fibo 30) : les mêmes valeurs sont recalculées encore et encore (fibo 3 deux fois, fibo 2 trois fois…). L'exercice G6 règle le problème.

F10. Le PGCD d'Euclide (niveau 2)

pgcd(a, 0) = a, et pgcd(a, b) = pgcd(b, a mod b). Écris (pgcd a b) pour a, b ≥ 0. Est-elle enveloppée ou terminale ? Pourquoi termine-t-elle ?

Solution F10

Racket

(define (pgcd a b)
  (if (= b 0)
      a
      (pgcd b (modulo a b))))
(pgcd 48 18)   ; → 6
(pgcd 17 5)    ; → 1
(pgcd 10 0)    ; → 10
(gcd 48 18)    ; → 6

(pgcd 48 18)
(pgcd 18 12)
(pgcd 12 6)
(pgcd 6 0)
6

Elle est terminale : l'appel récursif est directement le résultat. Elle termine parce que le second argument diminue strictement à chaque appel (a mod b < b) sans devenir négatif, donc il finit par valoir 0. Racket fournit gcd, pratique pour vérifier.

F11. Diviseurs et nombres premiers (niveau 3)

Écris (nb-diviseurs n) pour n ≥ 1 : le nombre de diviseurs de n entre 1 et n. Idée : une fonction auxiliaire (compte-diviseurs n d) qui compte les diviseurs de n parmi 1, 2, …, d.
Écris (premier? n) : n est premier quand il a exactement deux diviseurs.

Indice 1

Cas de base de compte-diviseurs : d = 0, aucun diviseur.

Indice 2

Cas récursif : on compte les diviseurs parmi 1, …, d − 1, et on ajoute 1 si d divise n. Et (nb-diviseurs n), c'est (compte-diviseurs n n).

Solution F11

Racket

(define (compte-diviseurs n d)
  (cond [(= d 0) 0]
        [(= (modulo n d) 0) (+ 1 (compte-diviseurs n (- d 1)))]
        [else (compte-diviseurs n (- d 1))]))
(define (nb-diviseurs n) (compte-diviseurs n n))
(define (premier? n) (= (nb-diviseurs n) 2))
(nb-diviseurs 12)   ; → 6
(nb-diviseurs 1)    ; → 1
(premier? 13)       ; → #t
(premier? 1)        ; → #f
(premier? 91)       ; → #f

1 n'est pas premier (un seul diviseur) : la définition « exactement deux diviseurs » le règle toute seule. 91 = 7 × 13. compte-diviseurs pourrait être définie à l'intérieur de nb-diviseurs (encapsulation). Elle mélange un appel terminal (ligne else) et un appel enveloppé : elle n'est donc pas récursive terminale. L'exercice G8 fait mieux.

GRécursivité terminale

Cours : partie 10.

G1. Enveloppée ou terminale ? (niveau 1)

Pour chaque fonction : enveloppée ou terminale ? Que calcule-t-elle ?

Racket

(define (g1 n) (if (= n 0) 1 (* 2 (g1 (- n 1)))))
(define (g2 n acc) (if (= n 0) acc (g2 (- n 1) (* 2 acc))))
(define (g3 a b) (if (= b 0) a (g3 b (modulo a b))))
(define (g4 n) (if (< n 10) 1 (+ (g4 (quotient n 10)) 1)))
(define (g5 n) (cond [(= n 0) #f] [(= n 1) #t] [else (g5 (- n 2))]))
(define (g6 n) (if (= n 0) 0 (g6 (g6 (- n 1)))))

Réponses G1

Racket

(define (g1 n) (if (= n 0) 1 (* 2 (g1 (- n 1)))))
(define (g2 n acc) (if (= n 0) acc (g2 (- n 1) (* 2 acc))))
(define (g3 a b) (if (= b 0) a (g3 b (modulo a b))))
(define (g4 n) (if (< n 10) 1 (+ (g4 (quotient n 10)) 1)))
(define (g5 n) (cond [(= n 0) #f] [(= n 1) #t] [else (g5 (- n 2))]))
(define (g6 n) (if (= n 0) 0 (g6 (g6 (- n 1)))))
(g1 10)      ; → 1024
(g2 10 1)    ; → 1024
(g3 48 18)   ; → 6
(g4 2026)    ; → 4
(g5 7)       ; → #t
(g6 5)       ; → 0

g1 : enveloppée, elle calcule 2ⁿ.
g2 : terminale, elle calcule acc × 2ⁿ.
g3 : terminale, c'est le PGCD de F10.
g4 : enveloppée, même si l'appel est écrit en premier dans l'addition : l'addition attend son résultat. C'est le nombre de chiffres.
g5 : terminale ; elle répond « n est-il impair ? » pour n ≥ 0. Pour un n négatif, elle ne s'arrête jamais (une boucle infinie, sans épuiser la mémoire).
g6 : l'appel extérieur est terminal, mais l'appel intérieur est un argument, donc il n'est pas terminal : la fonction n'est pas récursive terminale. Elle renvoie toujours 0.

G2. Suivre l'accumulateur (niveau 1)

Avec la fonction g de la slide 33, écris la trace de (g 4), puis celle de (g 4 2). Pourquoi 48 ?

Racket

(define (g n [acc 1])
  (if (= n 1)
      acc
      (g (- n 1) (* n acc))))

Solution G2

Racket

(define (g n [acc 1])
  (if (= n 1)
      acc
      (g (- n 1) (* n acc))))
(g 4)     ; → 24
(g 4 2)   ; → 48

(g 4 2)
(g 3 8)
(g 2 24)
(g 1 48)
48

L'accumulateur est parti de 2 au lieu de 1 : le résultat vaut 2 × 4!. C'est le défaut de la valeur par défaut visible (partie 10.4 du cours).

G3. Rendre terminal avec un accumulateur (niveau 2)

Écris les versions terminales suivantes, dans le style de ton enseignant (accumulateur avec valeur par défaut), et trace chacune sur un petit exemple :

(puissance-t x n [acc 1])
(nb-chiffres-t n [acc 1])
(somme-chiffres-t n [acc 0])

Indice 1

La méthode de la partie 10.3 : l'accumulateur part de ce que renvoyait le cas de base, le cas de base renvoie l'accumulateur, et l'opération se fait avant l'appel.

Indice 2

Pour puissance-t, l'appel récursif est (puissance-t x (- n 1) (* x acc)).

Solution G3

Racket

(define (puissance-t x n [acc 1])
  (if (= n 0)
      acc
      (puissance-t x (- n 1) (* x acc))))
(define (nb-chiffres-t n [acc 1])
  (if (< n 10)
      acc
      (nb-chiffres-t (quotient n 10) (+ acc 1))))
(define (somme-chiffres-t n [acc 0])
  (if (= n 0)
      acc
      (somme-chiffres-t (quotient n 10) (+ acc (modulo n 10)))))
(puissance-t 2 10)        ; → 1024
(nb-chiffres-t 2026)      ; → 4
(nb-chiffres-t 0)         ; → 1
(somme-chiffres-t 2026)   ; → 10

(somme-chiffres-t 2026)
(somme-chiffres-t 2026 0)
(somme-chiffres-t 202 6)
(somme-chiffres-t 20 8)
(somme-chiffres-t 2 8)
(somme-chiffres-t 0 10)
10

G4. Cacher l'accumulateur (niveau 2)

Réécris puissance-t dans le style avec fonction auxiliaire (partie 10.4 du cours) : (puissance-encapsulee x n), avec deux paramètres seulement, l'accumulateur étant caché dans une fonction locale. Que renvoie (puissance-t 2 3 5), et pourquoi puissance-encapsulee ne peut-elle pas avoir ce problème ?

Solution G4

Racket

(define (puissance-encapsulee x n)
  (define (boucle n acc)
    (if (= n 0)
        acc
        (boucle (- n 1) (* x acc))))
  (boucle n 1))
(define (puissance-t x n [acc 1])
  (if (= n 0)
      acc
      (puissance-t x (- n 1) (* x acc))))
(puissance-encapsulee 2 10)   ; → 1024
(puissance-encapsulee 5 0)    ; → 1
(puissance-t 2 3 5)           ; → 40

(puissance-t 2 3 5) vaut 5 × 2³ = 40 : l'accumulateur est parti de 5. Avec puissance-encapsulee, personne ne peut toucher à l'accumulateur de l'extérieur. Remarque aussi que boucle utilise directement le x de puissance-encapsulee, visible grâce à la portée : inutile de le lui passer en paramètre.

G5. Le miroir (niveau 3)

Écris (miroir n), qui renverse les chiffres de n : (miroir 1234) vaut 4321. Ici, la récursivité terminale avec accumulateur est la méthode naturelle. Que donne (miroir 1200), et pourquoi ?

Indice 1

À la main : on prend 4, puis 3, puis 2, puis 1, et on construit 4, puis 43, puis 432, puis 4321.

Indice 2

À chaque étape, le nouvel accumulateur vaut acc × 10 + le dernier chiffre de n, et n perd son dernier chiffre.

Solution G5

Racket

(define (miroir n [acc 0])
  (if (= n 0)
      acc
      (miroir (quotient n 10) (+ (* acc 10) (modulo n 10)))))
(miroir 1234)     ; → 4321
(miroir 7)        ; → 7
(miroir 1200)     ; → 21
(miroir 120021)   ; → 120021

(miroir 1234 0)
(miroir 123 4)
(miroir 12 43)
(miroir 1 432)
(miroir 0 4321)
4321

L'accumulateur combine les chiffres dans l'ordre inverse (partie 10.3 du cours), et ici, c'est exactement ce qu'on veut. (miroir 1200) vaut 21, parce que « 0021 » s'écrit 21 : les zéros de tête disparaissent. Et (= (miroir n) n) teste si n est un palindrome, comme 120021.

G6. Fibonacci en temps linéaire (niveau 3)

Écris (fibo-t n [a 0] [b 1]) avec deux accumulateurs : a et b sont deux nombres de Fibonacci consécutifs. Combien d'appels pour (fibo-t 30), contre 2 692 537 pour (fibo 30) ?

Indice 1

Au départ, a = F(0) et b = F(1).

Indice 2

Une étape fait passer le couple (a, b) à (b, a + b) et diminue n de 1. Quand n vaut 0, la réponse est a.

Solution G6

Racket

(define (fibo-t n [a 0] [b 1])
  (if (= n 0)
      a
      (fibo-t (- n 1) b (+ a b))))
(fibo-t 10)    ; → 55
(fibo-t 100)   ; → 354224848179261915075

(fibo-t 5 0 1)
(fibo-t 4 1 1)
(fibo-t 3 1 2)
(fibo-t 2 2 3)
(fibo-t 1 3 5)
(fibo-t 0 5 8)
5

31 appels pour (fibo-t 30) (n va de 30 à 0). La version de F9 demanderait environ 10²¹ appels pour n = 100 : des dizaines de milliers d'années, même à un milliard d'appels par seconde.

G7. Question de cours (niveau 2)

Dans DrRacket, (somme 5000000) (partie 9.3 du cours) s'arrête sur out of memory, alors que (somme-t 5000000) renvoie 12500002500000. Explique pourquoi en quelques lignes, avec les mots : pile d'exécution, cadre de pile, opération en attente, appel terminal.

Réponse G7

Racket

(define (somme-t n [acc 0])
  (if (= n 0)
      acc
      (somme-t (- n 1) (+ n acc))))
(somme-t 5000000)   ; → 12500002500000

Dans somme, chaque appel laisse une opération en attente (l'addition de n au résultat de l'appel suivant). Chacune occupe un cadre de pile sur la pile d'exécution : 5 millions de cadres attendent en même temps, et la limite de 256 Mo de DrRacket est dépassée. Dans somme-t, l'appel récursif est un appel terminal : il ne reste rien à faire après lui, donc Racket réutilise le cadre de l'appel en cours au lieu d'en empiler un nouveau. La mémoire utilisée reste constante, comme pour une boucle.

G8. Premier, en mieux (niveau 3)

Écris (premier-rapide? n), qui teste les diviseurs d = 2, 3, 4… seulement tant que d² ≤ n, avec une fonction locale récursive terminale (aucun-diviseur? d). Pourquoi peut-on s'arrêter à √n ?

Indice 1

Les cas de aucun-diviseur? : si d² > n, on n'a trouvé aucun diviseur, réponse #t ; si d divise n, réponse #f ; sinon, on essaie d + 1.

Indice 2

N'oublie pas les nombres inférieurs à 2, qui ne sont pas premiers.

Solution G8

Racket

(define (premier-rapide? n)
  (define (aucun-diviseur? d)
    (cond [(> (* d d) n) #t]
          [(= (modulo n d) 0) #f]
          [else (aucun-diviseur? (+ d 1))]))
  (and (>= n 2) (aucun-diviseur? 2)))
(premier-rapide? 2)         ; → #t
(premier-rapide? 1)         ; → #f
(premier-rapide? 91)        ; → #f
(premier-rapide? 97)        ; → #t
(premier-rapide? 1000003)   ; → #t
(premier-rapide? 1000001)   ; → #f

Si n = p × q avec p ≤ q, alors p² ≤ p × q = n, donc p ≤ √n : si n a un diviseur autre que 1 et lui-même, il en a un inférieur ou égal à √n. Pour 1000003, cela fait un millier d'essais au plus, au lieu d'un million. 1000001 = 101 × 9901 : le diviseur 101 est trouvé au centième essai. Tous les appels sont terminaux : chacun est le résultat d'une ligne du cond, et (aucun-diviseur? 2) est la dernière expression du and.

HProblèmes de synthèse

Ces problèmes mélangent tout le chapitre. Ils sont plus longs, comme un dernier exercice de DST.

H1. La conjecture de Syracuse (niveau 2)

Partant d'un entier n ≥ 1 : si n est pair, on le divise par 2 ; sinon, on le remplace par 3n + 1. On recommence jusqu'à tomber sur 1.

Écris (syracuse-suivant n), qui calcule le terme suivant.
Écris (etapes n), le nombre d'étapes pour atteindre 1, en récursivité enveloppée. Par exemple, 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 : (etapes 6) vaut 8.
Écris (etapes-t n [acc 0]), en récursivité terminale.
Que vaut (etapes 27) ? Et la question 3 de la méthode (« chaque appel se rapproche-t-il du cas de base ? »), que donne-t-elle ici ?

Solution H1

Racket

(define (syracuse-suivant n)
  (if (even? n)
      (quotient n 2)
      (+ (* 3 n) 1)))
(define (etapes n)
  (if (= n 1)
      0
      (+ 1 (etapes (syracuse-suivant n)))))
(define (etapes-t n [acc 0])
  (if (= n 1)
      acc
      (etapes-t (syracuse-suivant n) (+ acc 1))))
(etapes 6)     ; → 8
(etapes-t 6)   ; → 8
(etapes 27)    ; → 111

27 est célèbre : il lui faut 111 étapes, avec un détour par 9232. Quant à la terminaison, personne ne sait y répondre : l'argument ne diminue pas toujours (3n + 1 est plus grand que n), et l'affirmation « on finit toujours par tomber sur 1 » est la conjecture de Syracuse (ou de Collatz), posée en 1937, vérifiée par ordinateur sur des nombres gigantesques, et jamais démontrée. La question 3 de la méthode n'a pas toujours de réponse facile, et parfois pas de réponse connue du tout.

H2. Les nombres parfaits (niveau 3)

Un nombre est parfait s'il est égal à la somme de ses diviseurs propres, c'est-à-dire ses diviseurs strictement inférieurs à lui : 6 = 1 + 2 + 3.

Écris (somme-diviseurs-propres n) pour n ≥ 1.
Écris (parfait? n).
Teste 6, 28, 496 et 12.

Indice 1

Comme en F11, une fonction auxiliaire parcourt les candidats d = 1, 2, …, n − 1. Cette fois, fais-la terminale, avec un accumulateur qui additionne les diviseurs trouvés.

Indice 2

Le cas de base de la fonction auxiliaire : d a atteint n. Et (somme-diviseurs-propres 1) doit valoir 0.

Solution H2

Racket

(define (somme-diviseurs-propres n)
  (define (boucle d acc)
    (cond [(>= d n) acc]
          [(= (modulo n d) 0) (boucle (+ d 1) (+ acc d))]
          [else (boucle (+ d 1) acc)]))
  (boucle 1 0))
(define (parfait? n) (= (somme-diviseurs-propres n) n))
(somme-diviseurs-propres 12)   ; → 16
(parfait? 6)                   ; → #t
(parfait? 28)                  ; → #t
(parfait? 496)                 ; → #t
(parfait? 12)                  ; → #f
(parfait? 1)                   ; → #f

Ici, la récursion ne « descend » pas : c'est d qui monte vers n. Ce qui garantit la terminaison, c'est que l'écart n − d diminue à chaque appel. Les diviseurs propres de 12 font 1 + 2 + 3 + 4 + 6 = 16, plus que 12.

H3. Les nombres d'Armstrong (niveau 3)

Un nombre à k chiffres est un nombre d'Armstrong s'il est égal à la somme de ses chiffres élevés chacun à la puissance k : 153 = 1³ + 5³ + 3³. Écris (armstrong? n), en réutilisant nb-chiffres (F4) et puissance (F2), et une fonction auxiliaire (somme-puissances-chiffres n k). Teste 153, 370, 371, 407, 9474 (quatre chiffres), puis 154 et 10.

Indice

Attention au piège : k est le nombre de chiffres du nombre de départ. Si tu le recalcules à l'intérieur de la récursion, pendant que n perd ses chiffres, tu obtiens autre chose. Calcule-le une fois, et passe-le en paramètre.

Solution H3

Racket

(define (nb-chiffres n)
  (if (< n 10) 1 (+ 1 (nb-chiffres (quotient n 10)))))
(define (puissance x n)
  (if (= n 0) 1 (* x (puissance x (- n 1)))))
(define (somme-puissances-chiffres n k)
  (if (= n 0)
      0
      (+ (puissance (modulo n 10) k)
         (somme-puissances-chiffres (quotient n 10) k))))
(define (armstrong? n)
  (= n (somme-puissances-chiffres n (nb-chiffres n))))
(armstrong? 153)    ; → #t
(armstrong? 407)    ; → #t
(armstrong? 9474)   ; → #t
(armstrong? 154)    ; → #f
(armstrong? 10)     ; → #f

9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256.

H4. La méthode de Héron (niveau 3)

Pour approcher √a, on utilise la suite $u_0 = 1$ et $u_{n+1} = \frac{1}{2}\left(u_n + \frac{a}{u_n}\right)$ , qui converge vers √a (une suite pour ton cours de maths).

Écris (heron a n), qui renvoie $u_n$ . Calcule (heron 2 1), (heron 2 2) et (heron 2 3) : pourquoi des fractions ?
Écris (racine a eps [u 1]), récursive terminale, qui calcule les termes successifs jusqu'à ce que $|u^2 - a| < \varepsilon$ , puis renvoie u.

Indice 1

heron ressemble à suite-u (F8). Utilise un let pour ne calculer $u_{n-1}$ qu'une seule fois : sans lui, la fonction s'appellerait deux fois à chaque niveau, comme fibo.

Indice 2

Pour racine : si u est assez proche, on le renvoie ; sinon, on recommence avec le terme suivant à la place de u.

Solution H4

Racket

(define (heron a n)
  (if (= n 0)
      1
      (let ([u (heron a (- n 1))])
        (/ (+ u (/ a u)) 2))))
(define (racine a eps [u 1])
  (if (< (abs (- (* u u) a)) eps)
      u
      (racine a eps (/ (+ u (/ a u)) 2))))
(heron 2 1)                          ; → 3/2
(heron 2 2)                          ; → 17/12
(heron 2 3)                          ; → 577/408
(exact->inexact (heron 2 5))         ; → 1.4142135623730951
(sqrt 2)                             ; → 1.4142135623730951
(racine 2 1/1000)                    ; → 577/408
(exact->inexact (racine 2 1/1000))   ; → 1.4142156862745099

Comme $u_0 = 1$ et a = 2 sont exacts, tous les termes sont des fractions exactes : Racket calcule la suite sans aucune erreur d'arrondi. Au cinquième terme, la valeur coïncide déjà avec (sqrt 2) sur tous les chiffres d'un flottant : la convergence est très rapide.

H5. La puissance rapide (niveau 3)

On peut calculer xⁿ avec beaucoup moins de multiplications : $x^n = (x^{n/2})^2$ si n est pair, et $x^n = x \times x^{n-1}$ si n est impair. Écris (puissance-rapide x n), avec un let pour ne calculer $x^{n/2}$ qu'une fois. Combien de multiplications pour n = 1000, contre 1000 pour puissance (F2) ? Que se passe-t-il si l'on oublie le let ?

Solution H5

Racket

(define (puissance-rapide x n)
  (cond [(= n 0) 1]
        [(even? n) (let ([y (puissance-rapide x (quotient n 2))])
                     (* y y))]
        [else (* x (puissance-rapide x (- n 1)))]))
(puissance-rapide 2 10)                        ; → 1024
(puissance-rapide 5 3)                         ; → 125
(= (puissance-rapide 2 1000) (expt 2 1000))    ; → #t

Pour n = 1000, l'exposant passe par 1000, 500, 250, 125, 124, 62, 31, 30, 15, 14, 7, 6, 3, 2, 1, puis 0 : 15 multiplications au lieu de 1000. Sans le let, en écrivant (* (puissance-rapide x (quotient n 2)) (puissance-rapide x (quotient n 2))), chaque étape paire double le nombre d'appels : on monte à 1511 multiplications, pire que la version naïve. C'est le « exécuter une seule fois une expression » de la slide 26, avec un vrai enjeu. Cet algorithme (square-and-multiply) est aussi celui qu'utilise la cryptographie : RSA calcule ainsi les puissances de très grands nombres.

IDST blanc (1 h 30)

Conditions : 1 h 30, sur papier, avec la cheatsheet imprimée pour seul document, sans machine. Barème sur 20. Corrige-toi ensuite avec le corrigé, sévèrement (une parenthèse qui manque, c'est un code faux), note tes erreurs dans ton carnet, puis tape tes fonctions dans le fichier d'autocorrection (partie I) pour les vérifier. Ce sujet est une simulation construite sur le CM1 : le vrai DST peut être organisé autrement.

Exercice 1. Questions de cours (4 points)

Qu'est-ce qu'un prédicat ? Donne un prédicat prédéfini, puis écris le prédicat (negatif-ou-nul? x). (1 pt)
Quelle est la différence entre (define N (random 10)) et (define (n) (random 10)) ? (1 pt)
Quelle est la différence entre let et let* ? Donne un exemple où ils donnent des résultats différents. (1 pt)
Qu'est-ce qu'un appel terminal ? Pourquoi une fonction récursive terminale ne fait-elle pas grandir la pile d'exécution en Racket ? (1 pt)

Exercice 2. Évaluation (4 points, 0,5 par expression)

Donne la valeur affichée, ou « erreur » avec la raison.

(- 20 (* 2 3) 4)
(/ 12 8)
(quotient -7 2)
(modulo -7 2)
(and (> 3 2) (< 3 2))
(if (= 0 0.0) "a" "b")
(let* ([x 3] [y (* x x)]) (- y x))
((+ 1 2))

Exercice 3. Erreurs (3 points, 1 par code)

Pour chaque code : l'erreur survient-elle avant ou pendant l'exécution ? Quelle est sa cause ? Corrige-le.

Racket

;; code à corriger (a)
(define (moitie x) (/ x 2)

Racket

;; code à corriger (b)
(define (signe x)
  (cond [(> x 0) 1]
        [(< x 0) -1]))
(+ (signe 0) 1)

Racket

;; code à corriger (c)
(define (compte n) (if (= n 0) 0 (+ 1 (compte n-1))))

Exercice 4. Fonctions (4 points)

Écris (entre-bornes? x a b), vrai si a ≤ x ≤ b, sans if. (1 pt)
Écris (frais-port poids), le poids étant en kilogrammes : jusqu'à 1 kg compris, 5 € ; jusqu'à 5 kg compris, 8 € ; jusqu'à 20 kg compris, 15 € ; au-delà, 30 €. (1,5 pt)
Écris (aire-triangle a b c), l'aire d'un triangle de côtés a, b et c par la formule de Héron (le même Héron qu'en H4) : avec $s = \frac{a + b + c}{2}$ , l'aire vaut $\sqrt{s(s-a)(s-b)(s-c)}$ . Utilise un let pour ne calculer s qu'une fois. (1,5 pt)

Exercice 5. Récursivité (5 points)

Écris (somme-multiples-3 n), la somme des multiples de 3 compris entre 0 et n (n ≥ 0), en récursivité enveloppée. Par exemple, (somme-multiples-3 10) vaut 3 + 6 + 9 = 18. (1,5 pt)
Donne la trace de (somme-multiples-3 4). (1 pt)
Écris (somme-multiples-3-t n [acc 0]), la version récursive terminale. (1,5 pt)
Que se passe-t-il si l'on appelle ta fonction de la question 1 avec n = −1 ? Propose une correction. (1 pt)

Corrigé et barème

Exercice 1

Un prédicat est une fonction qui renvoie un booléen, #t ou #f ; par convention, son nom se termine par ?. Exemples : even?, zero?. Barème : 0,5 pour la définition et l'exemple, 0,5 pour le code (0,25 seulement avec un (if ... #t #f) inutile).

Racket

(define (negatif-ou-nul? x) (<= x 0))
(negatif-ou-nul? 0)   ; → #t
(negatif-ou-nul? 2)   ; → #f

N est une constante : (random 10) est évalué une seule fois, à la définition, et N vaut ensuite toujours la même chose. n est une fonction d'arité 0 : chaque appel (n) refait un tirage. 0,5 par idée.
let calcule toutes les expressions avant de lier les noms, donc une liaison ne voit pas les autres ; let* lie les noms un par un. 0,5 pour l'explication, 0,5 pour un exemple juste, comme celui-ci :

Racket

(define x 10)
(let ([x 2] [y x]) y)    ; → 10
(let* ([x 2] [y x]) y)   ; → 2

Un appel terminal est un appel dont le résultat est directement celui de la fonction : il ne reste rien à faire après lui. Racket réutilise alors le cadre de pile de l'appel en cours au lieu d'en empiler un nouveau (élimination des appels terminaux), donc la mémoire reste constante. 0,5 + 0,5.

Exercice 2

Racket

(- 20 (* 2 3) 4)                     ; → 10
(/ 12 8)                             ; → 3/2
(quotient -7 2)                      ; → -3
(modulo -7 2)                        ; → 1
(and (> 3 2) (< 3 2))                ; → #f
(if (= 0 0.0) "a" "b")               ; → "a"
(let* ([x 3] [y (* x x)]) (- y x))   ; → 6
((+ 1 2))                            ; → erreur : application: not a procedure

0,5 par réponse exacte. Répondre 1.5 au lieu de 3/2 vaut 0 : l'exactitude est justement ce qui est testé.

Exercice 3 (0,5 pour le diagnostic, moment et cause ; 0,5 pour la correction)

a) Avant l'exécution, à la lecture : il manque la parenthèse qui ferme le define.
b) Pendant l'exécution : (signe 0) ne renvoie rien, car aucune ligne du cond n'est vraie, et + échoue avec contract violation. Il faut une ligne [else 0].
c) Avant l'exécution : n-1: unbound identifier. Il faut (- n 1).

Racket

(define (moitie x) (/ x 2))
(define (signe x)
  (cond [(> x 0) 1]
        [(< x 0) -1]
        [else 0]))
(define (compte n) (if (= n 0) 0 (+ 1 (compte (- n 1)))))
(moitie 7)         ; → 7/2
(+ (signe 0) 1)    ; → 1
(compte 4)         ; → 4

Exercice 4

Racket

(define (entre-bornes? x a b) (<= a x b))
(define (frais-port poids)
  (cond [(<= poids 1) 5]
        [(<= poids 5) 8]
        [(<= poids 20) 15]
        [else 30]))
(define (aire-triangle a b c)
  (let ([s (/ (+ a b c) 2)])
    (sqrt (* s (- s a) (- s b) (- s c)))))
(entre-bornes? 5 1 10)    ; → #t
(entre-bornes? 11 1 10)   ; → #f
(frais-port 1)            ; → 5
(frais-port 5)            ; → 8
(frais-port 20)           ; → 15
(frais-port 25)           ; → 30
(aire-triangle 3 4 5)     ; → 6

Barème : 1) 1 point, 0,5 avec un if ; 2) 1,5 point, dont 0,5 pour l'ordre des conditions et 0,5 pour les frontières (<=, puisque 1 kg compris coûte 5 €) ; 3) 1,5 point, dont 0,5 pour le let.

Exercice 5

Racket

(define (somme-multiples-3 n)
  (cond [(= n 0) 0]
        [(= (modulo n 3) 0) (+ n (somme-multiples-3 (- n 1)))]
        [else (somme-multiples-3 (- n 1))]))
(define (somme-multiples-3-t n [acc 0])
  (cond [(= n 0) acc]
        [(= (modulo n 3) 0) (somme-multiples-3-t (- n 1) (+ acc n))]
        [else (somme-multiples-3-t (- n 1) acc)]))
(somme-multiples-3 10)     ; → 18
(somme-multiples-3-t 10)   ; → 18
(somme-multiples-3 30)     ; → 165

La trace de la question 2 :

(somme-multiples-3 4)
(somme-multiples-3 3)        ; 4 n'est pas un multiple de 3
(+ 3 (somme-multiples-3 2))
(+ 3 (somme-multiples-3 1))
(+ 3 (somme-multiples-3 0))
(+ 3 0)
3

Question 4 : avec n = −1, la condition (= n 0) n'est jamais vraie. n passe par −2, −3, −4… sans fin, et chaque multiple de 3 rencontré laisse une addition en attente : dans DrRacket, la mémoire finit par s'épuiser. Correction : le cas de base (<= n 0), qui renvoie 0.

Barème : 1) 1,5 point (cas de base 0,5, test de divisibilité 0,5, appel récursif 0,5) ; 2) 1 point, 0,5 si une étape manque ; 3) 1,5 point (accumulateur et valeur de départ 0,5, cas de base qui renvoie acc 0,5, tous les appels terminaux 0,5) ; 4) 1 point (explication 0,5, correction 0,5). Toute autre solution juste compte, par exemple une version qui descend de 3 en 3. Si l'énoncé du vrai DST ne précise pas le style d'accumulateur, les deux (valeur par défaut ou fonction auxiliaire) devraient être acceptés : à confirmer avec ton enseignant (partie 14 du cours).

Et ensuite. Refais ce sujet une semaine plus tard, sans regarder le corrigé, et compare tes deux copies. Relis ton carnet d'erreurs avant le vrai DST.