Elemento più frequente

[MindFlyer]

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?

[rand]

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.

[ipparco]

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

[rand]

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!

[teppic]

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.

[rand]

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 ??

[SkZ]

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;
}

[MindFlyer]

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.

[SkZ]

ero rimasto alle stringhe (char ha 256 caratteri)

[MindFlyer]

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

[rand]

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

[rand]

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]

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!

[MateCa]

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

[marcuz]

Ok avevo capito male E' possibile dimostrare la correttezza dell'algoritmo?