[Risolto] [C][Matrici] Trovare i MAX riga-colonna

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Scrivi risposta
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

[Risolto] [C][Matrici] Trovare i MAX riga-colonna

Messaggio da zangetsu94 »

Mi servirebbe un algoritmo che mi permette di calcolare, se esiste, che sia contemporaneamente il più grande sulla propria riga e sulla propria colonna. E che mi permetta di stampare posizione e valore.

Avevo iniziato con una semplice matrice 4x4 con valori preinseriti prima di generalizzare il tutto, ma purtroppo non riesco a far andar bene il confronto tra valori e la stampa...
Sbaglio qualcosa nell'algoritmo

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#define R 4 //righe
#define C 4 //colonne

int main()
{
int v[R][C]={{1,2,3},{8,10,9},{11,0,66,25},{11,25,11,25}},  //valori messi a caso
int max;
int i,  j; //coordinate valori matrice. Riga i-esima, colonna j-esima


        max=v[0][0]; 
        for (i=0; i<R; i++)
        {
            for(j=0; j<C; j++)
            {
                if (v[i][j]>=max)
                {
                    max=v[i][j];
                    for (i=i; i<R; i++)
                    {
                        if (v[i][j]>max)
                        {
                            max=v[i][j];
                            printf("Massimo riga colonna %d in posizione (%d, %d)\n", max, i, j);
                        }
                    }
                }
            }
            max=v[0][0];
        }

    return 0;
}
Grazie in anticipo :birra:
Ultima modifica di zangetsu94 il martedì 19 maggio 2015, 21:31, modificato 2 volte in totale.
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Avatar utente
crap0101
Rampante Reduce
Rampante Reduce
Messaggi: 8242
Iscrizione: martedì 30 ottobre 2007, 6:33
Desktop: LXDE
Distribuzione: Ubuntu 18.04.1 LTS
Sesso: Maschile
Località: TO
Contatti:

Re: [C][Matrici] Trovare MAX riga-colonna

Messaggio da crap0101 »

zangetsu94 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4758566#p4758566][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Mi servirebbe un algoritmo che mi permette di calcolare, se esiste, che sia contemporaneamente il più grande sulla propria riga e sulla propria colonna. E che mi permetta di stampare posizione e valore.
Non sono sicuro di aver capito bene: vuoi trovare, nella matrice, il numero che è il maggiore tra i numeri della riga in cui si trova e anche tra i numeri della colonna in cui si trova?
Se è così ti stai complicando la vita :-) perchè il numero che cerchi è semplicemente il più grande che c'è in *tutta* la matrice, per cui non devi far altro che scorrere gli ememtni e registrare la posizione di quello maggiore, ogni volta che ne trovi uno. Per cui, nel tuo codice, il for più interno è inutile. E poi, perchè per ogni riga resetti max

Codice: Seleziona tutto

max=v[0][0];
?
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

Re: [C][Matrici] Trovare MAX riga-colonna

Messaggio da zangetsu94 »

Vorrei trovare i numeri che hanno quella caratteristica ad esempio:

0 0 0 1 1 0 0 0
0 1 4 3 2 2 0 0
1 2 5 2 2 4 1 1
1 1 2 2 3 2 1 0
0 0 0 2 1 1 0 0

In tale matrice i numeri evidenziati hanno quella caratteristica. Ecco perché alla fine resetto il max. Non cerco il max assoluto. :)
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da M_A_W_ 1968 »

L'algoritmo cercato è piuttosto banale e richiede, nella sua versione più intuitiva, due passi e due array di appoggio, di dimensioni rispettivamente pari al numero di righe e di colonne della matrice.

Si tratta banalmente di cercare iterativamente il massimo di ogni colonna (per fissare le idee) e, per ogni colonna, memorizzarlo nel primo array. Successivamente si ripete la medesima scansione, ma per righe, memorizzando per ciascuna di esse il relativo massimo in una locazione dell'array (indicizzata col numero di riga, in questo caso).

Come step finale, si scansiona l'array dei massimi caratterizzato da dimensione minore (infatti la richiesta che r=c limita di fatto la scansione alla sottomatrice quadrata massimale sinistra della matrice data!). Per ogni locazione i-esima, se la corrispondente locazione nell'altro array dei massimi contiene il medesimo valore, allora siamo in presenza di una cella con le caratteristiche desiderate.

In colore blu sono riportati gli array di appoggio richiesti dall'algoritmo, nella versione più elementare. I valori tra parentesi risultano esclusi dal confronto finale, come già sottolineato.

0 0 0 1 1 0 0 0 1
0 1 4 3 2 2 0 0 4
1 2 5 2 2 4 1 1 5
1 1 2 2 3 2 1 0 3
0 0 0 2 1 1 0 0 2
1 2 5 3 3(4 1 1)
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da Claudio_F »

