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 ;(trace true)
  60
  61 (setq L '(3 7 + 4 2 + *))
  62 (setq M '(4 3 7 + * 2 -))
  63 (define (calculExp P L)
  64   (cond
  65     ((null? L) P)
  66     ((= (first L) '+) (calculExp (cons (+ (first P) (P 1)) (rest (rest P))) (rest L)))
  67     ((= (first L) '-) (calculExp (cons (- (P 1) (first P)) (rest (rest P))) (rest L)))
  68     ((= (first L) '*) (calculExp (cons (* (first P) (P 1)) (rest (rest P))) (rest L)))
  69     ;FIXME: test for divide by zero
  70     ((= (first L) '/) (calculExp (cons (/ (P 1) (first P)) (rest (rest P))) (rest L)))
  71     ((calculExp (cons (first L) P) (rest L)))))
  72 (println "calculExp")
  73 (println (calculExp '() L))
  74 ;(trace true)
  75 (println (calculExp '() M))
  76
  77 ;(trace nil)
  78
  79 (exit)