Vai al contenuto principale
← OlimpiApp Difficile

Informatica · Algoritmi

Chiamate memoizzate di f(22)

Una funzione ricorsiva è definita da $f(n) = f(n-2) + f(n-5)$ per $n \ge 5$, con $f(n) = 1$ per ogni n < 5 (caso base, senza ulteriore ricorsione). Viene calcolata f(22) usando la memoization (ogni valore di n viene calcolato al più una volta: le chiamate successive con lo stesso argomento riusano il risultato salvato). Quante chiamate ricorsive distinte (cioè quanti valori distinti di n) vengono effettivamente eseguite in tutto, incluso il calcolo iniziale di f(22)?