Ricorsione

Hanoi

11/02/201813/02/2018 di admin

Vedi la discussione

Algoritmo ricorsivo…

START

QUERY "Quanti dischi? ", n

CALL hanoi(n,1,2,3)

END

ENTER n,a,b,c

IF n = 1 THEN

WRITE a, "-->", c

ELSE

CALL hanoi(n-1,a,c,b)

CALL hanoi(1,a,b,c)

CALL hanoi(n-1,b,a,c)

ENDIF

RETURN

Fibonacci

10/02/201828/02/2018 di admin

Vedi la discussione

Versione ricorsiva…

START

QUERY "n = ", n

fn=fibonacci(n)

WRITE "Fibonacci di", n, "=", fn

END

ENTER n

IF n <= 2 THEN

f=1

ELSE

f=fibonacci(n-1)+fibonacci(n-2)

ENDIF

RETURN f

Versione iterativa

START

QUERY "n = ", n

a=1

b=1

IF n >= 3 THEN

FOR i=3 TO n STEP 1 DO

c=a+b

a=b

b=c

ENDFOR

ENDIF

WRITE b

END

05/05/201502/03/2017 di admin

Se il linguaggio di programmazione prevede la ricorsione… una SUB A può chiamare la SUB A, se stessa, per svolgere lo stesso compito ma con un’stanza diversa

ricorsione

La SUB A chiama la SUB A … finché non succede qualcosa (l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva) e si ritorna all’indietro fino alla prima chiamata…

Procedura

Funzione

Basic

Sub XYZ(parametri_formali)

...

Call XYZ(parametri_attuali)

...

End Sub

Function XYZ(parametri_formali) As Double

...

x=XYZ(parametri_attuali)

...

XYZ=espr

End Function

C…

void XYZ(parametri_formali)

{

...

XYZ(parametri_attuali);

...

}

double XYZ(parametri_formali)

{

...

x=XYZ(parametri_attuali);

...

return espr;

}

Pascal

Procedure XYZ(parametri_formali);

...

Begin

...

XYZ(parametri_attuali);

...

End;

Function XYZ(parametri_formali): Double;

...

Begin

...

x=XYZ(parametri_attuali);

...

XYZ:=espr;

End;

Ricorsione indiretta

Nel caso di ricorsione indiretta il sottoprogramma chiama un secondo sottoprogramma che a sua volta … che a sua volta chiama il primo

…

La torre di Hanoi

01/01/201506/12/2017 di admin

Il problema

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.
Sul primo di tali perni sono infilati 64 dischi d’oro, di dimensioni decrescenti, che formano una torre.
Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.
Per risolvere la questione si può utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l’opera il mondo sarà finito!

Analisi

Siano D₁, D₂, …, D_n le etichette dei dischi di una torre di Hanoi con n dischi.

Prova!

Analisi

Il problema con un solo disco è banale

il disco è sinistra
sposta il disco D₁ dalla 1° alla 3° torre

Se i dischi sono 2 le mosse sono 3

i dischi sono a sinistra
sposta il disco D₁ dalla 1° alla 2° torre
sposta il disco D₂ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 3° torre

Se i dischi sono 3 le mosse sono 7

i dischi sono a sinistra
sposta il disco D₁ dalla 1° alla 3° torre
sposta il disco D₂ dalla 1° alla 2° torre
sposta il disco D₁ dalla 3° alla 2° torre
sposta il disco D₃ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 1° torre
sposta il disco D₂ dalla 2° alla 3° torre
sposta il disco D₁ dalla 1° alla 3° torre

…

Se i dischi sono 4, 5, … si può riconoscere lo schema risolutivo

i dischi sono a sinistra
sposta i dischi D₁…D_n-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare D_n
sposta il disco D_n dalla 1° alla 3° torre
sposta i dischi D₁…D_n-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra D_n

Algoritmo

Ad ogni passo è sufficiente specificare

il numero di dischi coinvolti, perché si parla sempre dei dischi in cima a una torre
il nome della torre di origine
il nome della torre di appoggio
il nome della torre di destinazione

allora l’algoritmo risolutivo per il problema

Hanoi(n, origine, appoggio, destinazione)

diventa

Hanoi(n-1, origine, arrivo , appoggio)
Hanoi(1, origine, appoggio, destinazione)
Hanoi(n-1, appoggio, origine, destinazione)

con l’accortezza che nel caso di torre con un solo disco è sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.

Prova!

La soluzione è costituita da una sequenza di coppie

a >> b

di spostamenti dalla torre a alla torre b.

La complessità dell'algoritmo

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell'algoritmo è proporzionale al numero di spostamenti di dischi

T(1) = 1
T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3
T(3) = T(2)+T(1)+T(2) = 3+1+3 = 7
T(4) = T(3)+T(1)+T(3) = 7+1+7 = 15
...
T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1
...

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

2¹-1, 2²-1, 2³-1, 2⁴-1, 2⁵-1, 2⁶-1, 2⁷-1, ...

quindi

T(n) = 2ⁿ-1

I tempi necessari per risolvere il problema sono

n	T(n) = 2ⁿ-1	1 Hz (uomo)	1 GHz (PC)
1	2¹-1 = 1	un secondo	10^-9 s
2	2²-1 = 3	3 secondi	3*10^-9 s
10	2¹⁰-1 = 1023	~17 minuti	~10^-6 s
20	2²⁰-1 = 1.048.575	~12 giorni	~10^-3 s
30	2³⁰-1 = 1.073.741.823	~34 anni	~1 s
64	2⁶⁴-1 = 18.446.744.073.709.551.615	~5*10¹¹ anni	~500 anni

Conclusioni

L'algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2ⁿ)
Non può esistere un algoritmo con complessità minore
Il problema della torre di Hanoi è un problema intrinsecamente esponenziale
Il problema della torre di Hanoi è un problema intrattabile!

Quick sort

31/12/201406/12/2017 di admin

Un algoritmo di ordinamento

molto complicato: ricorsivo e difficile da ricordare
ma ottimo: è quasi sempre molto veloce…

Procedure QUICKSORT(var V: Vettore; Inf, Sup: Integer);

Var

i, j: Integer;

Perno: Elemento;

Begin1

If(Inf < Sup) Then

Begin

i:=Inf;

j:=Sup;

Perno:=V[(Inf+Sup) DIV 2];

Repeat

While(V[i] < Perno) Do

Inc(i);

While(Perno < V[j]) Do

Dec(j);

If(i <= j) then

Begin

SCAMBIA(V[i], V[j]);

Inc(i);

Dec(j);

End;

Until(I > J);

QUICKSORT(V, Inf, j);

QUICKSORT(V, i, Sup);

End;