Ricorsione

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi Numericamente si tratta della successione 1, 3, 7, 15, 31, 63, 127, … cioè 21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, … quindi T(n) = 2n-1 I tempi necessari per una persona oppure per un … Leggi tutto

Vedi esercizio numero 12 di pagina 202 del libro di testo Vedi gli algoritmi risolutivi Versione iterativa T(n) = m1 + m2 + […] + m3= m1+m2+[f1+f2+{…}+f6]+m3= m1+m2+[f1+f2+{(f3+f4+f5)*n+f3}+f6]+m3= (3n+4)+3= 3*n+7 Versione ricorsiva Cioè La ricorsione sostituisce l’iterazione e non cambia significativamente il tempo di esecuzione. Versione con formula In ordine di esecuzione (le operazioni sono … Leggi tutto

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo. Algoritmo ricorsivo Il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive Il tempo di attesa è esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande L’algoritmo ricorsivo per il calcolo … Leggi tutto

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

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