 |
Lisp »Tips 'n Tricks
»Funzioni ricorsive in AutoLISP »1 | 2 | 3 | 4 | 5 | 6 | 7
La Torre di Hanoi
La Torre di Hanoi è un gioco che consiste in tre pioli verticali e un certo numero di dischi di dimensioni decrescenti. All'inizio del gioco, i dischi sono impilati in ordine di grandezza crescente sul primo piolo (a sinistra).
Il gioco consiste nello spostare tutti i dischi dal primo al secondo piolo, muovendo solo un disco alla volta e senza che mai un disco più piccolo stia sotto uno più grande; il terzo piolo è d'ausilio come punto di appoggio nei trasferimenti.
I pioli sono numerati da 0 a 2.
I due listati (in Pascal e AutoLISP) sfruttano le funzioni ricorsive e suggeriscono le mosse necessarie per risolvere il gioco.
Il lisp salva le soluzioni nel file HANOI.TXT, nella cartella aperta, mentre il programma in Pascal mostra le mosse su video (per non saturare la memoria DOS).
Le mosse sono 2ª - 1 (a è il numero dei dischetti).
Hanoi.pas
{
hanoi.pas by Claudio Piccini
www.cg-cad.com
}
program torri_di_hanoi;
var
nmossa,ndischi: Integer;
Procedure muovi(disco,sorgente,destinazione:Integer);
begin
nmossa := succ(nmossa);
Writeln(nmossa,' muovi il disco ',disco,' da ',sorgente,' a ',destinazione)
end;
Procedure hanoi(nrdis,sorgente,destinazione,ausiliario:Integer);
begin
if nrdis=1 then
muovi(1,sorgente,destinazione)
else
begin
hanoi(nrdis-1,sorgente,ausiliario,destinazione);
muovi(nrdis,sorgente,destinazione);
hanoi(nrdis-1,ausiliario,destinazione,sorgente)
end;
end;
begin (* main *)
nmossa := 0;
Write('Introdurre numero di dischi<=15: ');
Readln(ndischi);
hanoi(ndischi,0,1,2)
end.
|
Hanoi.lsp
;;;
;;; hanoi.lsp - 16 Febbraio 2004
;;; (C)2004 by Claudio Piccini
;;; http://www.cg-cad.com/
;;;
;;; Gioco della Torre di Hanoi
;;;
(defun muovi (disco sorgente destinazione / cm cd cs cds)
(setq nmossa (1+ nmossa))
(setq cm (itoa nmossa))
(setq cd (itoa disco))
(setq cs (itoa sorgente))
(setq cds (itoa destinazione))
(setq str (strcat cm " muovi il disco " cd " da " cs " a " cds "\n"))
(write-line str f1)
)
(defun hn (nrdis sorgente destinazione ausiliario)
(if (= nrdis 1)
(muovi 1 sorgente destinazione)
(progn
(hn (- nrdis 1) sorgente ausiliario destinazione)
(muovi nrdis sorgente destinazione)
(hn (- nrdis 1) ausiliario destinazione sorgente)
)
)
)
(defun c:hanoi ( / nomeDir nf)
(setq nomeDir (getvar "dwgprefix"))
(setq nf (strcat nomeDir "hanoi.txt"))
(setq f1 (open nf "w"))
(setq nmossa 0)
(initget (+ 1 2 4))
(setq ndischi (getint "\nIntrodurre numero di dischi<=15: "))
(princ "\n")
(hn ndischi 0 1 2)
(close f1)
(princ)
)
;;;eof
|
Camminare (e incontrarsi per strada) a Manhattan
La piantina raffigura un quartiere simile a Manhattan, le cui strade sono regolari (con una eccezione). Si ipotizza che ogni tratto di strada fra un incrocio e quello successivo, sia in direzione N->S che in direzione O->E, abbia una lunghezza di 100 metri.
L'obiettivo è andare a piedi dall'isolato A (e in particolare dall'incrocio in basso a destra dell'isolato A) all'isolato B (e in particolare all'incrocio in alto a sinistra dell'isolato B).
Se B dista da A e isolati in direzione O->E e c isolati in direzione N->S, dobbiamo percorrere e+c tratti di strada.
Quante alternative abbiamo per spostarci da A a B lungo uno dei percorsi più brevi?
Se e=c=0 restiamo dove siamo = 1.
Se e=0 (a) o c=0 (b)
l'unico percorso più breve è una linea retta N->S (a) o O->E (b) = 1.
Resta e,c>0 e il problema è lo stesso anche se A e B sono molto vicini:
I percorsi più brevi sono solo 2: e+c e c+e; non esiste un terzo percorso breve che attraversa sia l'incrocio + sia l'incrocio +!
Se spostiamo A dove era in origine si vede che comunque ogni percorso breve che porta a B deve passare da + o da + ma non da entrambi.
La soluzione sta nel sommare il numero di percorsi brevi che passano da + e il numero di percorsi brevi che attraversano +.
Il numero di percorsi brevi da A a + è lo stesso problema con e e c-1 (a).
Il numero di percorsi brevi da A a + è lo stesso problema con e-1 e c (b).
Infatti nel caso (2) (a) è e=1,c=0 e (b) e=0,c=1.
Manh.pas
{
manh.pas by Claudio Piccini
www.cg-cad.com
}
program camminare_Manhattan;
var
e,c: Integer;
function nPercorsi(e,c:Integer):Integer;
begin
if (e=0) or (c=0) then nPercorsi := 1
else nPercorsi := nPercorsi(e,c-1) + nPercorsi(e-1,c)
end;
begin (* main *)
Write('Introdurre numero di isolati in direzione OVEST-EST: ');
Readln(e);
Write('Introdurre numero di isolati in direzione NORD-SUD: ');
Readln(c);
Writeln('Le alternative sono ', nPercorsi(e,c))
end.
|
Manh.lsp
;;;
;;; manh.lsp - 17 Febbraio 2004
;;; (C)2004 by Claudio Piccini
;;; http://www.cg-cad.com/
;;;
;;; Per le strade di Manhattan
;;;
(defun nPercorsi (e c)
(if (or (= e 0)(= c 0))
(setq np 1)
(setq np (+ (nPercorsi e (- c 1))(nPercorsi (- e 1) c))))
)
(defun c:manh ()
(initget (+ 1 4)) ; non nullo e non negativo
(setq e (getint "\nIntrodurre numero di isolati in direzione OVEST-EST: "))
(initget (+ 1 4)) ; non nullo e non negativo
(setq c (getint "\nIntrodurre numero di isolati in direzione NORD-SUD: "))
(princ (strcat "\nLe alternative sono " (itoa (nPercorsi e c))))
(princ)
)
;;;eof
|
Lisp »Tips 'n Tricks
Ultimo Aggiornamento_Last Update: 17 Febbraio 2004
|
|
