Materiali didattici che utilizzo per integrare i libri di testo, motivare e/o distrarre i miei studenti.
Dopo aver analizzato gli algoritmi risolutivi consideriamo i pro e i contro di ognuno Metodo risolutivo Pro Contro Ricorsivo Codifica elegante ~n chiamate ricorsive~n moltiplicazioni Iterativo Codifica elementare ~n moltiplicazioni Con formula Numero di operazioni costante Difficile da ricordareNumeri irrazionaliValore approssimato Conclusioni Per il calcolo del fattoriale di n esistono più algoritmi Al crescere di … 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 T(1) = 1 T(2) = 1 T(3) = 1+T(2)+T(1) = 1+1+1 = 3 > 22-1 T(4) = 1+T(3)+T(2) = 1+3+1 = 5 > 22-1 T(5) = … Leggi tutto
Vedi la discussione Algoritmo ricorsivo…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 |
Vedi la discussione Versione ricorsiva…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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