ieri mi sono messo a dare un'occhiata al lisp (quanto di più si allontani dalla mia forma-mentis).
Oggi decido di provare a scrivere un programma che non sia un esercizio di quelli proposti dalla guida che stavo usando e quindi parto con un onesto mergesort.
Comincio a codare e tra esulti e imprecazioni arrivo a scrivere una discreta struttura ricorsiva per fare il tutto.
Peccato che ottengo un comportamento bizzarro nella funzione di mergesort
La funzione faceva una cosa del genere
Codice: Seleziona tutto
mergesort(lista A)
I=A.length
if(I<=1) return A
merge( mergesort( left(A)), mergesort( right(A)));
peccato che mi ritrovo la lista perfettamente ordinata ma parecchi elementi duplicati con una certa logica (che non ho capito).
così decido di fare le cose alla vecchia maniera e mi sono orientato su
Codice: Seleziona tutto
mergesort(lista A)
I=A.length
if(I<=1) return A
B=mergesort( left(A))
C=mergesort( right(A))
merge( B,C );
mentre scrivevo il codice ecco che appena aggiungo B=mergesort( left(A)) decido di fare un test per vedere se la chiamata a funzione riusciva bene.
L'amaro risultato è stato quello di vedere che TUTTO il programma funzionava bene
ma capite???
Un miscuglio senza senso di due metodi mi fa funzionare un programma. E se uso uno dei due metodi il programma fallisce miseramente!!!!
Quella riga aggiunta mi è diventata una blackbox è il fatto che sappia lisp da due giorni non mi consente neanche di capire il perchè con quella chiamata ricorsiva in più (che incasina enormemente l'albero della ricorsione) il tutto funge
infine eccovi il codice completo
Codice: Seleziona tutto
;;;Lisp strange version of mergesort
;;;written by Giovanni Santostefano
;;;http://santostefanogiovanni.blogspot.com
(defun g_merge(A B)
"Merge 2 different lists"
(cond
((null A) B)
((null B) A)
((<= (first A) (first B)) (cons (first A) (g_merge (rest A) B)))
(t (cons (first B) (g_merge A (rest B))))))
;;A is the list
;;I is the list half lenght
(defun g_firsthalf(A I)
"Take the first half of a list"
(if (= I 0)
nil
(cons (first A) (g_firsthalf (rest A) (- I 1)))))
;;A is the list
;;I is the list half length
(defun g_secondhalf(A I)
"Take the second half of a list"
(if (<= I 1)
(rest A)
(g_secondhalf (rest A) (- I 1))))
(defun g_mergesort(A)
"The mergesort"
(setq I (list-length A))
;(print A)
(if (<= I 1) (return-from g_mergesort A))
(setq M (round (/ I 2)))
(setq C (g_mergesort (g_firsthalf A M))) ;blackbox
;(setq D (g_mergesort (g_secondhalf A M))); not work
;(g_merge C D) ) not work
(g_merge (g_mergesort (g_firsthalf A M)) (g_mergesort (g_secondhalf A M))) )
