Fix the recursive optimized power calculation

[TD_LISP.git] / exercices / arithmetic.lsp

diff --git a/exercices/arithmetic.lsp b/exercices/arithmetic.lsp
index a3f27ce90d7c99e6e7ca71575b0b7a16d336c6b0..d3b6cefc06903923ebcb5723aefceaa9da0b56ff 100755 (executable)
--- a/exercices/arithmetic.lsp
+++ b/exercices/arithmetic.lsp
@@ -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)
 
@@ -41,15 +43,17 @@
 ;(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)