Per ogni locazione i-esima, se la corrispondente locazione nell'altro array dei massimi contiene il medesimo valore, allora siamo in presenza di una cella con le caratteristiche desiderate
Non basta, così risulterebbe un massimo '1' anche in riga 0 colonna 0, e i valori verrebbero sempre segnalati lungo la diagonale.
Se non sbaglio una volta ottenuti gli array dei massimi di ogni riga e di ogni colonna bisogna anche iterare l'intera matrice per vedere se quei massimi, oltre ad essere uguali, coincidono anche come coordinate.

Un algoritmo Python da dui prendere spunto può essere il seguente:

Codice: Seleziona tutto

data = ( (0, 0, 0, 1, 1, 0, 0, 0),
         (0, 1, 4, 3, 2, 2, 0, 0),
         (1, 2, 5, 2, 2, 4, 1, 1),
         (1, 1, 2, 2, 3, 2, 1, 0),
         (0, 0, 0, 2, 1, 1, 0, 0) )

max_rows = [max(row) for row in data]        # massimi delle righe
max_cols = [max(col) for col in zip(*data)]  # massimi delle colonne
for y in range(len(data)):                   # scansione righe
    for x in range(len(data[0])):            # scansione colonne
        if max_rows[y] == data[y][x] == max_cols[x]:
            print('row=%2d  col=%2d  n=%2d' % (y, x, data[y][x]))
Risultato:

Codice: Seleziona tutto

row= 2  col= 2  n= 5
row= 3  col= 4  n= 3
Ultima modifica di Claudio_F il domenica 17 maggio 2015, 14:21, modificato 2 volte in totale.
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da M_A_W_ 1968 »

Claudio_F [url=http://forum.ubuntu-it.org/viewtopic.php?p=4758644#p4758644][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: Non basta, così risulterebbe un massimo '1' anche in riga 0 colonna 0, e i valori verrebbero sempre segnalati lungo la diagonale.
La prima considerazione è corretta, ma rientra perfettamente nella definizione data dall'OP, che nel caso dovrà meglio ripensare alla sua specifica e alla gestione delle molteplcità. Il valore 1, stando alla richiesta. è effettivamente valore massimo comune per riga zero e colonna zero, sebbene non evidenziato nell'esempio. Secondo l'implementazione, in tale caso occorre scegliere se si vuole che venga segnalato il valore con la coordinata massima, o quello con la coordinata minima, o (con un po' più di lavoro) tutti i valori duplicati per riga e colonna. Pare comunque di capire, pur se lasciato implicito dall'OP, che un caso siffatto sia altamente degenere per la natura dei dati trattati (anche se è doveroso prevederlo, e banale trattarlo).

La seconda, invece, non si applica. L'esempio anzi illustra chiaramente il contrario. La procedura semplificata in O(N^2) copre già ambedue i casi di massimo locale: sia quelli appartenenti alla diagonale principale che i valori duplicati, ossia coppie di valori identici aventi coordinate di tipo (a,b) e (b,c). Ma probabilmente intendevi riferirti al fatto che l'algoritmo e le strutture dati vanno leggermente complessificate se si intende segnalare, oltre al valore massimo comune, anche la relativa posizione nella matrice di partenza. Risulta comunque sufficiente memorizzare, durante le scansioni per righe e per colonne, le coordinate di ogni massimo relativo, sovrascrivendole alle vecchie in modo da avere, al termine di ciascuna iterazione dell'outer loop, valore e coordinate (di prima o ultima occorrenza, secondo il verso della scansione) di ogni massimo locale.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da Claudio_F »

L' OP dovrebbe specificare se l'output per la seguente matrice è corretto, ovvero se è possibile che in una riga o in una colonna vi siano più massimi:

0 0 0 1 3 0 0 0 3
0 1 4 3 2 2 0 0 4
1 5 5 5 2 4 1 1 5
1 1 2 2 3 2 1 0 3
1 0 0 1 1 1 0 1 1
1 5 5 5 3 4 1 1

Codice: Seleziona tutto

row= 0  col= 4  n= 3
row= 2  col= 1  n= 5
row= 2  col= 2  n= 5
row= 2  col= 3  n= 5
row= 3  col= 4  n= 3
row= 4  col= 0  n= 1
row= 4  col= 7  n= 1
Ultima modifica di Claudio_F il domenica 17 maggio 2015, 14:23, modificato 2 volte in totale.
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da M_A_W_ 1968 »

Credo che questo banale esempio di codice servirà a chiarire all'OP cosa si ottiene applicando la sua specifica così come esposta ed esemplificata. Per la sua caratteristica intrinseca, il codice proposto segnala unicamente l'occorrenza a coordinate minori di un eventuale massimo multiplo di riga e di colonna. Gestire esplicitamente molteplicità superiori è comunque puerile, si va dalla peggiore soluzione (gli array dei massimi locali diventano array di puntatori a schifezzuole di liste linkate semplici di strutture coord_t) a quella più elegante (per ogni entry dei vettori dei massimi relativi, un bit array mappa tutte le locazioni di riga o di colonna ove appaiono i valori duplicati), con sfumature per tutti i gusti.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

