Elemento più frequente

Programmazione, algoritmica, teoria dell'informazione, ...
MindFlyer

Messaggio da MindFlyer » 24 mag 2007, 00:22

Se ho capito bene la soluzione di betta, su un array del tipo
1-1-2-2-3-3-4-4-...-n/2-n/2
ci mette tempo quadratico. Giusto?

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 24 mag 2007, 10:40

Quello che dice =Betta= non ha spazio costante e non è nemmeno lineare. Detto rozzamente "spazio costante" significa usare un numero di celle di memoria finito e indipendente dalla lunghezza dell'array. Questo restringe parecchio il numero di cose ragionevoli da fare.

Avatar utente
ipparco
Messaggi: 58
Iscritto il: 24 gen 2007, 10:44
Località: Verona

Messaggio da ipparco » 25 mag 2007, 12:00

Dai, rand, dacci qualche hint...
Sono curioso, per cui, anche se metti direttamente la soluzione, non mi offendo.

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 25 mag 2007, 14:36

L'hint ve l'ho già postato in realtà. Basta pensare ai vincoli del problema. Tempo lineare e spazio costante vuol dire che al massimo è consentito fare una o più scansioni durante le quali ci si può portar dietro un elemento e magari anche un contatore. Questo è sufficiente per poter scandire l'array mantenendo un unico elemento candidato ad essere il maggioritario. Esiste un algoritmo per farlo molto elementare che si descrive in 3-4 righe di pseudo-codice, quindi non è impossibile arrivarci con un pò di immaginazione, forza!

Avatar utente
teppic
Moderatore
Messaggi: 704
Iscritto il: 26 ago 2005, 09:50
Località: Parma
Contatta:

Messaggio da teppic » 25 mag 2007, 14:56

Io ci riesco in tempo N log N. Andrà bene? :?

Costruisco una funzione ricorsiva che prende in input un array e risponde:
1) VERO/FALSO a seconda se esiste un elemento che compare più di metà delle volte
E in caso positivo:
2) Che elemento è
3) Quante volte compare.

Il funzionamento è il seguente.

Chiama se stessa due volte: sulla prima metà dell'array e sulla seconda metà.

Se un elemento compare più della metà delle volte nell'array intero, allora deve comparire più della metà delle volte in almeno uno dei due sottoarray (pigeonhole - funziona anche se la lunghezza è dispari).

Se entrambe le chiamate rispondono FALSO, l'array intero non ha un elemento frequentissimo. Rispondo FALSO ed esco.

Se una o entrambe le chiamate rispondono VERO, per una o due volte conto quante volte compare l'elemento più frequente del sottoarray nell'altro sottoarray, faccio la somma e capisco se compare più della metà delle volte sull'array intero.

Rispondo a seconda del risultato ed esco.

