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.
Elemento più frequente
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'!
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'!
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei
-
MindFlyer
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...
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)
-
MindFlyer
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) $$ $.
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) $$ $.
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
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
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)).
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)).
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! )..
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!
).. 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!
Non ho mai incontrato un uomo così ignorante dal quale non abbia potuto imparare qualcosa. - G.Galilei
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).
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)