Auito algoritmo matrice

di il
11 risposte

Auito algoritmo matrice

Avrei bisogno di un aiuto
ho una matrice dove in ogni cella c'è un numero compreso tra 1 e 4

mi potreste consigliare un algoritmo che trova il più grande gruppo ke contiene lo stesso numero?

il gruppo è ottenuto dall'accostamente orizzontale o veticale di numeri uguali(nn vale quindi nella direzione diagonale)

11 Risposte

  • Re: Auito algoritmo matrice

    Ecco a te:
    i define N e M li ho impostati a 3 entrambi. Le variabili i e j sono per i cicli for.
    La variabile ris, che è uguale a 0 ogni volta che incomincia una nuova riga è il risultato. All'interno del for c'è l'if. Se ris è maggiore della somma, allora ris lo metto in somma, altrimenti cambio riga e ritorna ris=0. La somma è inizializzata 0 prima dei cicli perchè è la somma maggiore, quella da superare.
    #include <stdio.h>
    #include <stdlib.h>
    
    #define N 3
    #define M 3
    
    int main()
    {
        int mat[N][M];
        int i, j, somma, ris;
    
        for(i=0; i<N; i++)
        {
            for(j=0; j<M; j++)
            {
                printf("mat[%d][%d] = ", i, j);
                scanf("%d", &mat[i][j]);
            }
        }
    
        somma=0;
        for(i=0; i<N; i++)
        {
            ris=0;
            for(j=0; j<M; j++)
            {
                ris=ris+mat[i][j];
                if(ris>somma)
                {
                    somma=ris;
                }
            }
        }
        printf("Somma maggiore: %d", somma);
    
        return 0;
    }
    
  • Re: Auito algoritmo matrice

    Grazie mille,da quello che ho capito il tuo algoritmo mi calcola la somma massima per riga delle celle della matrice...però nn è quello a cui mi riferivo

    i numeri all'interno delle celle servono solo per differenziarle,potrebbero essere anche colori...
    quello a cui mi riferivo io è cercare in tutta la matrice il gruppo più grande che contiene lo stesso numero,ovviamente nel gruppo le celle uguali devono essere collegate,cioè adiacenti...il collegamento deve essere considerato solo se le celle uguali(cioè contenenti lo stesso numero) sono adiacenti verticalmente o orizzontalmente(se si toccano verticalmente nn conta)

    ...quindi potremmo avere gruppi di varia forma,per esempio a elle o un rettangolo,o un rettangolo cavo al centro...nn so se mi sono spiegato
  • Re: Auito algoritmo matrice

    Scusami ma non h capito proprio niente di quello che hai scritto...
  • Re: Auito algoritmo matrice

    Se per esempio ho una matrice fatta cosi:

    12323213223
    23212312322
    23123123132
    12323312131
    12331231111

    quell'insieme di "1" in basso a destra è il gruppo più grande che contiene lo stesso numero all'interno della matrice
    come faccio ad individuarlo?....poichè dovrei poi copiare sono quel gruppo di "1" in una seconda matrice...
  • Re: Auito algoritmo matrice

    Ciao alterind, vedo che sei nottambulo!

    Nell' esempio ho messo una matrice 10x10 contente un gruppo di tre elementi messo a elle (il 5), un gruppo di 4 elementi messo a quadrato (il 7) il resto è tutto a zero e forma un gruppo 93 elementi.

    Un insieme di celle uguali è stato chiamato Gruppo e viene tenuto un array di gruppi, per cui alla fine puoi vedere quanti e quali gruppi ci sono e che dimensione hanno.

    L' algoritmo è ricorsivo e per ogni cella cerca gli adiacenti uguali mettendo le loro coordinate (la struct Cell) in un array (la classe Group), ogni gruppo va a finire nell' array 'groups'.
    
    #include <iostream>
    #include <vector>
    using namespace std;
    
    struct Cell
    {
    	int x;
    	int y;
    	Cell(int ax, int ay) { x = ax; y = ay; }
    };
    
    class Group: public vector<Cell>
    {
    };
    
    class Raggruppateur
    {
    public:
    
    	static const int dimX = 10;
    	static const int dimY = 10;
    
    	int matrix[dimX][dimY];
    	int flags[dimX][dimY];
    
    	vector<Group> groups;
    
    public:
    	Raggruppateur()
    	{
    		for(int x = 0; x < dimX; ++x)
    			for(int y = 0; y < dimY; ++y)
    				matrix[x][y] = flags[x][y] = 0;
    	}
    
    	void Raggruppation()
    	{
    		for(int x = 0; x < dimX; ++x)
    			for(int y = 0; y < dimY; ++y)
    			{
    				if (flags[x][y] == 0)
    				{
    					groups.push_back(Group());
    					Raggruppation(x, y, matrix[x][y]);
    				}
    			}
    	}
    
    	void Add(int x, int y)
    	{
    		flags[x][y] = 1;
    		groups.back().push_back(Cell(x, y));
    	}
    
    	void Raggruppation(int x, int y, int seed)
    	{
    		if ((x < 0) || (y < 0) || (x >= dimX) || (y >= dimY))
    			return;
    
    		if ((matrix[x][y] != seed) || (flags[x][y] != 0))
    			return;
    
    		Add(x, y);
    		Raggruppation(x - 1, y, seed);
    		Raggruppation(x + 1, y, seed);
    		Raggruppation(x, y - 1, seed);
    		Raggruppation(x, y + 1, seed);
    	}
    };
    
    int main (void) 
    {
    	Raggruppateur r;
    	r.matrix[1][3] = r.matrix[2][3] = r.matrix[2][4] = 5;
    	r.matrix[5][6] = r.matrix[6][6] = r.matrix[5][7] = r.matrix[6][7] = 7;
    	r.Raggruppation();
    
    	for (vector<Group>::iterator it = r.groups.begin(); it != r.groups.end(); ++it) {
    		Cell c = *it->begin();
    		int n = r.matrix[c.x][c.y];
    		cout << n << " - "<< it->size() << endl;
    	}
    	
    	return 0;
    }
    
    La seconda matrice chiamata 'flags' serve per marcare quali celle sono già state raggruppate.

    Troverai dei nomi un pò stupidi e le classi scritte rozzamente (è tutto pubblico e inline) è l' effetto del caldo boia che c' è stato ieri.
    Comunque a te interessa solo l' algoritmo poi immagino organizzerai il codice diversamente.
  • Re: Auito algoritmo matrice

    Grazie mille dell'aiuto....suppongo nn sia scritto in C poichè sto trovando difficoltà a capirlo conoscendo solo il C come linguaggio di programmazione

    cercherò di spremermi un po'...
  • Re: Auito algoritmo matrice

    Ciao alterind
    quello strano linguaggio che vedi è il C++ Non avrai difficoltà a isolare l' algoritmo perchè non sfrutta caratteristiche particolari del C++ a parte le classi vector di cui volendo puoi fare a meno.
    Se ti serve una mano fa un fischio.
  • Re: Auito algoritmo matrice

    In realtà nn l'ho capito fino in fondo...sai,sono alle prime armi,ho dato solo un esame di programmazione..

    una veloce conversione in C,please ?
  • Re: Auito algoritmo matrice

    Ciao alterind
    volentieri, però prima dimmi esattamente cosa ti serve. Ad esempio in C++ mettevo da parte l' elenco di tutti i gruppi trovati ed ogni gruppo era l' elenco di celle che lo formavano, quasta cosa è semplice in C++ e complicata in C se non ti interessa non la scrivo.

    Per esempio quando chiedi di trovare il gruppo più grande cosa vuoi che ti sia restituito? Ti basta il numero di celle che lo compongono? Vuoi la posizione di dove inizia, ti serve un elenco di tutte le sue celle?
  • Re: Auito algoritmo matrice

    Avrei bisogno di tutte le celle che compongono il gruppo maggiore

    cmq il programma è in C anche perchè il C++ nn l'ho mai studiato,il mio precedente esame di informatica era in C...

    grazie mille per la disponibilità
  • Re: Auito algoritmo matrice

    Ti ho riscritto l' esempio senza classi e senza vector.
    La parte che riguarda il riempimento delle liste in C è piuttosto noiosa e te la lascio

    In questo modo l' algoritmo di ricerca dovrebbe essere chiaro, se non lo fosse chiedi pure.
    
    #include <stdio.h>
    
    struct Cell  // servirà come nodo della lista ... al momento non è usato
    {
       int x;
       int y;
       Cell* next;
    };
    
    #define dimX 10
    #define dimY 10
    
    Cell* group = NULL;
    int groupLength = 0;
    int maxGroupLength = 0;
    
    int matrix[dimX][dimY];
    int flags[dimX][dimY];
    
    void ClearMatrix()
    {
          for(int x = 0; x < dimX; ++x)
             for(int y = 0; y < dimY; ++y)
                matrix[x][y] = flags[x][y] = 0;
    }
    
    void NewGroup()
    {
    	// da fare ... crea una nuova lista 
    	
    	if (groupLength > maxGroupLength)
    		maxGroupLength = groupLength;
    
    	groupLength = 0;
    }
    
    void ClearGroup()
    {
    	// da fare ... svuota la lista ed elimina i nodi
    	
    	groupLength = 0;
    }
    
    void GroupAdd(int x, int y)
    {
        ++groupLength;
    
    	// da fare aggiunge un nodo alla lista.
    }
    
    void ToGroup(int x, int y, int seed)
    {
        if ((x < 0) || (y < 0) || (x >= dimX) || (y >= dimY))
            return;
    
        if ((matrix[x][y] != seed) || (flags[x][y] != 0))
            return;
    
        flags[x][y] = 1;
           GroupAdd(x, y);
    
        ToGroup(x - 1, y, seed);
        ToGroup(x + 1, y, seed);
        ToGroup(x, y - 1, seed);
        ToGroup(x, y + 1, seed);
    }
    
    void ToGroup()
    {
        for(int x = 0; x < dimX; ++x)
            for(int y = 0; y < dimY; ++y)
            {
    			if (flags[x][y] == 0)
    			{
    				NewGroup();
    				ToGroup(x, y, matrix[x][y]);
    			}
            }
    }
    
    int main (void) 
    {
       ClearMatrix();
    
       matrix[1][3] = matrix[2][3] = matrix[2][4] = 5;
       matrix[5][6] = matrix[6][6] = matrix[5][7] = matrix[6][7] = 7;
       ToGroup();
    
       printf("Max group length %d",  maxGroupLength);
    
       return 0;
    }
    
    Questa versione trova il gruppo più grande e ne scrive la dimensione, ho lasciato vuote le funzioni per le liste, se hai problemi su questa parte dato che è un argomento diverso ti conviene aprire un nuovo thread.
Devi accedere o registrarti per scrivere nel forum
11 risposte