----- 19/01/18 -----

> L'esercizio 5 dell'esame del 3/02/2017 (prova scritta di recupero)
> chiede di transformare la procedura per renderla piu' efficiente,
> applicando la tecnica top-down di memoization.
> Tuttavia, la procedura che riporto qui di seguito fornisce risultati diversi
> rispetto a quella originale (per alcuni input):
>
>     /* Costante "cauale" per inizializzare l'array */
>     private static final int UNKNOWN = -253; 
>
>     public static int f( String s ) {
>       return gmem( s, ' ' );
>     }
>
>     /* Dichiarazione e inizializzazione di un array
>      * La dimensione 128 corrisponde al range di cartteri (valori di b)
>      */
>     private static int arr[];
>     public static void init() {
>       arr = new int[128];
>       for (int i=0; i<127 ; i++) {
>         arr[i] = UNKNOWN;
>       }
>     }
>	
>     public static int gmem( String s, char b ) {
>       if (arr[b]==UNKNOWN) {  // Controllo se e' gia' stato calcolato
>                              // un risultato per la stringa s e il carattere b.
>                              // [...]
>         if (s.equals("")) {
>           arr[b]=0;
>         } else {
>           char c = s.charAt(0);
>           String st=s.substring(1);
>           if (c<=b) {
>             arr[b] = gmem(st,b);
>           } else {
>             arr[b] = Math.max(gmem(st,b),gmem(st,c)+1);
>       }}}
>       return arr[b];
>     }

-----

La ragione principale per cui il programma non puo' funzionare
(cioe' non consente di calcolare gli stessi valori calcolati da f nel programma originale)
e' che i valori della procedura ricorsiva g dipendono da due parametri, una stringa e un carattere, mentre gli elementi dell'array in cui registri i valori gia' calcolati
dipendono da un solo indice, che corrisponde al carattere.
Di conseguenza, quando vengono calcolati due valori diversi in corrispondenza
allo stesso carattere, poniamo  g(u,c)  e  g(v,c),  il secondo di questi che viene
registrato in corrispondenza all'indice associato a c sostituisce il precedente,
che viene quindi perso definitivamente.

Nella soluzione, pero', ci sono anche altri problemi:

- Metodologicamente sarebbe opportuno evitare variabili globali
  definite attraverso l'attributo "static": la struttura degli esempi svolti
  in classe costituisce un modello piu' adatto per impostare la soluzione.

- Il metodo "init" non viene mai invocato
  e quindi non si capisce quando l'array dovrebbe essere inizializzato.

----- * -----