Pages: [1]   Go Down
Print
Author Topic: Somma diagonali matrice  (Read 3583 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Jack&Daxter
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 398



« on: 17-01-2011, 18:41:13 »

Ragazzi qualcuno di voi è riuscito a fare l'esercizio che somma le diagonali parallele di una matrice??
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #1 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 ...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Jack&Daxter
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 398



« Reply #2 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
Logged
Luxandro
Apprendista Forumista
**
Offline Offline

Posts: 307



« Reply #3 on: 17-01-2011, 19:59:19 »

Ciao salvo!  

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;
}
« Last Edit: 17-01-2011, 20:17:24 by Luxandro » Logged

"Quando non stai guardando è come un'onda. Quando guardi è come una particella!"
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 17-01-2011, 21:06:17 »

Ciao salvo!  

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

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++)
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Jack&Daxter
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 398



« Reply #5 on: 18-01-2011, 01:07:26 »

Grazie per l'aiuto ragazzi !!!! Siete stati davvero utili !!
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #6 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 è .

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 ).

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;
    }
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Impact
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 107



« Reply #7 on: 21-01-2011, 16:46:34 »

Per me è arabo! ahahahah
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #8 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;
    }
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
StephCT
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #9 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...
Logged

"Che la Forza sia con Te"
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #10 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 univ:
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   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...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #11 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...
Che bello, ci sono riuscito  !

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 ...
Meditate gente, meditate ciao...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
mr.ben
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 131


« Reply #12 on: 22-01-2011, 02:06:30 »

 
Logged
StephCT
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #13 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 :-)
Logged

"Che la Forza sia con Te"
StephCT
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #14 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 Cheesy
Logged

"Che la Forza sia con Te"
Pages: [1]   Go Up
Print
Jump to: