[Risolto]script Torre di HANOI

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: script Torre di HANOI

Messaggio da Saruman »

>:(
Hai ragione non è semplicissimo! ho provato più volte su carta è penna ma non capisco dov'è l'errore!

Facciamo un esempio passo passo insieme?

Io ho ragionato cosi: Esempio su 3 anelli 7 movimenti in totale:

Si parte da qui!

Codice: Seleziona tutto

case $# in
viene valutata $# ed in base al valore contenuto vengono eseguite le operazioni associate. qui ho gia un dubbio!  :-\ io digito 3 come fa ad entrare nel blocco

Codice: Seleziona tutto

    case $(($1>0)) in     # Must have at least one disk.
    1)
        dohanoi $1 1 3 2
        echo "Total moves = $Moves"
        exit 0;
        ;;
Va be poi ci ritorneremo, cmq siamo in questo blocco, si controlla che il numero di dischi  sia  >0  e si entra nel blocco uno sempre con i soliti dubbi, viene invicata la funzione

Codice: Seleziona tutto

dohanoi $1 1 3 2
$1= numero dischi , pilastro 1 pilastro 3 pilastro 2 e si entra qui.

Codice: Seleziona tutto

dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
	let "Moves += 1"  # Modification to original script.
        dohanoi "$(($1-1))" $4 $3 $2
dove staticamente nella chiamate precedente è stato assegnato $2= pilastro 1 $4 pilastro 3 $3 pilastro 2, quindi all'istruzione successiva dovrebbe stampare

Codice: Seleziona tutto

 echo move $2 "-->" $3
move 1-->2, viene incrementato il numero di movimenti e viene richiamato la funzione 

Codice: Seleziona tutto

dohanoi "$(($1-1))" $4 $3 $2
ovvero dohanoi $1 3 2 1 quindo dopo dovrebbe stampare  move 3-->1 con evidente errore. >:(

Un esempio passo passo con tre anelli credo che mi risolva ogni problema,

Ti ringrazio anticipatamente per la gentilezza.  (b2b)
Avatar utente
nuu
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 394
Iscrizione: mercoledì 30 maggio 2007, 2:07

Re: script Torre di HANOI

Messaggio da nuu »

Allora, andiamo con ordine, se ho capito bene i tuoi dubbi:

1) $# è il numero di parametri passati alla funzione, NON il parametro stesso. Il check fallisce solo se passi due parametri (es hanoi.sh 4 5), mentre finché passi un solo parametro (es hanoi.sh 3), il check riesce. Sto parlando di questo codice:

Codice: Seleziona tutto

case $# in
1)
2) $(($1>0)) restituisce un valore booleano (vero o falso, quindi 1 o 0): se $1>0, allora restituisce 1, mentre se non lo è (ovvero se $10. Ora sto parlando di questo codice:

Codice: Seleziona tutto

    case $(($1>0)) in     # Must have at least one disk.
    1)

e si entra qui.

Codice: Seleziona tutto

dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
	let "Moves += 1"  # Modification to original script.
        dohanoi "$(($1-1))" $4 $3 $2
dove staticamente nella chiamate precedente è stato assegnato $2= pilastro 1 $4 pilastro 3 $3 pilastro 2
no, la chiamata precedente (quella statica) ha assegnato $2=pil1, $3=pil3, $4=pil2.
quindi all'istruzione successiva dovrebbe stampare

Codice: Seleziona tutto

 echo move $2 "-->" $3
move 1-->2, viene incrementato il numero di movimenti e viene richiamato la funzione 

Codice: Seleziona tutto

dohanoi "$(($1-1))" $4 $3 $2
ovvero dohanoi $1 3 2 1 quindo dopo dovrebbe stampare  move 3-->1 con evidente errore. >:(
Di nuovo no, lui decrementa $1 ad ogni ricorsione (chiama dohanoi con primo parametro $(($1-1)) ovvero il risultato di $1-1, quindi dohanoi 2, dohanoi 1, dohanoi 0). Ad ogni ricorsione vengono invertiti i pilastri, perché per ogni ricorsione $2, $3 e $4 rappresentano pilastri diversi (in quanto ogni dohanoi viene chiamata a parametri invertiti). Ogni due ricorsioni i parametri ritornano quelli originali. Ti posso consigliare di commentare un po' lo script per capirci di più. Prova così:

Codice: Seleziona tutto

E_NOPARAM=66  # No parameter passed to script.
E_BADPARAM=67 # Illegal number of disks passed to script.
Moves=        # Global variable holding number of moves.
              # Modifications to original script.

dohanoi() {   # Recursive function.
    case $1 in
    0)
        ;;
    *)
	echo "-- dohanoi "$(($1-1))" $2 $4 $3 (ricors 1)"
	dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
	let "Moves += 1"  # Modification to original script.
        echo "-- dohanoi "$(($1-1))" $4 $3 $2 (ricors 2)"
        dohanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
