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 (setq N '(10 10 5 / +))
  64 (define (calculExp P L)
  65   (cond
  66     ((null? L) (first P))
  67     ; all these conditions could probably be simplified
  68     ((= (first L) '+) (calculExp (cons (+ (P 1) (first P)) (rest (rest P))) (rest L)))
  69     ((= (first L) '-) (calculExp (cons (- (P 1) (first P)) (rest (rest P))) (rest L)))
  70     ((= (first L) '*) (calculExp (cons (* (P 1) (first P)) (rest (rest P))) (rest L)))
  71     ;FIXME: test for divide by zero
  72     ((= (first L) '/) (calculExp (cons (/ (P 1) (first P)) (rest (rest P))) (rest L)))
  73     ((number? (first L)) (calculExp (cons (first L) P) (rest L)))))
  74 (println "calculExp")
  75 (println (calculExp '() L))
  76 ;(trace true)
  77 (println (calculExp '() M))
  78 (println (calculExp '() N))
  79
  80 ;(trace nil)
  81
  82 (setq Q '(+ (* x 0) (* 10 (+ y 0))))
  83 (define (algsimplificator L)
  84   (cond
  85     ((null? L) '())
  86     ((= (first L) ) (rest L))
  87
  88     ))
  89 (println "algsimplificator")
  90 ;(println algsimplificator(Q))
  91
  92 (define (fibonacci N)
  93   (cond
  94     ((= N 0) 0)
  95     ((= N 1) 1)
  96     ((> N 1) (+ (fibonacci (- N 1)) (fibonacci (- N 2))))))
  97 (println "fibonacci")
  98 ;(println (fibonacci 21))
  99 ;(println (fibonacci 14))
 100 (println (fibonacci 20))
 101 (println (time (fibonacci 20)))
 102
 103 ;(trace true)
 104
 105 (define (fibo:fibo n)
 106   (if (not fibo:mem) (set 'fibo:mem '(0 1)))
 107   (dotimes (i (- n 1))
 108     (push (+ (fibo:mem -1) (fibo:mem -2)) fibo:mem -1))
 109   (last fibo:mem))
 110 (println "fibo")
 111 (println (fibo 20))
 112 (println (time (fibo 20)))
 113
 114 ;(trace nil)
 115
 116 (exit)