Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 1, 9 CFU => Topic started by: Jack&Daxter on 17-01-2011, 18:41:13



Title: Somma diagonali matrice
Post by: Jack&Daxter on 17-01-2011, 18:41:13
Ragazzi qualcuno di voi è riuscito a fare l'esercizio che somma le diagonali parallele di una matrice??


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-01-2011, 18:46:21
Non ho ben chiaro cosa siano "LE" diagonali parallele in una matrice...

Puoi postare il testo completo? Magari riesco a trovarti una soluzione .penso...


Title: Re:Somma diagonali matrice
Post by: Jack&Daxter on 17-01-2011, 18:51:08
Data una matrice quadrata di int dire se esiste una diagonale parallela alla principale (inclusa la principale stessa) tale che la somma dei suoi elementi sia divisibile per 5


Title: Re:Somma diagonali matrice
Post by: Luxandro on 17-01-2011, 19:59:19
Ciao salvo!  .ciaociao

Io ho risolto così...

Code:
boolean metodo(int [][] A)
{
int s1 = 0, s2 = 0, s3 = 0;
for(int i = 0; i < A.length; i++)
{
s1 += A [i][i];        //somma relativa alla diagonale principale
for(int x = i+1, y = 0; (x < A.length-1)&&(y < A.length); x++, y++)
{
s2 += A [x][y]; //s2:somma delle diagonali parallele sottostanti la diagonale principale
        s3 += A [y][x]; //s3:somma delle diagonali parallele sovrastanti la diagonale principale
}
if(s2 % 5 == 0)  return true;    else if(s3 % 5 == 0)  return true;
}
if(s1 % 5 == 0)  return true;
return false;
}


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-01-2011, 21:06:17
Ciao salvo!  .ciaociao

Io ho risolto così...
[...]
Il tuo codice è errato .sisi.

In pratica quando calcola la somma dei valori delle diagonali parallele alla principale (esclusa la principale), si dimentica di aggiungere l'ultimo elemento in basso a destra, col risultato che è come se ignorasse la presenza dell'ultima riga e dell'ultima colonna (tranne per l'elemento nell'angolo in basso a destra, che viene sommato in un codice diverso).

L'errore è facilmente rimovibile cancellando quel -1 nella prima parte della condizione di uscita del ciclo for:
Code:
for(int x = i+1, y = 0; (x < A.length-1)&&(y < A.length); x++, y++)
ottenendo:
Code:
for(int x = i+1, y = 0; x < A.length && y < A.length; x++, y++)


Title: Re:Somma diagonali matrice
Post by: Jack&Daxter on 18-01-2011, 01:07:26
Grazie per l'aiuto ragazzi !!!! Siete stati davvero utili !!


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 18-01-2011, 02:05:07
Non so se il mio algoritmo (e il relativo codice) sarà più intuitivo rispetto a quello di Luxandro, ma almeno nella mia testa lo è .sisi.

