exercices/arithmetic.lsp

   1 #!/usr/bin/env newlisp
   2
   3 ;O(N)
   4 (define (Puissance1 P N)
   5   (cond
   6     ((= N 0) 1)
   7     ((= N 1) P)
   8     ((< N 0) (div 1 (Puissance1 P (- N))))
   9     ((* P (Puissance1 P (- N 1))))))
  10 (println "Puissance1")
  11 (println (Puissance1 5 5))
  12 (println (Puissance1 2 12))
  13
  14 ;(trace true)
  15
  16 ;O(log N)
  17 (define (Puissance2 P N)
  18   (cond
  19     ((= N 1) P)
  20     ((= N 2) (* P P))
  21     ((> N 2)
  22      (cond
  23        ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
  24        ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
  25 (println "Puissance2")
  26 (println (Puissance2 5 5))
  27 (println (Puissance2 2 12))
  28
  29 ;(trace nil)
  30
  31 ; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
  32 (define (pgcd N P)
  33   (cond
  34     ((< N P) (pgcd P N))
  35     ((= N P) N)
  36     ((= P 0) N)
  37     ((pgcd (- N P) P))))
  38 (println "PGCD")
  39 (println (pgcd 12 4))
  40 (println (pgcd 25 5))
  41 (println (pgcd 21 7))
  42
  43 ;(trace true)
  44
  45 ; https://fr.wikipedia.org/wiki/Coefficient_binomial
  46 ; relation de pascal commenté
  47 (define (comb N P)
  48   (cond
  49     ((= P 0) 1)
  50     ((= N P) 1)
  51     ;((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
  52     ((/ (* N (comb (- N 1) (- P 1))) P))))
  53 (println "comb")
  54 (println (comb 5 4))
  55 (println (comb 60 4))
  56 (println "(comb 12 8) = "(comb 12 8))
  57
  58 ;(trace nil)
  59
  60 (setq L '(3 7 + 4 2 + *))
  61 (setq P '())
  62 (define (calculExp P L)
  63   (cond
  64     ((null? L) 0)
  65     ((= (first L) '+) (+ (first P) (calculExp (rest P) (rest L))))
  66     ((= (first L) '-) (- (first P) (calculExp (rest P) (rest L))))
  67     ((= (first L) '*) (* (first P) (calculExp (rest P) (rest L))))
  68     ;FIXME: test for divide by zero
  69     ((= (first L) '/) (/ (first P) (calculExp (rest P) (rest L))))
  70     ((cons (first L) (calculExp P (rest L))))))
  71 ;(println (calculExp P L))
  72
  73 (exit)