Trovare in un vettore il valore con il numero massimo di rip

di il
5 risposte

Trovare in un vettore il valore con il numero massimo di rip

Salve ragazzi,come da titolo,mi serve un aiutino con questo quesito:
(Il vettore è di interi)
Il codice che ho provato è il seguente:
int contatori[Max_Dim];
for(int i=0;i<dim;i++)
{for(int j=0;j<dim;j++)
{
if(vettore==vettore[j])
contatori++
}
int posMax=0;
for(int i=1;i< dim;i++)
{if(contatori>contatori[posMax])
posMax=i;
}

cout<<"Il valore"<< vettore[posMax]<< "si ripete"<<contatori[posMax] -1
Però non mi convince più di tanto,in primis perchè confronto ogni valore con sè stesso e quindi per stampare il risultato corretto di ripetizioni lo devo diminuirlo di 1 e secondo perchè se ho un vettore del tipo "1 4 4 1",otterrei un vettore "2 2 2 2",quando mi sarebbero bastati solo due indici...
Avevo pensato ad una struct del tipo:
typedef struct
{
int num;
int rip;
}valore;
per identificare per ogni valore una struttura da cui posso attingere subito al numero di ripetizioni senza crearne di superflue
Però il professore vuole che questo esercizio venga svolto solo con i vettori..:S
Grazie in anticipo per le vostre risposte

5 Risposte

  • Re: Trovare in un vettore il valore con il numero massimo di rip

    Ciao,
    adesso controllo meglio il tuo codice, però un altro approccio sarebbe quello di ordinare il vettore (con l'algoritmo che vuoi). Dopo diventa semplicissimo capire qual è il valore che si ripete più volte.
  • Re: Trovare in un vettore il valore con il numero massimo di rip

    Se l'intervallo di valori ammessi è limitato potresti usare il counting sort fermandoti già al primo passaggio.

    Oppure come detto da minomic puoi ordinarlo e poi scandirlo usando solo 2 contatori (il primo contiene il massimo numero di ripetizioni fino a quel momento, il secondo contiene le ripetizioni del valore che si sta scandendo. Però così perdi tempo con un algoritmo di ordinamento che ha nel migliore dei casi un costo linearitmico, mentre la prima soluzione è lineare (scandisci una volta il vettore di partenza e una volta il vettore dei contatori (che possiamo sperare sia più piccolo dell'altro).

    ciao.
  • Re: Trovare in un vettore il valore con il numero massimo di rip

    Ho buttato giù due righe tentando qualche ottimizzazione
    
    #include <stdlib.h>
    #include <stdio.h>
    
    #define MAXDIM 10
    
    int main()
    {
    
    	int vettore[MAXDIM] = {3, 3, 3, 2, 2, 4, 4, 4, 7, 3};
    	int max = 0;
    	int best = 0;
    	int k;
    	for (int i = 0; i < MAXDIM; i++)
    	{
    		max = 0;
    	
                    // Da notare che non scorro sempre tutto il vettore
                    // ma mi fermo quando il numero degli elementi 
                    // ancora da analizzare non consentirebbe comunque
                    // di superare il massimo raggiunto [best]
    		for (int j = i + 1; j < MAXDIM - best + max; j++)
    		{
    			if (vettore[j] == vettore[i])
    			{
    				max++;
    			}
    			if (max > best)
    			{
    				best = max;
    				k = vettore[i];
    			}
    		}
    	}
    
    	printf ("...and the winner is %d con %d ripetizioni!", k, best);
    }
    
    Se usassi le strutture il tuo prof farebbe bene ad arrabbiarsi, infatti non si tratta di usare una struttura dati più elaborata, ma di rendere efficiente il conteggio.

    Alcune precisazioni finali: il programma conta solo le ripetizioni e non le occorrenze. Leggendo il titolo si dà per scontato che esista un solo numero massimo di elementi che ha delle ripetizioni.
  • Re: Trovare in un vettore il valore con il numero massimo di rip

    Lascio anche una possibile implementazione (senza ordinamento) che ho scritto al volo. Non è molto ottimizzata ma sembra che funzioni:
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void stampa_vettore(int* vettore, int dim)
    {
        int i;
        printf("\n");
        for(i=0; i<dim; i++)
        {
            printf("%d  ", vettore[i]);
        }
        printf("\n\n");
    }
    
    int valore_max_ripetizioni(int* vettore, int dim)
    {
        int i, j, count=1, count_max=0, val_max;
        
        for(i=0; i<dim; i++)
        {
            for(j=i+1; j<dim; j++)
            {
                if((vettore[j] != -1) && (vettore[j] == vettore[i]))
                {
                    /* incremento il contatore relativo a questo elemento */
                    count++;
                    /* segno che l'ho gia' considerato */
                    vettore[j] = -1;
                }
            }
    
            if(vettore[i] != -1)
            {
                printf("%d ripetizioni di %d\n", count, vettore[i]);
            }
    
    		/* se questo elemento e' (per ora) quello che si ripete piu' volte */
            if(count > count_max)
            {
                count_max = count;
                val_max = vettore[i];
            }
            
            /* resetto il contatore */
            count = 1;
        }
        
        return val_max;
    }
    
    
    int main()
    {
        int vettore[]={1, 2, 1, 2, 3, 1, 4};
        int piu_ripetuto;
        
        stampa_vettore(vettore, 7);
        
        piu_ripetuto = valore_max_ripetizioni(vettore, 7);
        
        printf("\nIl valore piu' ripetuto e' %d.\n", piu_ripetuto);
        
        return 0;
    }
    
    L'inconveniente è che il vettore viene "distrutto", nel senso che il suo contenuto viene alterato. Però il codice si può ovviamente modificare in modo che le operazioni vengano fatte su una copia del vettore e non sull'originale.
  • Re: Trovare in un vettore il valore con il numero massimo di rip

    Grazie a tutti ragazzi!!siete stati utilissimi
Devi accedere o registrarti per scrivere nel forum
5 risposte