L'idea di fondo è semplice:
1) si enumerano le diagonali parallele alla principale (inclusa la principale), che sono in numero finito (se la matrice è di tipo N\times N ci saranno esattamente 2\cdot N-1 diagonali parallele alla principale, inclusa la principale);
2) dopodiché si passano in rassegna tutte queste diagonali e si calcolano le coordinate dell'elemento che sta più in alto a sinistra nella diagonale con indice i considerata (che sono \({X, Y}\)\equiv\({\max\{{i - \({N - 1}\), 0}\},\;\max{\{(N - 1) - i, 0\}}\));
3)a partire da questo elemento si sommano i contributi di tutti gli altri elementi della stessa diagonale (gli altri elementi si trovano facilmente incrementando entrambe le coordinate/indici \({X, Y}\) del nuovo elemento da sommare finché si resta entro la matrice).
4)controllo banale: se questa somma è divisibile per 5 allora si fa in modo che tutto il metodo ne sia informato (si noti l'eleganza e l'utilità di avere un'unico punto di restituzione valore -return- in tutto il codice .sisi).

Ecco il codice:
Code:
    boolean metodo2 (int [][] A)
    {
        boolean found = false;

        for (int i = 0, max = 2 * A.length - 1; i < max && !found; i++)
        {
            int sum = 0;

            for (int iX = Math.max (i - (A.length - 1), 0), iY = Math.max ((A.length - 1) - i, 0); iX < A.length && iY < A.length; iX++, iY++)
                sum += A [iY][iX];
            found = (sum % 5) == 0;
        }
       
        return found;
    }


Title: Re:Somma diagonali matrice
Post by: Impact on 21-01-2011, 16:46:34
Per me è arabo! ahahahah


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-01-2011, 23:30:53
Per me è arabo! ahahahah
Considera che una volta data la materia, dovrai essere perfettamente in grado di poter leggere un codice come qualsiasi, o comunque riscrivertelo in modo da leggerlo meglio tu (ma per poterlo riscrivere devi capire come è strutturato in ogni caso).

Per adesso, te lo riscrivo io in modo più leggibile ma meno ottimizzato:
Code:
    boolean metodo2leggibile (int [][] A)
    {
        boolean found = false;

        //i indica la i-esima diagonale parallela alla principale
        for (int i = 0, max = 2 * A.length - 1;
             i < max && !found; i++)
        {
            //si inizializza la somma a zero inizialmente
            int sum = 0;

            int iX = Math.max (i - (A.length - 1), 0);  //iX è l'indice di colonna dell'elemento più in alto a sinistra della i-esima diagonale parallela alla principale
            int iY = Math.max ((A.length - 1) - i, 0);  //iY è l'indice di riga dell'elemento più in alto a sinistra della i-esima diagonale parallela alla principale
           
            //questo ciclo incrementa di volta in volta iX e iY di una unità, cioè fa scorrere al prossimo elemento della i-esima diagonale parallela alla principale
            for (; iX < A.length && iY < A.length; iX++, iY++)
                //e ne aggiunge il contributo alla somma
                sum += A [iY][iX];
               
            found = (sum % 5) == 0;     //quando (sum % 5) == 0 è vero, allora anche found è vero; quando è falso, anche found è falso
        }
       
        return found;
    }


Title: Re:Somma diagonali matrice
Post by: StephCT on 21-01-2011, 23:56:56
per me nn era arabo il codice in sè, ma l'operazione contorta per scorrere gli elementi in diagonale xD questo tuo codice mi pare di capire che è abbastanza legato al contesto delle matrici quadrate. e se dovesse succedere di calcolarla in una matrice generica? quindi che potrebbe essere quadrata o rettangolare...


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-01-2011, 01:32:48
OK. Nel caso di matrici qualsiasi (quindi genericamente rettangolari, ricordando che anche i quadrati sono casi particolari di rettangoli) la logica rimane la stessa, cioè enumero le diagonali orientate a \frac{3}{4}\pi radianti) e poi in \({iX, iY}\) calcolo di volta in volta gli indici del primo elemento in alto a sinistra di tale diagonale, ma stavolta lo calcolo nel modo più semplice, cioè seguendo il margine sinistro (prima) e poi superiore (poi) della matrice, un elemento alla volta (il successivo elemento si troverà incrementando \({iX, iY}\) del vettore \({incX, incY}\), che cambierà il suo valore quando si giunge al vertice top-left); il resto è uguale, si scorrrono tutti gli elementi di tale diagonale finché si rimane all'interno della matrice e poi si verifica la divisibilità della somma dei suoi elementi per 5;

Ho preparato due codici che sviluppano questa idea; il seguente è quello leggibile |-O:
Code:
   boolean metodoMatriciRettangolariLeggibile (int [][] A)
    {
        boolean found = false;

        int max = A.length + A [0].length - 1;
        int i = 0;
        
        int iX = 0;
        int iY = A.length - 1;
        
        int incX = 0;
        int incY = -1;
        
        while (i < max && !found)
        {
            int sum = 0;
            
            for (int x = iX, y = iY; x < A [0].length && y < A.length; x++, y++)
                sum += A [y][x];
            
            found == (found % 5) == 0;

            iX += incX;
            iY += incY;
            
            if (iX == 0 && iY == 0)
            {
                incX = 1;
                incY = 0;
            }
        }
        
        return found;
    }
