;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Exercice 1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; 1. (decomposition 13 2) => (1 1 0 1) ;; 2. (decomposition 11 3) => (1 0 2) ;; 3. decomposition retourne la liste des chiffres de l'entier "entier" ;; quand il est écrit dans la basse "base" ;; 4. (defun decomposition (entier base) (do ((quotient (floor entier base) (floor quotient base)) (chiffres (list (mod entier base)) (cons (mod quotient base) chiffres))) ((zerop quotient) chiffres))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Exercice 2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun serie (epsilon) ; version loop (loop for signe = 1 then (- signe) for denominateur from 1 by 2 for terme = (/ denominateur) then (/ denominateur) sum (* signe terme) until (< terme epsilon))) (defun serie (epsilon) ; version do (do* ((signe 1 (- signe)) (denominateur 1 (+ 2 denominateur)) (terme (/ denominateur) (/ denominateur)) (somme (* signe terme) (+ somme (* signe terme)))) ((< terme epsilon) somme))) (defun my-pi (&optional (epsilon 1d-2)) (coerce (* 4 (serie (/ epsilon 10))) 'float)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Exercice 3 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; 1. (defun injectivep (a) ;; lisp style (= (length a) (length (remove-duplicates a)))) ;; 2. (defun internep (a) (every (lambda (x) (< -1 x (length a))) a)) ;; 3. (defun permutationp (a) (and (internep a) (injectivep a))) ;; 4. (defun inv-a (a) ;; dotimes (assert (permutationp a)) (let* ((n (length a)) (inv (make-array (length a)))) (dotimes (i n inv) (setf (aref inv i) (count-if (lambda (x) (> (aref a i) x)) a :start (1+ i)))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Autres versions utilisant différents types de boucles ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun injectivep (p) ;; loop (loop with n = (length p) for i from 0 below n do (loop for j from (1+ i) below n when (= (aref p i) (aref p j)) do (return-from injectivep nil)) finally (return t))) (defun injectivep (p) ;; do (let ((n (length p))) (dotimes (i n t) (do ((j (1+ i) (1+ j))) ((>= j n)) (when (= (aref p i) (aref p j)) (return-from injectivep nil)))))) (defun internep (a) ;; loop (loop with m = (1- (length a)) for v across a unless (<= 0 v m) do (return nil) finally (return t))) (defun internep (a) ;; do (let* ((n (length a)) (m (1- n))) (dotimes (i n t) (unless (<= 0 (aref a i) m) (return nil))))) (defun inv-a (a) ;; loop (assert (permutationp a)) (loop with n = (length a) with inv = (make-array n) for i from 0 below n do (loop for j from (1+ i) below n when (> (aref a i) (aref a j)) do (incf (aref inv i))) finally (return inv))) (defun inv-a (a) ;; dotimes + do (assert (permutationp a)) (let* ((n (length a)) (inv (make-array n))) (dotimes (i n inv) (do ((j (1+ i) (1+ j))) ((>= j n)) (when (> (aref a i) (aref a j)) (incf (aref inv i))))))) (defun inv-a (a) ;; map (assert (permutationp a)) (let ((i 0)) (map 'vector (lambda (x) (incf i) (count-if (lambda (y) (> x y)) a :start i)) a)))