* Fix aplatir function

 * Implement filtre with recursion
 * Fix C n p function

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>

diff --git a/exercices/arithmetic.lsp b/exercices/arithmetic.lsp
index 85f3f0145e446732be437de2f02cb280541aa8f9..a3f27ce90d7c99e6e7ca71575b0b7a16d336c6b0 100755 (executable)
--- a/exercices/arithmetic.lsp
+++ b/exercices/arithmetic.lsp
@@ -1,12 +1,30 @@
 #!/usr/bin/env newlisp
 
 #!/usr/bin/env newlisp
 

-(define (Puissance P N)
+;O(N)
+(define (Puissance1 P N)

   (cond
     ((= N 0) 1)
     ((= N 1) P)
   (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))
+
+;(trace true)
+
+;O(log N)
+(define (Puissance2 P N)
+  (cond
+    ((= N 0) 1)
+    ((= N 1) P)
+    ((> N 1)
+     (cond
+       ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
+       ((* P (Puissance2 (Puissance2 P 2) (/ (- 1 N) 2))))))))
+(println "Puissance2")
+;(println (Puissance2 5 5))
+
+;(trace nil)

 
 ; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
 (define (pgcd N P) 
 
 ; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
 (define (pgcd N P) 


@@ -15,16 +33,37 @@
     ((= N P) N)
     ((= P 0) N)
     ((pgcd (- N P) P))))
     ((= N P) N)
     ((= P 0) N)
     ((pgcd (- N P) P))))

+(println "PGCD")

 (println (pgcd 12 4))
 (println (pgcd 25 5))
 (println (pgcd 21 7))
 
 (println (pgcd 12 4))
 (println (pgcd 25 5))
 (println (pgcd 21 7))
 

+;(trace true)
+

 ; https://fr.wikipedia.org/wiki/Coefficient_binomial
 ; https://fr.wikipedia.org/wiki/Coefficient_binomial

+; relation de pascal

 (define (comb N P) 
   (cond
     ((= P 0) 1)
     ((= N P) 1)
 (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))))))
+(println "comb")
+(println (comb 5 4))
+(println (comb 60 4))
+
+;(trace nil)
+
+(setq L '(3 7 + 4 2 + *))
+(setq P '())
+(define (calculExp P L)
+  (cond
+    ((null? L) 0)
+    ((= (first L) '+) (+ (first P) (calculExp (rest P) (rest L)))) 
+    ((= (first L) '-) (- (first P) (calculExp (rest P) (rest L))))
+    ((= (first L) '*) (* (first P) (calculExp (rest P) (rest L))))
+    ;FIXME: test for divide by zero
+    ((= (first L) '/) (/ (first P) (calculExp (rest P) (rest L))))
+    ((cons (first L) (calculExp P (rest L))))))    
+;(println (calculExp P L))

 
 (exit)
 
 (exit)

diff --git a/exercices/lists.lsp b/exercices/lists.lsp
index e97d74796833b3869973bd155c33bb1b69a650d4..6bf12a5e7a1e1803016fd4b6bc1e3d03b33b8c1a 100755 (executable)
--- a/exercices/lists.lsp
+++ b/exercices/lists.lsp
@@ -118,11 +118,11 @@
 
 (define (aplatir L) 
   (cond
 
 (define (aplatir L) 
   (cond

-    ((null? L) nil)
-    ((atom? L) (list L)) ;FIXME: the "casting" is not working properly
+    ((null? L) '())
+    ((atom? L) (list L))

     ((append (aplatir (first L)) (aplatir (rest L))))))
 (println "aplatir/flat")
     ((append (aplatir (first L)) (aplatir (rest L))))))
 (println "aplatir/flat")

-;(println (aplatir T))
+(println (aplatir T))

 (println (flat T))
 
 ;(trace nil)
 (println (flat T))
 
 ;(trace nil)


@@ -202,5 +202,24 @@
     ((and (inclu L1 L2) (inclu L2 L1) true))))
 (println "filtre")
 (println (filtre L1 L2 ?))
     ((and (inclu L1 L2) (inclu L2 L1) true))))
 (println "filtre")
 (println (filtre L1 L2 ?))

+(println (filtre L M ?))
+
+;algorithm written on the board
+(define (filtrerec L1 L2 C)
+  ;FIXME: use the function argument C
+  (cond
+    ((null? L1)
+      (cond
+        ((null? L2) true)
+        ((= '? (first L2)) (filtrerec L1 (rest L2)))
+        (nil)))
+    ((null? L2) (filtrerec L2 L1))
+    ((= '? (first L1)) (filtrerec (rest L1) L2))
+    ((= '? (first L2)) (filtrerec L1 (rest L2)))
+    ((= (first L1) (first L2)) (filtrerec (rest L1) (rest L2)) )
+    (nil)))
+(println "filtrerec")
+(println (filtrerec L1 L2 ?))
+(println (filtrerec L M ?))

 
 (exit)
 
 (exit)