----- 10/06/13 -----

> Mi riferisco all'esercizio di laboratorio del 17 Aprile 2013,
> piu' precisamente il punto 2.
>
> Sono riuscito a tradurre da Scheme a Java la procedura "g",
> ho realizzato la versione che applica correttamente la memoization,
> ma la versione in programmazione dinamica non funziona
> e non riesco a capire perche'.
>
> Includo i programmi che ho realizzato.
>
> Memoization:
>
> public static final int UNKNOWN = 0;	
>
> public static int g(int x, int y)
> {
>   int[][] h = new int [x+y][y+x];
>
>   for(int i = 0; i <= x; i = i+1)
>   {	
>     for(int j = 0; j <=y; j = j+1)
>     {
>       h[i][j] = UNKNOWN;
>     }
>   }
>   return gMem(x, y, h);
> }
>
> public static int gMem(int x, int y, int[][] h)
> {
>   if( h[x][y] == UNKNOWN )
>   {
>     if( (x<2) || (y<2) )
>     {
>       h[x][y] = (x * y);
>     }
>     else
>     {
>       h[x][y] = gMem((x-1),y,h) + gMem(x,(y-2),h) + gMem((x+1),(y-1),h);
>     }
>   }
>   return h[x][y];
> }
>
> Programmazione dinamica:
>
> public static final int UNKNOWN = 0;
>
> public static int gDim(int x, int y)
> {
>   int[][] h = new int [x+y][y+x];
>   for(int i = 0; i <= x; i = i+1)
>   {	
>     for(int j = 0; j <= y; j = j+1)
>     {
>       h[i][j] = UNKNOWN;
>     }
>   }
>   int count = 0; // Contatore per le prove
>
>   for(int i = 0; i <= x; i = i+1)
>   {	
>     for(int j = 0; j <= y; j = j+1)
>     {
>       if( (i < 2) || (j < 2) )
>       {
>         h[i][j] = (i * j);
>         break; 
>       }
>       else
>       {
>         h[i][j] = h[i-1][j] + h[i][j-2] + h[i+1][j-1];
>       }
>     }
>   }
>   return h[x][y];
> }

-----

Il problema sta nell'ordine in cui sono calcolati gli elementi
della matrice, in quanto si fa riferimento a valori che in realta'
non sono ancora stati determinati. (Per rendersene conto,
e' sufficiente provare a simulare il processo manualmente.)

Aggiungo due osservazioni:
1. La matrice e' in genere sovradimensionata
(cosa succede se uno dei due argomenti e' zero?);
2. nel caso di programmazione dinamica,
non e' necessario inizializzare la matrice preliminarmente.

----- * -----