;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-advanced-reader.ss" "lang")((modname exam-mai-2017) (read-case-sensitive #t) (teachpacks ((lib "valrose.rkt" "installed-teachpacks"))) (htdp-settings #(#t write repeating-decimal #t #t none #f ((lib "valrose.rkt" "installed-teachpacks")) #f))) ;;; examen terminal ;;; Fac. Sciences de Nice, L1-Info, Mai 2017 ; Q1. (define (foo x y) (cond ((= x 1) y) ((= (modulo x 2) 0) (cons x (foo (/ x 2) y))) (else (foo (+ (* 3 x) 1) (cons x y))))) (check-expect (foo 12 '()) '(12 6 10 16 8 4 2 5 3)) ; vérification avec trace : (require racket/trace) ; mais on doit savoir vérifier à la main ! (trace foo) (foo 12 '()) (untrace foo) ; ----------------------------------------------------------------------- ; Q2a ; Le résultat de (ppdiv n) est un diviseur PREMIER de n puisque sinon ; il serait lui-même divisible par un entier k qui serait un diviseur de n ; encore plus petit, ce qui est impossible puisque ppdiv renvoie le "plus ; petit" diviseur de n. ; Q2b (define (ppdiv n) ; le plus petit diviseur >= 2 de l'entier n (local [(define (iter k) ; on boucle sur k comme en Python (if (zero? (modulo n k)) k (iter (+ k 1))))] ; appel récursif terminal <==> itération ! (iter 2))) (check-expect (list (ppdiv 15) (ppdiv 17)) '(3 17)) ; Q2c ; n >= 2, retourne itérativement la liste L croissante des facteurs premiers DISTINCTS de n (define (facteurs-premiers n) (local [(define (iter n acc) (if (= n 1) (reverse acc) ; croissante... (local [(define d (ppdiv n))] ; le plus petit facteur premier de n (iter (/ n d) (if (member d acc) acc (cons d acc))))))] ; on a dit DISTINCTS ! (iter n empty))) (check-expect (facteurs-premiers (* 2 2 2 5 11 11)) '(2 5 11)) ; Q2d (define (exposant p n) ; pourquoi un "iter" inutile chez certains ?... (if (zero? (modulo n p)) (+ 1 (exposant p (quotient n p))) ; keep it simple ! 0)) (check-expect (exposant 2 40) 3) ; Q2e ; il est important de comprendre ce style de "combinaisons" de primitives ; au lieu de coder lourdement... (idem en Python). ; "Pour chaque facteur premier, je fais..." : (define (factorise n) ; mais ok pour une autre solution plus lourde (map (lambda (p) (list p (exposant p n))) (facteurs-premiers n))) (check-expect (factorise (* 2 2 2 5 11 11)) '((2 3) (5 1) (11 2))) ; ----------------------------------------------------------------------- ; Q3a - QUESTION DE COURS ! (define (insertion x LT) ; LT triée en décroissant. Voir cours 6 page 19 (cond ((empty? LT) (list x)) ((> x (first LT)) (cons x LT)) (else (cons (first LT) (insertion x (rest LT)))))) (check-expect (insertion 10 '(22 19 15 8 6 1)) '(22 19 15 10 8 6 1)) ; Q3b (define (tri-ins L) ; recursive enveloppee. Voir cours 6 page 20 (if (empty? L) L (insertion (first L) (tri-ins (rest L))))) (check-expect (tri-ins '(15 1 8 22 6 19)) '(22 19 15 8 6 1)) ; Q3c (define (tri-ins-it L) (local [(define (iter L acc) (if (empty? L) acc ; <-- pas de reverse ! (iter (rest L) (insertion (first L) acc))))] (iter L empty))) (check-expect (tri-ins-it '(15 1 8 22 6 19)) '(22 19 15 8 6 1)) ; Q3d ; REP : OUI (la pile occupe un espace lineaire et ne modifie pas cette complexite) ; Q3e ; REP : O(n^2), vu en cours. ; Q3f (define (tri-ins-os L) (reduce insertion empty L)) ; reduce attend une fonction *binaire* (check-expect (tri-ins-os '(15 1 8 22 6 19)) '(22 19 15 8 6 1)) ; -------------------------------------------------------------------- ; Q4 ; REP : 30000 Hz d'après le théorème de Nyquist (cours audio page 5) ; -------------------------------------------------------------------- ; Q5a (define FOND (place-image (circle 20 'solid "yellow") 500 50 ; le ballon est "en haut dans le ciel"... (above (rectangle 600 300 'solid "lightblue") (rectangle 600 300 'solid "wheat")))) ; et pas "sand" l'énoncé se trompe ; Q5b (define-struct ballon (x y r color v)) ; Q5c (define (random-ballon) (make-ballon (random 600) (+ 300 (random 301)) 4 (list-ref '("blue" "white" "red") (random 3)) ; comme en Python... (+ 3 (* 5 (random))))) ; Q5d (define INIT (build-list 30 (lambda (i) (random-ballon)))) ; Q5e (define (dessiner L) (if (empty? L) FOND (local [(match-define (ballon x y r color v) (first L))] (place-image (circle r 'solid color) x y (dessiner (rest L)))))) ; Q5f (define (suivant L) (if (empty? L) L (local [(match-define (ballon x y r color v) (first L))] (cons (if (< r 30) (make-ballon x y (+ r #i0.1) color v) (make-ballon x (- y v) r color v)) (suivant (rest L)))))) (define (suivant_ L) ; ou avec map... (map (lambda (b) ; mouvement d'un seul ballon b (tous les ballons restent vivants) (local [(match-define (ballon x y r color v) b)] (if (< r 30) (make-ballon x y (+ r #i0.1) color v) (make-ballon x (- y v) r color v)))) L)) ; Q5g (define (final? L) ; ou toute solution plus lourde (andmap (lambda (b) (< (ballon-y b) -32)) L)) ; pas grave pour le -32, ok pour 0... ; ****** tout ce qui suit est hors-sujet ************************************ (define (last-scene L) ; HORS-SUJET ! (place-image (text "\u03bb" 32 "black") 500 50 ; la lettre lambda (place-image (text "Sous les claviers, la plage !" 46 "black") 300 450 FOND))) (void (big-bang INIT ; void pour ne pas voir le resultat de big-bang (on-tick suivant_) (on-draw dessiner) (stop-when final? last-scene) ; last-scene HORS-SUJET ! (name "Exam Mai 2017")) )