Elemento più frequente

Programmazione, algoritmica, teoria dell'informazione, ...
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Elemento più frequente

Messaggio da rand » 19 mag 2007, 19:50

Questo non è certo originale ma è sempre carino per chi non lo conosce già:
Determinare se in un array di interi c'è un valore che si ripete più della metà delle volte usando spazio costante e senza alterare l'array.
La soluzione banale prende tempo quadratico ma esiste qualcosa di molto migliore che lascio a voi trovare. Ciao.

Avatar utente
=Betta=
Messaggi: 22
Iscritto il: 09 mag 2006, 14:54
Località: Modena
Contatta:

Messaggio da =Betta= » 20 mag 2007, 13:02

Beh, così su due piedi, mi verrebbe da fare un sort dell'array. A questo punto, i valori uguali saranno tutti vicini, quindi userei una variabile che mi scorre il vettore e che incrementa di uno ogni volta che l'elemento che sta consderando è uguale al precedente, mentre si azzera appena ne trova uno diverso, ricominciando così la conta. Se durante il ciclo, il valore della variabile supera n/2 (considerando con n il valore della lunghezza dell'array), allora vuol dire che il valore che sta considerando si ripete per più della metà.
Così è un po' più ottimizzato di un quadratico, anche se probabilmente si può trovare qualcosa di ancora migliore... Va beh vorrà dire che ci penserò un altro po'! :wink:
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei

Avatar utente
=Betta=
Messaggi: 22
Iscritto il: 09 mag 2006, 14:54
Località: Modena
Contatta:

Messaggio da =Betta= » 20 mag 2007, 13:04

Ah però così altero l'array, mi ero dimenticata dell'ultima parte del tuo messaggio... Beh allora come non detto, penserò a qualcos'altro!! :lol:
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei

MindFlyer

Messaggio da MindFlyer » 21 mag 2007, 12:24

Butto li' un'osservazione che forse e' utile: se c'e' un elemento che si ripete piu' della meta' delle volte, allora compare in 2 posizioni consecutive dell'array.

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

Messaggio da marcuz » 21 mag 2007, 14:52

MindFlyer: provo ad aggiungere qualcosa alla tua osservazione.
Se N è pari e ci sono N/2+1 o più elementi uguali, allora almeno due o più di questi sono consecutivi.
Se N è dispari e ci sono N/2+1 o più elementi uguali, allora possono non esserci due o più elementi uguali consecutivi.

Correggetemi se sbaglio...
Ultima modifica di marcuz il 21 mag 2007, 15:05, modificato 2 volte in totale.
Nessun uomo è un'isola (J. Donne)

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

Messaggio da MateCa » 21 mag 2007, 14:59

E' sufficiente considerare il primo e l'ultimo elemento dell'array come consecutivi...comunque non capisco come possa essere utile :oops:
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 » 21 mag 2007, 15:06

ah io non consideravo l'ultimo e il primo consecutivi...
Nessun uomo è un'isola (J. Donne)

MindFlyer

Messaggio da MindFlyer » 21 mag 2007, 17:34

Sì, scusate per l'imprecisione. Quell'unico caso si esclude in tempo lineare, oppure si riconduce agli altri facendo finta che l'array sia circolare, come volete.
Usare questa cosa in modo sensato, è tutto un altro paio di maniche, però. :roll:

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

Messaggio da ipparco » 22 mag 2007, 10:02

Per il caso pessimo non ho idee, ma per il caso medio una soluzione potrebbe essere questa: si prende un elemento a caso e si scorre l'array per vedere se ricorre più di metà delle volte; se sì, si termina, altrimenti si ricomincia da capo.
Sia $ $$ n $$ $ il numero degli elementi, sia $ $$ m $$ $ il numero di passi che vengono eseguiti all'interno del loop "infinito"; $ $$ m $$ $ è lineare rispetto a $ $$ n $$ $. Il numero di passi svolti mediamente sarà al più
$ m \sum_{i=1}^{\infty} i/2^i $. Poichè $ \sum_{i=1}^{\infty} i/2^i $ è convergente, in media l'algoritmo opererà in $ O(m) $ e, quindi, in $ $$ O(n) $$ $.

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

Messaggio da SkZ » 22 mag 2007, 10:26

si puo' abbreviare la tua procedura cosi' volendo

Codice: Seleziona tutto

l=strlen(str);
m=l>>1;
for(i=0; i<m; i++)
  for(j=i+1, n=0; j<l; j++){
    if(str[i]==str[j]) n++;
    if(n>m) return 0;
    if(j>n+m) break;
  }
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

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

Messaggio da ipparco » 22 mag 2007, 10:54

Oooops, ho riletto il problema e mi sono accorto che ho fatto un algoritmo che non c'entra niente. Avevo capito: dato un array con un elemento che ricorre più di metà delle volte, trovare l'elemento usando spazio costante.
Scusate.

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

Messaggio da ipparco » 22 mag 2007, 11:38

Imperterrito, incurante delle figuracce, continuo a sparare algoritmi.
Una soluzione potrebbe essere questa:
1) trovo il valore massimo nell'array, che chiamo max
2) eseguo un ciclo con i che va da 1 a logaritmo in base 2 di max
3) trovo il numero di elementi che, in base 2, terminano con 0 e il numero di elementi che, in base 2, terminano con 1 (si usa il modulo 2, o, meglio, il modulo 2^i)
4) se entrambi i valori sono minori della metà + 1, si termina con insuccesso, altrimenti si prende il valore che ha avuto più hit, per esempio 1, e al ciclo successivo si testano i valori 01 e 11 (modulo 4, cioè 2^2)
5) se entrambi i valori sono minori della metà + 1 si termina con insuccesso, altrimenti si prende il valore che ha avuto più hit, e così via.
Questo sistema permette sia di verificare se un array ha un elemento che ricorre più di metà delle volte, sia di esibire questo elemento (che, nel caso esista, viene "ricostruito" iterazione dopo iterazione).
Il caso peggiore è O(nlog(max)).

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

