30 maggio 2024 - esercizio 6

[Elia-Belli]

[Elia-Belli]

Il numero $n$ può essere ottenuto in 3 modi applicando le rispettive operazioni ai numeri $n-1,\ n/2,\ n/3$ , ottenibili ricorsivamente allo stesso modo.

• Se vogliamo minimizzare le operazioni sceglieremo ad ogni chiamata ricorsiva il minimo dei 3 per poi sommare $1$, ovvero l'ultima operazione necessaria per ottenere $n$, con caso base $x_2 = 0$
  $$x_n = min(x_{n-1},\ x_{n/2},\ x_{n/3}) +1$$

• Se vogliamo calcolare il numero di modi per ottenere $n$ dovremo sommare i modi per ottenere i numeri a cui applicare l'ultima operazione ricorsivamente, con caso base $y_2 = 1$
  $$y_n = y_{n-1} + y_{n/2} + y_{n/3}$$

[CiottoloMaggico]

[CarloDaRomadev]

è possibile trovare Xn con un algoritmo di programmazione dinamica

ma non è possibile trovare Yn con un algoritmo di programmazione dinamica nel tempo richiesto, ho quindi usato una strategia differente

queste funzioni hanno costo O(n + 3n)