From: Jérôme Benoit Date: Sun, 7 May 2017 13:52:07 +0000 (+0200) Subject: Fix the recursive optimized power calculation X-Git-Url: https://git.piment-noir.org/?p=TD_LISP.git;a=commitdiff_plain;h=7c69bee537f3343712cfa6b35b6433c9f8cb3459 Fix the recursive optimized power calculation And small cleanups in the code Signed-off-by: Jérôme Benoit --- 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))