1)
    case $(($1>0)) in     # Must have at least one disk.
    1)
        echo "-- dohanoi "$1" 1 3 2 (chiamata statica iniziale)"
        dohanoi $1 1 3 2
        echo "Total moves = $Moves"
        exit 0;
        ;;
    *)
        echo "$0: illegal value for number of disks";
        exit $E_BADPARAM;
        ;;
    esac
    ;;
*)
    echo "usage: $0 N"
    echo "       Where "N" is the number of disks."
    exit $E_NOPARAM;
    ;;
esac
Magari capisci un po' meglio cosa sta succedendo!

Ciao
nuu
Learn to pause -- or nothing worthwhile can catch up to you.
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: script Torre di HANOI

Messaggio da Saruman »

:-*

Tutto chiaro per il case pero non ho digerito bene come si combinano i pilastri.

Dopo la chiamata statica

Codice: Seleziona tutto

dohanoi $1 1 3 2
$1 vale 3 e si va in questo blocco

Codice: Seleziona tutto

dohanoi "$(($1-1))" $2 $4 $3
si rimane qui fin tanto che $1 non è uguale a zero Si rimane nella ricorsione 1 combinando i pilastri

Codice: Seleziona tutto

-- dohanoi "3" 1 3 2 (chiamata statica iniziale)
-- dohanoi "2" 1 2 3 (ricors 1 roby)
-- dohanoi "1" 1 3 2 (ricors 1 roby)
-- dohanoi "0" 1 2 3 (ricors 1 roby)
visto che si rimane su questa istruzione ed solo $1 viene decrementata fino a zero non capisco come cavolo si combinano i pilastri.  (mad)

Ho capito che si combinano tra i valori iniziali ovvero $2 = 1 $4=2  $3=3 e la chiamata statica $2=1 $4=3 $3=0 ma come si alternano no?

cmq alla fine abbiamo "quando $1=0" 123 quindi $2=1 $4=2 $3=3 e quindi echo move $2 "-->" $3 stampa 1--> 3 e si incrementa il numero delle mosse. a questo punto si arriva all'istruzione

Codice: Seleziona tutto

 dohanoi "$(($1-1))" $4 $3 $2
con i valori iniziali $2=1 $4=2 $3=3 ovvero 231

Da qui in poi mi sono perso..
Per prima cosa $1 se viene decrementato perche non resta a zero ?

Spero di non aver detto un mare di cavolate!

Mi resta da capire tutto il resto

Codice: Seleziona tutto

 -- dohanoi "3" 1 3 2 (chiamata statica iniziale)
-- dohanoi "2" 1 2 3 (ricors 1 )
-- dohanoi "1" 1 3 2 (ricors 1 )
-- dohanoi "0" 1 2 3 (ricors 1 )
move 1 --> 3
-- dohanoi "0" 2 3 1 (ricors 2)
move 1 --> 2
-- dohanoi "1" 3 2 1 (ricors 2)
-- dohanoi "0" 3 1 2 (ricors 1 )
move 3 --> 2
-- dohanoi "0" 1 2 3 (ricors 2)
move 1 --> 3
-- dohanoi "2" 2 3 1 (ricors 2)
-- dohanoi "1" 2 1 3 (ricors 1 )
-- dohanoi "0" 2 3 1 (ricors 1 )
move 2 --> 1
-- dohanoi "0" 3 1 2 (ricors 2)
move 2 --> 3
-- dohanoi "1" 1 3 2 (ricors 2)
-- dohanoi "0" 1 2 3 (ricors 1 )
move 1 --> 3
-- dohanoi "0" 2 3 1 (ricors 2)
Total moves = 7
Avatar utente
nuu
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 394
Iscrizione: mercoledì 30 maggio 2007, 2:07

Re: script Torre di HANOI

Messaggio da nuu »

