;; 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-pf1-juin-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)))
;;; exam Scheme Juin 2017, the last one, bye-bye and good luck !

;;; 1. Styles Impératif et Fonctionnel

; a)
; La programmation impérative procède par exécution séquentielle d'instructions et mutations des données.
; La programmation fonctionnelle n'opère pas de mutations, mais des transformations de données via des
; fonctions récursives.

; b)
; Oui, en Scheme la récursivité TERMINALE est traitée avec la même efficacité qu'une ITERATION (elle ne
; nécessite pas d'espace de pile pour s'exécuter). Exemple du cours, le pgcd des entiers naturels a et b :
(define (pgcd a b)
  (if (= b 0) a (pgcd b (modulo a b))))     ; <==> while b > 0 : (a,b) = (b, a % b)    en Python

;;; 2. Exécution d'une Fonction Récursive
;;; Le même exercice a été posé à la première session...

(define (foo x L)
  (cond ((= x 1) L)
        ((= (modulo x 2) 0) (cons x (foo (/ x 2) L)))
        (else (foo (+ (* 3 x) 1) (cons x L)))))

(check-expect (foo 12 empty) '(12 6 10 16 8 4 2 5 3))   ; <-- la réponse

;;; 3. Programmation sur les Nombres et les Listes

; a)

(define (suppr-mult k L)        ; à l'ordre sup !
  (filter (lambda (x) (not (zero? (modulo x k)))) L))

(check-expect (suppr-mult 3 '(4 6 2 1 9 12)) '(4 2 1))

(define (suppr-mult-rec k L)    ; récurrence enveloppée usuelle
  (cond ((empty? L) L)
        ((zero? (modulo (first L) k)) (suppr-mult-rec k (rest L)))
        (else (cons (first L) (suppr-mult-rec k (rest L))))))

(check-expect (suppr-mult-rec 3 '(4 6 2 1 9 12)) '(4 2 1))

; b)

(define (diviseurs n)        ; à l'ordre sup !
  (filter (lambda (k) (zero? (modulo n k))) (range 2 (+ n 1) 1)))   ; le range est un peu cher...

(check-expect (diviseurs 42) '(2 3 6 7 14 21 42))
(check-expect (diviseurs 19) '(19))    ; 19 est donc premier

(define (diviseurs-rec n)    ; question de cours, itération (non optimisée)...
  (local [(define (iter k acc)
            (cond ((> k n) (reverse acc))
                  ((zero? (modulo n k)) (iter (+ k 1) (cons k acc)))
                  (else (iter (+ k 1) acc))))]
    (iter 2 empty)))

(check-expect (diviseurs-rec 42) '(2 3 6 7 14 21 42))
(check-expect (diviseurs-rec 19) '(19))    ; 19 est donc premier

; c)

(define (crible L)        ; crible : on supprime tous les nombres qui sont des multiples (vu en TP)
  (if (empty? L)
      L
      (cons (first L) (crible (suppr-mult (first L) (rest L))))))

(check-expect (crible '(2 3 6 7 14 21 42)) '(2 3 7))   ; on élimine les multiples de 2,3,7

; d)

(define (diviseurs-premiers n)
  (crible (diviseurs n)))

(check-expect (diviseurs-premiers 4840) '(2 5 11))

; e)

(define (phi n)
  (* n (apply * (map (lambda (p) (- 1 (/ 1 p))) (diviseurs-premiers n)))))

(check-expect (phi 12) 4)       

;;; 4. Recherche Séquentielle dans une Liste Non Triée

; a)

(define (compte-triche L x)     ; ordre sup !
  (length (filter (lambda (e) (equal? e x)) L)))

(check-expect (compte-triche '(a b b a b c) 'b) 3)
(check-expect (compte-triche '(a b b a b c) 'd) 0)

(define (compte L x)            ; récurrence classique
  (cond ((empty? L) 0)
        ((equal? (first L) x) (+ 1 (compte (rest L) x)))
        (else (compte (rest L) x))))

(check-expect (compte '(a b b a b c) 'b) 3)
(check-expect (compte '(a b b a b c) 'd) 0)

; b)

(define (coupe L x)      ; itération
  (local [(define (iter L acc)   ; je cherche x et j'ai déjà parcouru acc
            (cond ((empty? L) #f)
                  ((equal? (first L) x) (list (reverse acc) L))     ; je coupe !
                  (else (iter (rest L) (cons (first L) acc)))))]
    (iter L empty)))

(check-expect (coupe '(le gros chien qui aboie) 'qui) '((le gros chien) (qui aboie)))
(check-expect (coupe '(le gros chien qui aboie) 'que) #f)

; NB : une récurrence enveloppée est un peu plus ennuyeuse à programmer...


;;; 5. Recherche Dichotomique dans un Intervalle Réel
;;; La technique de dichotomie ("couper en deux") a été illustrée plusieurs fois, en Python et Scheme.
;;; Elle est VITALE en programmation !

(define (une-racine f a b)               ; f continue sur [a,b] avec f(a) < 0 < f(b)
  (local [(define m (/ (+ a b) 2))]
    (if (< (- b a) #i0.001)
        m
        (local [(define y (f m))]        ; pour ne pas calculer f(m) plusieurs fois
          (cond ((> y 0) (une-racine f a m))     ; algorithme itératif !
                ((< y 0) (une-racine f m b))
                (else m))))))

(check-within (une-racine (lambda (x) (- (* x x) 2)) #i0 #i2) (sqrt 2) #i0.001)   ; j'attends (sqrt 2)