From 7c69bee537f3343712cfa6b35b6433c9f8cb3459 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 7 May 2017 15:52:07 +0200 Subject: [PATCH] Fix the recursive optimized power calculation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit And small cleanups in the code Signed-off-by: Jérôme Benoit --- exercices/arithmetic.lsp | 16 ++++++++++------ exercices/lists.lsp | 2 +- 2 files changed, 11 insertions(+), 7 deletions(-) diff --git a/exercices/arithmetic.lsp b/exercices/arithmetic.lsp index a3f27ce..d3b6cef 100755 --- 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) diff --git a/exercices/lists.lsp b/exercices/lists.lsp index 6bf12a5..35590da 100755 --- a/exercices/lists.lsp +++ b/exercices/lists.lsp @@ -169,7 +169,7 @@ ((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)) -- 2.34.1