ybor4 ha scritto: Ho capito che si combinano tra i valori iniziali ovvero $2 = 1 $4=2  $3=3 e la chiamata statica $2=1 $4=3 $3=0 ma come si alternano no?
allora, metti caso io abbia una funzione "pippo" e la chiamo così: "pippo par1 par2". Pippo è il nome funzione, par1 è il primo parametro, e par2 il secondo.
Nella funzione pippo, io elaboro i parametri usando $1 e $2. La prima volta che entro in pippo, $1 è "par1" e $2 è "par2".
Ora, da qualche parte pippo chiama sé stessa, perché è una funzione ricorsiva. La chiamata avviene con una riga che dice: "pippo $2 $1". Nota che $2, in questa chiamata, viene prima di $1. Nella prossima ricorsione di pippo, quindi, $1 non sarà più "par1", ma "par2"..e $2 sarà "par1"! Abbiamo cioè invertito l'ordine dei parametri. Ma che succede quando arriviamo di nuovo alla ricorsione ? succede che la chiamata "pippo $2 $1" stavolta si traduce in "pippo par1 par2"...ovvero torniamo alla situazione iniziale! Giacché questa cosa si ripete ad ogni iterazione, come vedi i parametri non fanno altro che invertirsi di volta in volta! Capito ora ? $1 e $2 non sono variabili *statiche*, ma sono i parametri passati alla funzione in QUELLA ricorsione specifica, e se io richiamo la ricorsione con $2 $1, nella successiva saranno invertiti... e in quella dopo, saranno dritti di nuovo :)
Spero davvero di essere stato chiaro perché meglio di così non so spiegartelo :)
Per prima cosa $1 se viene decrementato perche non resta a zero ?
per lo stesso motivo di sopra. $1 è una variabile locale della funzione dohanoi, quindi ogni ricorsione ha la propria. Se in una ricorsione la variabile raggiunge 0, la funzione termina e si ritorna alla ricorsione precedente. E in questa, magari $1 non è più zero.
Spero di non aver detto un mare di cavolate!
Per carità, non sono cavolate, ma permettimi di dire che hai scelto uno script che oltre ad essere un puro esercizio di stile, ha utilità praticamente nulla e non corrisponde a nulla di quanto vedrai nel mondo reale se tu dovessi mai andare ad amministrare una macchina usando Linux/Unix e bash. Io se fossi il tuo prof avrei molto più piacere ad esempio a vedere uno scriptino che prende in pasto un file di testo ed interpreta ogni riga come una directory, e ne fa il backup con tar, per poi spostarla in una directory di destinazione, e magari rimuove i vecchi backup dopo x giorni. E' immediato (ma non banalissimo) da realizzare, e ti insegna di più su variabili, path, comandi di sistema, confronti delle date, e operazioni pratiche su un sistema live unix di quanto tu creda di stare imparando ora :)

Ciao
nuu
Learn to pause -- or nothing worthwhile can catch up to you.
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: script Torre di HANOI

Messaggio da Saruman »

ok!

Grazie ora ho capito! Sull apprendere mi sa che hai ragione, cmq ho imparato la ricorsione che non è banale  (b2b)

Sono sempre pronto a nuove cose, quasi quasi posso proporgli anche un altro progetto tanto ho tempo fino al 5 e questo ormai lo finisco per aumentare il voto...

Hai delle specifiche più precise in modo che possa proporle al mio prof?

P.S. io sono sempre disposto a studiare ma non ho nessuna vergogna a chiedere spiegazioni e delucidazioni anche su piccole cose  (good)
Avatar utente
nuu
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 394
Iscrizione: mercoledì 30 maggio 2007, 2:07

Re: script Torre di HANOI

Messaggio da nuu »

certo, la ricorsione è un concetto importante nella programmazione, ma in bash è quasi inutilizzata :)

Comunque, quella del backup era giusto un'idea buttata lì, pensa tu stesso a cosa vorresti vedere in uno script di backup sul tuo sistema :) Io ne ho fatto uno simile per me visto che mi serviva concentrare tutto in uno diversi tipi di backup (database mysql, directory locali etc). Pensa tu a cosa vorresti, e proponilo :)

Ciao
nuu
Learn to pause -- or nothing worthwhile can catch up to you.
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: script Torre di HANOI

Messaggio da Saruman »

Ok Grazie ci penso un po sopra e ti faccio sapere.
Avatar utente
simo_magic
Rampante Reduce
Rampante Reduce
Messaggi: 9496
Iscrizione: lunedì 18 dicembre 2006, 21:37
Località: Piemonte

Re: [Risolto]script Torre di HANOI

Messaggio da simo_magic »

se proprio ti piace quell'algoritmo qui ti puoi sbizzarrire con i vari linguaggi! (rotfl)
http://www.kernelthread.com/hanoi/
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: [Risolto]script Torre di HANOI

Messaggio da Saruman »

Qualcuno, tanto per cultura generale, mi fa vedere la versione interattiva delle TorriDiHanoi?  (b2b)

Grazie
Avatar utente
nuu
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 394
Iscrizione: mercoledì 30 maggio 2007, 2:07

[Audio] Re: script Torre di HANOI

Messaggio da nuu »

interattiva? intendi forse iterativa?

Ciao
nuu
Learn to pause -- or nothing worthwhile can catch up to you.
Avatar utente
Saruman
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2378
Iscrizione: venerdì 16 marzo 2007, 22:29

Re: script Torre di HANOI

Messaggio da Saruman »

Si iterativa! scusa la gaff :-[
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 4 ospiti