const size_t ASIZE = 8;

typedef struct
{
    unsigned char R, C;
    int val;
} coord_t;

int main()
{
    int my_array[ASIZE][ASIZE];
    coord_t Rmax[ASIZE], Cmax[ASIZE];
    size_t i, j;

    srand(time(NULL));

    /* Popolazione dell'array */
    for (i = 0; i < ASIZE; ++i)
    {
        Rmax[i].val = INT_MIN;
        Cmax[i].val = INT_MIN;
        for (j = 0; j < ASIZE; ++j)
        {
            /* Si genera arbitrariamente un valore in  [10, 99] */
            my_array[i][j] =  rand() % 90 + 10;
        }
    }

    /* Scansione massimi per colonne */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            if (my_array[i][j] > Rmax[i].val)
            {
                Rmax[i].val = my_array[i][j];
                Rmax[i].R = (char)i;
                Rmax[i].C = (char)j;
            }
        }
    }

    /* Scansione massimi per righe */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            if (my_array[j][i] > Cmax[i].val)
            {
                Cmax[i].val = my_array[j][i];
                Cmax[i].R = (char)j;
                Cmax[i].C = (char)i;
            }
        }
    }

    /* Visualizzazione array */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            printf("%2d ", my_array[i][j]);
        }
        printf(" %2d\n", Rmax[i].val);
    }
    puts("");
    for (i = 0; i < ASIZE; ++i)
    {
        printf("%2d ", Cmax[i].val);
    }
    puts("");

    /* Scansione array dei massimi per riga e colonna */
    puts("\n> Valori massimi comuni per una data riga e colonna:");
    for (i = 0; i < ASIZE; ++i)
    {
        if (Cmax[i].val == Rmax[i].val)
        {
            printf("(%d) %2d my_array[%d][%d]",
                   i, Rmax[i].val, Rmax[i].R, Rmax[i].C);
            if (Rmax[i].R != Rmax[i].C)
            {
                printf(", my_array[%d][%d]", Cmax[i].R, Cmax[i].C);
            }
            puts("");
        }
    }

    return 0;
}
Ecco un test run, si noti come i valori sono ovviamente tutti pseudorandom.

92 34 58 32 55 14 52 71 92
37 92 33 19 17 79 69 38 92
53 67 96 58 22 29 19 55 96
13 19 89 46 10 83 79 19 89
84 79 54 40 56 88 38 83 88
30 93 22 27 88 97 91 33 97
87 55 49 11 40 96 70 91 96
73 88 42 52 83 89 63 13 89
92 93 96 58 88 97 91 91

> Valori massimi comuni per una data riga e colonna:
(0) 92 my_array[0][0]
(2) 96 my_array[2][2]
(4) 88 my_array[4][5], my_array[5][4]
(5) 97 my_array[5][5]
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da zangetsu94 »

Alla fine seguendo il consiglio iniziale di @M_A_W ho fatto così:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#define R 4
#define C 4

int main()
{
int v[R][C]={{1,2,3},{8,0,9,0},{11,0,66,10},{11,25,11,0}}, v1[R], v2[C], max, i, j;

        max=v[0][0];
        for (i=0; i<R; i++)
        {
            for (j=0; j<C; j++)
            {
                if (i>0)
                {
                    max=v[i][0];
                }
                for(j=0; j<C; j++)
                {
                    if (v[i][j]>=max)
                    {
                        max=v[i][j];
                    }
                }
            }
            v1[i]=max;
        }
        for (j=0; j<C; j++)
        {
            max=v[0][j];
            for (i=0; i<R; i++)
            {
                for (i=0; i<R; i++)
                {
                    if (v[i][j]>=max)
                    {
                        max=v[i][j];
                    }
                }
            }
            v2[j]=max;
        }
        for (i=0; i<R; i++)
        {
            for (j=0; j<C; j++)
            {
                if (v1[i]==v2[j])
                {
                    printf("L'isola può sorgere sul valore %d di coordinate (%d,%d)\n\n", v1[i], i, j);
                }
            }
        }

    return 0;
}
L'unico problema, è che se sono presenti più massimi uguali sulla stessa riga e colonna diversa -o viceversa- non so come fare in quanto la dimensione degli array varierebbe.
Dovrebbe andare bene anche per matrici non quadrate.
Potete dirmi se va bene? Se sono presenti errori concettuali o altro?
Vi ringrazio per quello che avete già fatto. :)
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C][Matrici] Trovare i MAX riga-colonna

