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