Ricorsione – ValCon.It

Hanoi

13/02/201811/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

28/02/201810/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

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 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 … Leggi tutto

La torre di Hanoi

06/12/201701/01/2015 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 … Leggi tutto

Quick sort

06/12/201731/12/2014 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;