Algoritmo per la moda

[Vecchia Spugna]

Allora ragazzi mi sto letteralmente consumando il cervello per riuscire a trovare un algoritmo che mi clalcoli la moda con complessità O(n), cioè in pratica deve fare il tutto in un solo ciclo. A me sembra impossibile ma il professore dice che c'è...
boooooooooooooooh.
qualche idea?(più ci penso più mi pare assurdo poterlo fare con 1 ciclo solo,)
(ah ovviamente i dati in input non sono ordinati)
ciao a tutti e grazie in anticipo

[cionci]

Lo puoi fare se sai il range da tra cui possono variare gli elementi...se non lo sai dovresti allocare troppa memoria...

Supponendo che i dati siano interi che variano da 0 a N, dichiari un vettore (frequenze) di N interi...ogni elemento deve essere azzerato...

Supponendo che in dati siano nel vettore dati...

N = numero dei dati

1: i -> 1; max -> 0; indice_max -> 1
2: se i > N vai al punto 7
3: frequenze(dati(i)) -> frequenze(dati(i)) + 1
4: se frequenze(dati(i)) > max vai al punto 5, altrimenti vai al punto 6
5: max -> frequenze(dati(i)); indice_max = dati(i)
6: i -> i + 1; vai al punto 2
7: fine

[Vecchia Spugna]

purtroppo non ho il renge :(
se non ce l'ho mi dite che non posso far nulla?
però dai con l' allocazione dinamica.... alla fine anche fosse 1 vettore di 500, 1000 numeri non sarebbe infattibile.
altri metodi non ci sono?

[cionci]

Chiaro che con l'allocazione dinamica ci sono meno problemi...

Potresti fare una cosa del genere:

allochi 1000 interi per i numeri da 0 a 1000...se ti viene dato un numero più grande di 1000 usi realloc per allargare il vettore (per fare questa operazione il minor numero di volte possibile mettine 1000 in più rispetto all'elemento che supera il limite attuale)...

Altra soluzione sarebbe quella di una lsita, ma dopo diverrebbe O(n^2) per ricercare il valore...

Comunque anche con l'allocazione dinamica saresti emsso in ginocchio da valori che si molto alti e saresti limitato dalla memoria di sistema...

[Vecchia Spugna]

per O(n^2) esistono un' infinità di soluzioni ;) , ovvio
beh.. non so che dire.. grazie... sono molto demoralizzato :D
soprattutto a pensare che il prof dice che la soluzione O(n) c'è
vorrà dire che gli chiederò maggiori info sul range ;)

[Vecchia Spugna]

Allora riporto in auge la discussione con 1 aggiornamento così mi date una mano invece di stare ad askpettare la partita di domani sera sulla poltrona e con la fila di bottiglie di birra vuote!!! :sofico: :Prrr:

Alura....

Mediante tavole hash dovrebbe essere possibile fare il tutto con dei contatori.. quindi rimarrebbe il problema dei numeri con virgola....
Spremendo le vostre dotate meningi.. riuscireste a cavar fuori un'idea??

[cionci]

Non credevo che volessi trattare algoritmi così, per così dire, avanzati...
Il discorso hash è un po' complicato...è sì certo possibile fare il tutto con un vettore di contatori...ma il problema dell'hash è che non è biunivoco...di conseguenza non bastano i contatori...ma devi salvarti anche il valore facendo corrispondere ad ogni riga del vettore di hash un lista linkata... Ogni volta che trovi un certo hash dovrai scorrere la lista linkata e verificare che il valore sia stato già immesso, ed in tal caso incrementare il contatore corrispondente...

La probabilità di trovare un valore già immesso nel campo corrispondente ad un dato hash è proporzionale allla lunghezza del vettore hash...

Come calcolare un semplice hash per i numeri in virgola mobile potresti fare un algoritmo di questo tipo:

1) il vettore di hash contiene 2^16 elementi (puntatori a strutture)
2) la funzione hash, dato un valore floating point, ritorna un unsigned short int
3) dato in input alla funzione hash un floating point su 8 byte (un double) esegue la somma 2 byte a 2 byte...il risultato è l'hash... Non ti importa niente degli eventuali overflow, visto che sono un fattore voluto...

Sai come realizzare il punto 3 ? Pensaci...

[Vecchia Spugna]

dammi un paio di giorni per riprendermi dallo shock di ciò che mi hai detto poi ti rispondo :D
scherzi a parte fammici pensare un pò che non è roba propriamente semplice questa.. :P
sto iniziando ora il capitolo in questione ;)

[Vecchia Spugna]

Rieccomi..
(che palle dite voi... come non darvi ragione...)
ehehmmmm

credo, pensando che fosse la stessa cosa.. di aver speso giorni della mia vita a cercare algoritmi per la moda quando invece a me serviva l'elemento di maggioranza... :D pensando che fosse la stessa cosa.. invece non lo era :P

quindi oggi trovo questo...


"
Problem 3. A read-only array (ROM) contains n integers. Find a linear-time algorithm that
determines whether the array has a “majority element,” and if so, returns that value. An integer
x is a majority element in the array if it is in k locations, where k > n/2.

Discussion: Repeatedly eliminate pairs of different elements. If any element remains it is the
only possible majority element, and a simple linear search can determine whether or not it is. One
clean way to perform the first step uses a stack, with operations push(), pop(), and stacktop():
Majority candidate(a)
for each element c of the array a
if the stack is empty or c is on top of the stack
push(c)
otherwise
pop()
if the stack is nonempty
return top()

"

Questo è quanto!! (soluzione semplice ma geniale...)
ops... :fagiano:
forse non troppo semplice... :D
che faccio se i numeri immessi sono dispari?
inoltre...
il mio problema non è trovare l'elemento che compare NumeroDiVolte>n/2 , ma >=n/2... e ciò complica un pochettino la cosa...

allora cercando di far chiarezza in questo confusissimo post... :D
ciò che sottopongo alla vostra attenzione è...
1)cosa significa push e pop (so com'è fatto uno stack, ma non so push e pop cosa voglia dire :sofico: )
2)come mi comporto nei casi in cui n mi venga dispari
3)con che controlli aggiusto la situazione dato che mi possono anche venire 2 elementi di maggioranza




Grazie per aver consumato i vostri neuroni per capirmi ... :D
ciaooooooooo