e questo è quello poco leggibile:
Code:
   boolean metodoMatriciRettangolariIlleggibile (int [][] A)   //ILLEGIBILE :D
    {
        boolean found = false;

        for (iX = 0, iY = A.length - 1, incX = 0, incY = -1; iX < A [0].length && !found; iX += incX, iY += incY)
        {
            int sum = 0;
            
            for (int x = iX, y = iY; x < A [0].length && y < A.length; x++, y++)
                sum += A [y][x];
                
            found = (sum % 5) == 0;
            
            if (iX == 0 && iY == 0)
            {
                incX = 1; incY = 0;
            }
        }
    }
ma in cui mi sono sbarazzato di i e max, e ho sostituito il low-level while con un più elegante for, ed è più compatto  .wink :-OK.

Sto pensando anche a una versione basata su quest'ultimo codice reintroducendo i e max, eliminando x e y, e in cui iX e iY siano direttamente dipendenti da i... .penso .leggo .sisi


Title: Re:Somma diagonali matrice
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-01-2011, 01:53:21
Sto pensando anche a una versione basata su quest'ultimo codice reintroducendo i e max, eliminando x e y, e in cui iX e iY siano direttamente dipendenti da i... .penso .leggo .sisi
Che bello, ci sono riuscito  .smile!

Questo è il codice che avevo in testa:
Code:
   boolean metodo2 (int [][] A)
    {
        boolean found = false;

        for (int i = 0, max = A.length + A [0].length - 1; i < max && !found; i++)
        {
            int sum = 0;

            for (int iX = Math.max (i - (A.length - 1), 0), iY = Math.max ((A.length - 1) - i, 0); iX < A.length && iY < A.length; iX++, iY++)
                sum += A [iY][iX];
            found = (sum % 5) == 0;
        }
        
        return found;
    }
Che è il codice postato per primo in questa discussione al 99,9%!!!
Rispetto al primissimo codice postato in questa discussione, cambia solo l'inizializzazione di max, che è più generale e comprende le versioni rettangolari qualsiasi (quindi anche quella quadrata in cui max era una specializzazione, nel cui caso
A [0].length == A.length \RightarrowA [0].length + A.length = 2 * A.length).

Si vede che il primissimo codice era stato veramente ben pensato, altro che arabo .coolio...
Meditate gente, meditate :-ciao...


Title: Re:Somma diagonali matrice
Post by: mr.ben on 22-01-2011, 02:06:30
 .quoto


Title: Re:Somma diagonali matrice
Post by: StephCT on 22-01-2011, 10:46:21
scorrendo la pagina ti volevo già scrivere: ma invece di complicarti la vita xkè nn hai riadattato quello dei quadrati=? XD xkè ci avevo pensato prima di prendere sonno e bastava cambiare il max e operava ugualmente xD

bella! cmq grazie :-)


Title: Re:Somma diagonali matrice
Post by: StephCT on 22-01-2011, 18:09:57
Code:
boolean metodo (int [][] A)
{
int i=A.length-1, cont=0, diagonali=A.length+A[0].length-1;
while(cont<diagonali)
{
int sum=0;
int x = (i>0) ? i-- : 0;
int j = (x>0) ? 0 : (diagonali-cont-1);
while(x<A.length && j<A[0].length)
{
sum+=A[x][j];
x++;
j++;
}
if(sum%5==0)
return true;
else
cont++;
}
return false;
}

siccome nn mi riesco a capacitare di quale regola si usi per fare quell'assegnamento xD, volevo proporre anche questa soluzione perchè è l'unica cn la quale riesco a organizzare la mia testa :D