Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Giovi89 on 17-04-2009, 14:46:19



Title: problema ricorsione esercizio 3
Post by: Giovi89 on 17-04-2009, 14:46:19
Ragazzi ho provato a fare il seguente esercizio ma mi da errore:
Code:
class matrice
{
int i=0;
int j=0; int x=0;
public int [][] inserisci(int [] A, int [][] B)
{
if(x==B.length-1)//MI CONTROLLA LE COLONNE DELLA MATRICE BIDIMENSIONALE
{
x=0;
j++;
}
if(i==A.length-1)//PASSO BASE(INDICE CHE CONTROLLA L'ARRAY MONODIMENSIONALE
return B;
else
{
B[j][x]=A[i];
i++;
x++;
return inserisci(A, B);//PASSO INDUTTIVO
}
}

public static void main(String [] args)
{
matrice a=new matrice();
int A[] ={1,2,3,4,5,6,7,8,9};
int [][] B= new int [3][3];
int [][] e=a.inserisci(A, B);
for(int i=0; i<e.length;i++){
for(int j=0; j<e.length;j++)
System.out.print(e[i][j]+"\t");
} System.out.println();

}
}
il testo è il seguente:
Si supponga di avere un array contenente n2 oggetti. Scrivere un
metodo ricorsivo che inserisca tutti gli oggetti in un array
bidimensionale n x n.

grazie in anticipo... .ciaociao


Title: Re:problema ricorsione esercizio 3
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 18-04-2009, 01:53:25
Poiché una matrice è uno spazio geometrico discreto e non è stato definito alcun
tipo di ordinamento topologico da seguire, scelgo un mio ordinamento topologico
personalizzato.
Ricordando che a.length si suppone una potenza perfetta, la ricorsione è fatta così:
Ribattezzo a.length con L per brevità
Caso base: L = 1
In questo caso si restituisce una matrice fatta con una riga e una colonna, nell'unica
cella della quale viene copiato l'unico valore di a.
Caso induttivo: L > 1 ed è una potenza perfetta
sia b = √L - 1 il lato del quadrato immediatamente più piccolo di quello di area L e sia Mb la matrice ottenuta applicando ricorsivamente il metodo all'array fatto dai
primi b elementi.
distribuirò i restanti r = L - b² = 2√L - 1 elementi una colonna a destra e una riga in basso rispetto a Mb, dall'alto in basso e poi da destra a sinistra.
Ad esempio, se ho L = 9, prima applico il metodo ricorsivamente sui primi b² = 4 elementi ottenendo un quadrato 2x2 (quello rosso in figura) e attorno a questo quadrato 2x2 metto gli altri 2√L - 1 = 5 elementi secondo l'ordine crescente delle lettere della figura:
(http://galileo.dmi.unict.it/utenti/reversengineer/pub/forum/attachments/2009-04-17/myorder.png)

Ho fatto questo codice (file ex.java):
Code:
import java.lang.reflect.Array;
import java.util.Arrays;
import java.lang.Math;


public class ex
{
public static Object [][] arrayToMatrix (Object [] a)
{
//nota bene: si suppone che a.length sia una potenza perfetta
Object [][] c;

//caso base: a.length == 1
if (a.length == 1)
//assegna a c il rif. ad un'array bidimensionale 1x1 e all'unica cella assegna il numero "a[0]" (in una sola statement! studiatevi il codice :-P)
((c = new Object [1][]) [0] = new Object [1]) [0] = a [0];
else //caso induttivo: a.length > 1 e potenza perfetta
{
//calcola L e b (come descritti nel post -sopra-)
int L = a.length;
int lato = (int) Math.sqrt (L);
int b = lato - 1;

//chiamata ricorsiva con un array di lunghezza pari a quella della più grande matrice quadrata che ha meno elementi di a
c = arrayToMatrix (Arrays.copyOf (a, b * b));

//estende l'array bidimensionale c aggiungendo una colonna a destra...
for (int i = 0; i < c.length; i++)
c [i] = Arrays.copyOf (c [i], lato);

//...e una riga in basso
c = Arrays.copyOf (c, lato);
c [lato - 1] = new Object [lato];

//e riempie tali nuove celle (prima la colonna a destra...
for (int i = 0; i < lato; i++)
c [i][b] = a [b * b + i];
//...e poi la riga in basso
for (int i = 0; i < lato - 1; i++) // mi fermo a (lato - 1) poiché l'angolino in basso a destra è stato riempito col for precedente
c [lato - 1][lato - 2 - i] = a [b * b + lato + i];
}

return c;
}

public static void main (String [] args)
{
//Array di esempio di simboli (cambiatelo a piacere ma mantenendolo di lunghezza pari a una quadrato perfetto, altrimenti il programma crasha!)
char [] x = {'c', 'i', ' ', 'a', 'a', 't', 'i', 't', 't', 'o', 'u', '!', ' ', 'P', '-', ':'};
Object [] ox = new Object [x.length];
for (int i = 0; i < x.length; i++) ox [i] = new Character (x [i]);

Object [][] c = arrayToMatrix (ox);

//visualizza la matrice
System.out.print ("  |");
for (int i = 0; i < c [0].length; i++)
System.out.print ((i < 10 ? " " : "") + i + " ");
System.out.println ();

System.out.print ("-+");
for (int i = 0; i < c [0].length; i++)
System.out.print ("---");
System.out.println ();

for (int i = 0; i < c.length; i++)
{
System.out.print ((i < 10 ? " " : "") + i + "|");
for (int j = 0; j < c [i].length; j++)
System.out.print (" " + c [i][j] + " ");

System.out.println ();
}
}
}


Title: Re:problema ricorsione esercizio 3
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 18-04-2009, 01:57:27
Ragazzi ho provato a fare il seguente esercizio ma mi da errore:
L'errore è causato dal fatto che il tuo metodo va in loop infinito.
Considera che l'unico ramo che porta a una chiamata ricorsiva, richiama la funzione con un input in cui al massimo sono cambiati dei valori dentro A o B, ma non il numero di righe o la lunghezza di una delle righe né di A né di B, e questi ultimi (numero di righe o lunghezza di una delle righe di A o di B) sono gli unici parametri su cui ci si basa per optare se, nel tuo metodo, bisogna fare la chiamata ricorsiva o si è nei casi base.