 |
Lisp »Tips 'n Tricks
»Funzioni ricorsive in AutoLISP
»1
| 2
| 3
| 4
| 5
| 6
| 7 a
, b
, c
, d
, e
>II
>III
>IV
>V
>VI
>VII
Ricerca binaria in una lista ordinata e non
RBR usa le funzioni ricorsive per cercare un elemento in una lista ordinata.
Data una lista ordinata si legge l'elemento centrale se corrisponde alla chiave la ricerca è finita altrimenti si cerca nella prima metà della lista o nella seconda metà in base al fatto che la chiave sia minore o maggiore dell'elemento centrale.
;|
Rbr.lsp - 16 Marzo 2004
© 2004 Claudio Piccini
www.cg-cad.com
Ricerca binaria in una lista ordinata
Traduzione in Autolisp di ricercaBinRic()
Dal testo: C e Java, Laboratorio di Programmazione
Mc Graw Hill, 1997
©1997 A. Cisternino G. Fiorentino M.R. Laganà F. Romani F. Turini
#include "ricbric.h"
#include "bool.h"
bool ricercaBinRic(Elem x, Vettore a, int i, int j)
{
if (i > j)
return False;
else {
int k = (i + j)/2;
if (x == a[k])
return True;
if (x < a[k])
return ricercaBinRic(x, a, i, k - 1);
else
return ricercaBinRic(x, a, k + 1, j);
}
}
|;
(defun cerca (x ls i j / k)
(if (= test 0)
(progn
(if (> i j)
(progn
(setq test 1)
(princ "Falso")
)
(progn
(setq k (/ (+ i j) 2))
(if (= x (nth k ls))
(progn
(setq test 1)
(princ "Vero")
)
)
(if (and (< x (nth k ls))(= test 0))
(cerca x ls i (- k 1))
(cerca x ls (+ k 1) j)
)
)
)
)
)
)
(defun c:rbr ( / test ls j i x)
(setq test 0)
(setq ls
(list "Albero"
"Bianco"
"Cielo"
"E"
"Nuvola"
"Ombra"
"Spring"
)
)
(setq j (length ls))
(setq i 0)
(setq x (getstring "\n? "))
(cerca x ls i j)
(princ)
)
;;;eof
|
Test del LISP
Command: RBR
? Albero
Vero
Command: RBR
? E
Vero
Command: RBR
? albero
Falso
Command: RBR
? Bianco
Vero
Command: RBR
? Nuvola
Vero
Command: RBR
? Spring
Vero
Command: RBR
? Cielo
Vero
Command: RBR
? 123.5
Falso
Command: RBR
? Ombra
Vero
E se la lista non è ordinata? RBR2 implementa l'algoritmo delle bolle (Bubblesort).
Il metodo delle bolle consiste nello scorrere la lista, effettuando scambi quando due elementi contigui non sono nell'ordine giusto. In questo modo gli elementi minori, più leggeri salgono verso l'alto (immaginando la lista in verticale) come bolle... Il lisp usa la funzione (scambia x y).
Per vedere se funziona il lisp mostra la lista prima e dopo la bollitura.
;|
Rbr2.lsp - 16 Marzo 2004
© 2004 Claudio Piccini
www.cg-cad.com
Ricerca binaria in una lista non ordinata
|;
(defun scambia (i j / temp a b q lss)
(setq temp (nth i ls))
(if (/= i j)
(progn
(setq a (nth j ls))
(setq q 0)
(repeat (length ls)
(setq b (nth q ls))
(cond
((= q i)
(setq lss (append lss (list a)))
)
((= q j)
(setq lss (append lss (list temp)))
)
((and (/= q i)(/= q j))
(setq lss (append lss (list b)))
)
)
(setq q (1+ q))
)
(setq ls lss)
(setq lss nil)
)
)
)
(defun cerca (x i j / k)
(if (= test 0)
(progn
(if (> i j)
(progn
(setq test 1)
(princ "Falso")
)
(progn
(setq k (/ (+ i j) 2))
(if (= x (nth k ls))
(progn
(setq test 1)
(princ "Vero")
)
)
(if (and (< x (nth k ls))(= test 0))
(cerca x i (- k 1))
(cerca x (+ k 1) j)
)
)
)
)
)
)
(defun BubbleSort (size / i s)
(setq i 1)
(while (< i size)
(setq s (- size 1))
(while (>= s i)
(if (>
(nth (- s 1) ls)
(nth s ls)
)
(scambia (- s 1) s)
)
(setq s (1- s))
)
(setq i (1+ i))
)
)
(defun c:rbr ( / test ls j i x)
(setq test 0)
(setq ls
(list "E"
"Cielo"
"Bianco"
"Nuvola"
"Spring"
"Albero"
"Ombra"
)
)
(setq j (length ls))
(setq i 0)
(princ ls) ;mostra la lista ls
(BubbleSort j) ;ordina la lista ls
(princ "\n")
(princ ls) ;mostra la lista ordinata
(setq x (getstring "\n? "))
(cerca x i j)
(princ)
)
;;;eof
|
Test del LISP
Command: rbr
(E Cielo Bianco Nuvola Spring Albero Ombra)
(Albero Bianco Cielo E Nuvola Ombra Spring)
? Albero
Vero
Command:
Command:
RBR (E Cielo Bianco Nuvola Spring Albero Ombra)
(Albero Bianco Cielo E Nuvola Ombra Spring)
? E
Vero
Command:
Command:
RBR (E Cielo Bianco Nuvola Spring Albero Ombra)
(Albero Bianco Cielo E Nuvola Ombra Spring)
? ombra
Falso
Lisp »Tips 'n Tricks
Ultimo Aggiornamento_Last Update: 16 Marzo 2004
|
|