La funzione viene chiamata un numero di volte lineare in N.
L'unica procedura "lenta" è il contare quante volte compare un elemento nell'altro sottoarray, ma nel peggiore dei casi (si trova dopo un po' di conti) devo scorrere log N volte l'intero array.

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 25 mag 2007, 16:04

La soluzione sarebbe corretta se avesse spazio costante, invece ce l'ha logaritmico, perchè bisogna tenere traccia dei risultati forniti dalle chiamate ricorsive. Inoltre non è lineare in tempo. Andiamo, perchè volete complicarvi così tanto la vita ?? :wink:

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 27 mag 2007, 21:27

pensavo

Codice: Seleziona tutto

#include <string.h>
int main(int argc, char **argv){
  int n[256], f[256], i,l;

  for(i=0;i<256;i++) n[i]=f[i]=0;

  for(i=0; argv[1][i]; i++){
    n[argv[1][i]-'\0']++;
    if(argv[1][i]==argv[1][i+1]) f[i]++;
  }

  l=i>>1;  /*in pratica da la parte intera della divisione per 2 */
  for(i=0; i<256;i++)
    if(f[i] && n[i]>l)  return 0;

  return 1;
}
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

MindFlyer

Messaggio da MindFlyer » 29 mag 2007, 18:43

Non mi pare vada bene.
Per prima cosa stai "barando" perché l'array n dovrebbe essere infinitamente lungo, in quanto non esiste un limite superiore agli interi che puoi dare in input.
Poi, direi che l'array f è completamente inutile. Ed anzi va tolto, perché fa scazzare il programma. Se lo togli il programma funziona, ma resta il problema dell'array indefinitamente lungo.

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 29 mag 2007, 18:57

:oops: :oops: ero rimasto alle stringhe (char ha 256 caratteri)
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

MindFlyer

Messaggio da MindFlyer » 29 mag 2007, 20:01

Ok, np.
Mi piacciono questi problemi dove chi li propone garantisce che la soluzione è semplicissima, eppure nessuno la trova. :D

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 30 mag 2007, 22:04

Nessun'altra idea per farlo in tempo lineare e spazio costante?

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 01 giu 2007, 13:04

Va bene, ecco la soluzione. L'algoritmo fa due scansioni sul vettore A in questione. L' idea, come nell'hint, è di determinare nella prima scansione un solo elemento "candidato" ad essere il maggioritario e nella seconda verificare se questo è davvero maggioritario. La prima scansione mantiene una coppia (x,c) dove x è il candidato corrente e c è un opportuno contatore:

x = Null; c = 0;
for i = 1 to n do
{
// ad ogni nuova occorrenza del candidato c++ ad ogni altra occorrenza c-- //

if A == x then c = c+1 else c = c-1

// se c < 0 butta via x e A nuovo candidato //

if c < 0 then x = A; c = 1

}

Nella seconda scansione basta semplicemente vedere se il numero di occorrenze di x è piu' di n/2, se si restituisce x come maggioritario, altrimenti non c'è nessun maggioritario. Tempo lineare O(n) spazio O(1)

marcuz
Messaggi: 70
Iscritto il: 26 feb 2007, 21:54
Località: Pisa
Contatta:

Messaggio da marcuz » 02 giu 2007, 00:11

Suppongo che il valore iniziale di x debba essere A[0] e non "Null", correggetemi se sbaglio.

Scusa mettiamo di avere l'array A = {1, 1, 1, 1, 0, 0, 0, 2, 2}, svolgendo passo dopo passo mi sembra di aver capito che l'algoritmo si comporti così:

x = 1
c = 1
c = 2
c = 3
c = 4
c = 3
c = 2
c = 1
c = 0
c = -1 --> x = 2 c = 1

A questo punto l'elemento favorito è 2, che si ripete meno di n/2 volte, quindi l'algoritmo restituisce un riscontro negativo, mentre l'elemento più frequente c'è (1).

Vi prego di essere pazienti e spiegarmi, se sbaglio, qual è l'errore. Grazie!
Nessun uomo è un'isola (J. Donne)

Avatar utente
MateCa
Messaggi: 98
Iscritto il: 23 ago 2006, 23:27
Località: Camurana

Messaggio da MateCa » 02 giu 2007, 10:02

Non ho analizzato bene l'algoritmo risolutore, cmq penso di aver capito...
Nel tuo esempio effettivamente l'algoritmo trova come valore "che probabilmente di ripete più della metà delle volte" un valore che non è quello che si ripete più volte, però questo non influisce sulla correttezza della soluzione...Lo scopo del programma dev'essere quello di trovare se un elemento si ripete più della metà delle volte, se questo non accade poco importa che cosa faccia l'algoritmo, l'importante è che lo trovi nel caso ci sia. Non so se mi sono spiegato, ma quello che intendo dire è che la tua considerazione (che è giustissima :!: ) non implica che l'algoritmo sia sbagliato, anzi è una conferma che anche in quel caso funziona e restituisce il risultato corretto :D
Parlare oscuramente lo sa fare ognuno, ma chiaro pochissimi. (G. Galilei)

marcuz
Messaggi: 70
Iscritto il: 26 feb 2007, 21:54
Località: Pisa
Contatta:

Messaggio da marcuz » 02 giu 2007, 15:29

Ok avevo capito male :) E' possibile dimostrare la correttezza dell'algoritmo?
Nessun uomo è un'isola (J. Donne)

Rispondi