Messaggio da M_A_W_ 1968 »

La gestione di reiterati massimi locali (caso limite: la matrice contiene il medesimo valore in ogni cella!) è piuttosto banale, ma devi decidere tu in che modo gestire tali collisioni.

Questo è un codice d'esempio che usa una delle soluzioni più eleganti in assoluto, un bit array, per mappare tutte le eventuali occorrenze di un dato massimo relativo nella sua riga o colonna.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

const size_t ASIZE = 8;

/* 
** Abilitare qui o da command line per ottenere il conteggio dei valori massimi duplicati
** #define COUNT_MULTIPLES
 */

/* Per forzare molti valori uguali, si comprime l'intervallo per il RNG */
#ifdef COUNT_MULTIPLES
 #define RND_LIMIT 6
#else
 #define RND_LIMIT 90
#endif

typedef unsigned char uchar;
typedef struct
{
    uchar   R, C;
    int     val;
#ifdef COUNT_MULTIPLES
    size_t  bmap;
#endif
} coord_t;

int main()
{
    int my_array[ASIZE][ASIZE];
    coord_t Rmax[ASIZE], Cmax[ASIZE];
    size_t i, j;

    srand(time(NULL));

    /* Popolazione dell'array */
    for (i = 0; i < ASIZE; ++i)
    {
        Rmax[i].val  = INT_MIN;
        Cmax[i].val  = INT_MIN;

#ifdef COUNT_MULTIPLES
        Rmax[i].bmap = 0;
        Cmax[i].bmap = 0;
#endif

        for (j = 0; j < ASIZE; ++j)
        {
            my_array[i][j] = rand() % RND_LIMIT + 10;
        }
    }

    /* Scansione massimi per colonne */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            if (my_array[i][j] > Rmax[i].val)
            {
                Rmax[i].val = my_array[i][j];
                Rmax[i].R = (uchar)i;
                Rmax[i].C = (uchar)j;
            }
        }
    }
#ifdef COUNT_MULTIPLES
    for (i = 0; i < ASIZE; ++i)
    {
        register size_t b = 1;
        for (j = 0; j < ASIZE; ++j)
        {
            if ((j != Rmax[i].C) && (my_array[i][j] == Rmax[i].val))
            {
                Rmax[i].bmap |= b;
            }
            b <<= 1;
        }
    }
#endif

    /* Scansione massimi per righe */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            if (my_array[j][i] > Cmax[i].val)
            {
                Cmax[i].val = my_array[j][i];
                Cmax[i].R = (uchar)j;
                Cmax[i].C = (uchar)i;
            }
        }
    }
#ifdef COUNT_MULTIPLES
    for (i = 0; i < ASIZE; ++i)
    {
        register size_t b = 1;
        for (j = 0; j < ASIZE; ++j)
        {
            if ((j != Cmax[i].R) && (my_array[j][i] == Cmax[i].val))
            {
                Cmax[i].bmap |= b;
            }
            b <<= 1;
        }
    }
#endif

    /* Visualizzazione array */
    for (i = 0; i < ASIZE; ++i)
    {
        for (j = 0; j < ASIZE; ++j)
        {
            printf("%2d ", my_array[i][j]);
        }
        printf(" %2d\n", Rmax[i].val);
    }
    puts("");
    for (i = 0; i < ASIZE; ++i)
    {
        printf("%2d ", Cmax[i].val);
    }
    puts("");

    /* Scansione array dei massimi per riga e colonna */
    puts("\n> Valori massimi comuni per una data riga e colonna:");
    for (i = 0; i < ASIZE; ++i)
    {
        if (Cmax[i].val == Rmax[i].val)
        {
            printf("(%d) %2d r = %d, c = %d",
                   i, Rmax[i].val, Rmax[i].R, Rmax[i].C);

#ifdef COUNT_MULTIPLES
            if (Rmax[i].bmap > 0)
            {
                int k = 0;
                for (j = 1; j < INT_MAX; j <<= 1)
                {
                    if (Rmax[i].bmap & j)
                    {
                        printf(", %d", k);
                    }
                    ++k;
                }
            }

            if ((Rmax[i].R != Rmax[i].C) || (Cmax[i].bmap > 0))
            {
                printf("\n       c = %d, r = %d", Cmax[i].C, Cmax[i].R);
            }
            if (Cmax[i].bmap > 0)
            {
                int k = 0;
                for (j = 1; j < INT_MAX; j <<= 1)
                {
                    if (Cmax[i].bmap & j)
                    {
                        printf(", %d", k);
                    }
                    ++k;
                }
            }
#else
            if (Rmax[i].R != Rmax[i].C)
            {
                printf("\n       c = %d, r = %d", Cmax[i].C, Cmax[i].R);
            }
#endif
            puts("");
        }
    }

    return 0;
}
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 7 ospiti