[C++] array

[atomic]

scusate, ma proprio non riesco a scrivere il codice.
dato un array a[n] = {1, 4, 5, 1, ...
visualizzare l'elemento + frequente
tra pochi gg ho l'esame sul c++ e non riesco a risolvere i problemi sulla frequenza. se mi potete aiutare grazie

[Michele Facchin]

Qual'è il valore massimo che l'array può contenere?

[atomic]

non lo so...bisogna trovare il max?

[Michele Facchin]

No, è solo una domanda che vedo una cosa...quanto è il max? 10 100 1000 10000?

[atomic]

10

[Michele Facchin]

A mè è venuta questa idea che funziona con pochi...

#include <iostream.h>

main(){
 int array[11]={1,3,3,3,4,5,6,3,6,1,1};
 int frequenza[11]={0,0,0,0,0,0,0,0,0,0,0};
 int max=0,vf=0;
 for (int i=0;i<11;i++) 
  frequenza[array[i]]++;
 for (i=0;i<11;i++) 
  if (frequenza[i] > vf){
   vf=frequenza[i];
   max=i; }
 cout<<"Il valore frequente corrisponde a: "<<max<<endl;
 return(0);
}

Se modifichi i valori del vettore "array" con valori dal 0 al 10, lui ti dice quale di questo numero è ripetuto più volte:

Ti spiego:

Dichiaro un array di 11 valori v[0]..v[10]
Poi ne dichiaro un altro con tutti i valori a 0.

I valori 0 sarebbero le frequenze dei singoli numeri che all'inizio sono 0.

Scanno il vettore array[11] e per ogni valore incremento il corrispondente nella "tabella" frequenza[11]:

Nell'esempio:

{1,3,3,3,4,5,6,3,6,1,1}

il valore frequenza assumerà:

{0,3,0,4,1,1,2,0,0,0,0}

e cioè:

0 = numero degli 0 nel vettore array
3 = numero degli 1 nel vettore array
0 = numero dei 2 nel vettore array
4 = numero dei 3 nel vettore array

Ecc....

Cosi adesso sò quale dei valori nel vettore array è + frequente.

Infatti se noti il vcalore + frequente è il 3, perchè si presenta 4 volte e il suo indirizzo è dato dalla cella del vettore "frequenza".

P.S.

E' difficile da capire, o forse sono io che non lo sò spiegare...ma mi è venuto così a intuito...magari ci sono modi più semplici e molto migliori, mi informerò.

[Andrea Simonassi]

prova questa, ordina l'array e poi conta la lunghezza dei gruppi di valori
esempio
1,1,1,1,3,3,3,3,3,5,5,6,6,7,7

gruppo 1 lungo 4
gruppo 3 lungo 5,
gruppo 5 lungo 2
.....

vince il gruppo piu lungo

#include <algorithm>
int freq(int*a, size_t a_len)
{
  int*b=&a[a_len];
  int cur, c_cur=0, best, c_best=0; 	

  std::sort(a, b);

  while(a<b)
  {
    cur = *a++;
    if(++c_cur > c_best)c_best=c_cur, best=cur;
    if(*a!=cur)c_cur=0;
  }
  return best;
}

Complessita O(NlogN(se l'algoritmo di sort e' efficiente) + n(la scansione dell'array ordinato)), circa uguale a =(NlogN)

oppure crea una mappa in memoria dove associ i valori trovati nell'array a un conteggio, se conosci la STL

#include <map>
int freq(int*a, size_t a_len)
{
  int*b=&a[a_len];
	
  std::map<int,int>m;
  std::pair<std::map<int,int>::iterator ,bool>i;

  int best, c_best;

  while(a<b)
  {
    if(i = m.insert(std::map<int,int>::value_type (*a, 1)), !i.second) 
    i.first->second ++;
    if(i.first->second>c_best)    
      best = *a, c_best=i.first->second;
    ++a;
  }
  return best;
}

in questo caso la complessita' e' O(N) + la complessita' dell'insert nella mappa che non conosco

[atomic]

grazie!

[TheGreatWorld]

int main() {

int array[] = { 1, 1, 2, 4, 3, 3, 5, 6, 6, 6 };

int search[10] = { 0 };

for (int i = 0; i < 10; ++i)
search[i]++;

return 0;

}

// a buon intenditor poche parole

[Andrea Simonassi]

Originariamente inviato da TheGreatWorld

int main() {

int array[] = { 1, 1, 2, 4, 3, 3, 5, 6, 6, 6 };

int search[10] = { 0 };

for (int i = 0; i < 10; ++i)
search[i]++;

return 0;

}
// a buon intenditor poche parole

Ci ho capito na mazza, qual'è lo scopo di fare girare un simile programma che riempie un array di 1?