Messaggio da rand » 22 mag 2007, 12:44

L'idea di Ipparco è molto buona. Ma non è ancora la soluzione "vera". Si può risolvere in tempo lineare (questo è già un hint) con un approccio differente ma per nulla sofisticato. Dai, che non è difficile.

Avatar utente
=Betta=
Messaggi: 22
Iscritto il: 09 mag 2006, 14:54
Località: Modena
Contatta:

Messaggio da =Betta= » 23 mag 2007, 21:52

Premetto che la mia idea è da affinare, adesso la butto giù giusto in linea teorica e che considero l'array in modo circolare, quindi considero la cella finale come consecutiva a quella iniziale. (e che non sono molto brava a spiegare, quindi farò il possibile per farmi capire ugualmente! :wink: )..
Io scorrerei l'array e cercherei qual è la sequenza di lunghezza massima (chiamiamola L) di celle consecutive contenenti uno stesso numero (chiamiamolo A).
A questo punto, come ha detto MindFlyer, perchè possa esistere almeno un elemento che si ripete per più della metà dell'array deve trovarsi almeno in due posizioni consecutive.
Quindi, se L è uguale a 1, non sono presenti elementi che verificano la condizione richiesta. Se è maggiore di 1, andiamo a vedere quante volte nell'array è presente A, e tengo in memoria questo valore in una variabile (C).
Se A è presente per più della metà dell'array, il problema è risolto.
Altrimenti, bisogna chiedersi se è possibile che esista un altro valore nell'array che verifica la condizione richiesta.
Quindi vado a cercare il valore che ha un numero di celle consecutive massimo escluso A. Guardo quante volte si ripete nell'array (e le sommo nella variabile C) e, se neanche questo verifica la condizione, continuo la mia ricerca fino a quando la lunghezza massima di celle consecutive è >1 e C<N/2.

Spero di essere stata più o meno chiara... magari si possono trovare anche altre condizioni per ridurre ulteriorimente il numero di ricorsioni, se mi dite che sono sulla strada giusta provo a pensare anche a quelle! :D
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei

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

Messaggio da marcuz » 23 mag 2007, 23:45

So praticamente nulla di informatica, comunque ad intuito mi sembra di aver capito che per "spazio costante" si intenda che qualsiasi struttura creata nell'algoritmo deve essere indipendente dalla grandezza dell'input, è giusto?

A =Betta= : il tuo algoritmo, se ho capito bene, conta comunque tutti gli elementi, ma lo fa "in ordine di sospetto", ovvero ritenendo soluzioni più probabili gli elementi con sequenze di lunghezza maggiore. Da dove deriva precisamente questo sospetto? Poi, come si comporta il tuo algoritmo nel caso in cui ci siano due elementi distinti che hanno sequenze di uguale lunghezza massima? Poi, ordinando gli elementi per sospetto, associ una lunghezza L1 a un elemento A, L2 ad un elemento B, ecc. ma dove salvi queste relazioni? La struttura in cui le salvi dipende dal numero di elementi diversi nell'array, e quindi dall'input? (vedi inizio messaggio).
Nessun uomo è un'isola (J. Donne)

Rispondi