X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=exercices%2Farithmetic.lsp;h=f020099e8ea8be02431afe00dcc9d298375155c3;hb=25450b8430ab9b9f699580f0bef9ab0c1f65c5b2;hp=85f3f0145e446732be437de2f02cb280541aa8f9;hpb=ada8f303fa63f62209dddeab6f4618f5b73a66b7;p=TD_LISP.git

diff --git a/exercices/arithmetic.lsp b/exercices/arithmetic.lsp
index 85f3f01..f020099 100755
--- a/exercices/arithmetic.lsp
+++ b/exercices/arithmetic.lsp
@@ -1,12 +1,32 @@
 #!/usr/bin/env newlisp
 
-(define (Puissance P N)
+;O(N)
+(define (Puissance1 P N)
   (cond
     ((= N 0) 1)
     ((= N 1) P)
-    ((< N 0) (div 1 (Puissance P (- N))))
-    ((* P (Puissance P (- N 1))))))
-(println (Puissance 5 5))
+    ((< N 0) (div 1 (Puissance1 P (- N))))
+    ((* P (Puissance1 P (- N 1))))))
+(println "Puissance1")
+(println (Puissance1 5 5))
+(println (Puissance1 2 12))
+
+;(trace true)
+
+;O(log N)
+(define (Puissance2 P N)
+  (cond
+    ((= N 1) P)
+    ((= N 2) (* P P))
+    ((> N 2)
+     (cond
+       ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
+       ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
+(println "Puissance2")
+(println (Puissance2 5 5))
+(println (Puissance2 2 12))
+
+;(trace nil)
 
 ; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
 (define (pgcd N P) 
@@ -15,16 +35,82 @@
     ((= N P) N)
     ((= P 0) N)
     ((pgcd (- N P) P))))
+(println "PGCD")
 (println (pgcd 12 4))
 (println (pgcd 25 5))
 (println (pgcd 21 7))
 
+;(trace true)
+
 ; https://fr.wikipedia.org/wiki/Coefficient_binomial
+; relation de pascal commenté
 (define (comb N P) 
   (cond
     ((= P 0) 1)
     ((= N P) 1)
-    ((+ (comb (- 1 N) P) (comb (- 1 N) (- 1 P))))))
-;(println (comb 5 4))
+    ;((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
+    ((/ (* N (comb (- N 1) (- P 1))) P))))
+(println "comb")
+(println (comb 5 4))
+(println (comb 60 4))
+(println "(comb 12 8) = "(comb 12 8))
+
+;(trace nil)
+;(trace true)
+
+(setq L '(3 7 + 4 2 + *))
+(setq M '(4 3 7 + * 2 -))
+(setq N '(10 10 5 / +))
+(define (calculExp P L)
+  (cond
+    ((null? L) (first P))
+    ; all these conditions could probably be simplified
+    ((= (first L) '+) (calculExp (cons (+ (P 1) (first P)) (rest (rest P))) (rest L)))
+    ((= (first L) '-) (calculExp (cons (- (P 1) (first P)) (rest (rest P))) (rest L)))
+    ((= (first L) '*) (calculExp (cons (* (P 1) (first P)) (rest (rest P))) (rest L)))
+    ;FIXME: test for divide by zero
+    ((= (first L) '/) (calculExp (cons (/ (P 1) (first P)) (rest (rest P))) (rest L)))
+    ((number? (first L)) (calculExp (cons (first L) P) (rest L)))))    
+(println "calculExp")
+(println (calculExp '() L))
+;(trace true)
+(println (calculExp '() M))
+(println (calculExp '() N))
+
+;(trace nil)
+
+(setq Q '(+ (* x 0) (* 10 (+ y 0))))
+(define (algsimplificator L)
+  (cond
+    ((null? L) '())
+    ((= (first L) ) (rest L))
+
+    ))
+(println "algsimplificator")
+;(println algsimplificator(Q))
+
+(define (fibonacci N)
+  (cond
+    ((= N 0) 0)
+    ((= N 1) 1)
+    ((> N 1) (+ (fibonacci (- N 1)) (fibonacci (- N 2))))))
+(println "fibonacci")
+;(println (fibonacci 21))
+;(println (fibonacci 14))
+(println (fibonacci 20))
+(println (time (fibonacci 20)))
+
+;(trace true)
+
+(define (fibo:fibo n)
+  (if (not fibo:mem) (set 'fibo:mem '(0 1)))
+  (dotimes (i (- n 1))
+    (push (+ (fibo:mem -1) (fibo:mem -2)) fibo:mem -1))
+  (last fibo:mem))
+(println "fibo")
+(println (fibo 20))
+(println (time (fibo 20)))
+
+;(trace nil)
 
 (exit)