Repository 32bit  Forum
Repository 64bit  Wiki

MergeSort comico in Lisp

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

MergeSort comico in Lisp

Messaggioda Blizzard » ven lug 18, 2008 15:01

Ciao,
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 :evil:
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))) )
Avatar utente
Blizzard
Master
Master
 
Messaggi: 1509
Iscritto il: mar gen 02, 2007 22:53
Nome Cognome: Giovanni Santostefano
Slackware: 12.2
Kernel: 2.6.27.7-smp
Desktop: Fluxbox

Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti

cron