Fix the recursive optimized power calculation
authorJérôme Benoit <jerome.benoit@piment-noir.org>
Sun, 7 May 2017 13:52:07 +0000 (15:52 +0200)
committerJérôme Benoit <jerome.benoit@piment-noir.org>
Sun, 7 May 2017 13:52:07 +0000 (15:52 +0200)
And small cleanups in the code

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

index a3f27ce90d7c99e6e7ca71575b0b7a16d336c6b0..d3b6cefc06903923ebcb5723aefceaa9da0b56ff 100755 (executable)
@@ -9,20 +9,22 @@
     ((* 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 0) 1)
     ((= N 1) P)
-    ((> N 1)
+    ((= N 2) (* P P))
+    ((> N 2)
      (cond
        ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
-       ((* P (Puissance2 (Puissance2 P 2) (/ (- 1 N) 2))))))))
+       ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
 (println "Puissance2")
-;(println (Puissance2 5 5))
+(println (Puissance2 5 5))
+(println (Puissance2 2 12))
 
 ;(trace nil)
 
 ;(trace true)
 
 ; https://fr.wikipedia.org/wiki/Coefficient_binomial
-; relation de pascal
+; relation de pascal commenté
 (define (comb N P) 
   (cond
     ((= P 0) 1)
     ((= N P) 1)
-    ((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
+    ;((+ (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)
 
index 6bf12a5e7a1e1803016fd4b6bc1e3d03b33b8c1a..35590dada335ff070e4a9546859cdafbe8777b1c 100755 (executable)
     ((append 
        ;the pivot is the first element of the list
        (qsort (list< (first L) (rest L))) 
-       (cons (first L) '()) 
+       (list (first L))
        (qsort (list>= (first L) (rest L)))))))
 (println "qsort")
 (println (qsort C))