Newsgroup: it.comp.programmare
Titolo: [OT CHALLENGE - Maggioritario!]

L'ho postato su it.scienza.matematica dopo aver visto altri strani quiz, ma
forse è meglio postarlo anche qui :-)
Tempo fa un prof. d'Informatica mi chiese di realizzare un piccolo
algoritmo.
Ci sono riuscito però vorrei vedere se trovate altri metodi...
Data una sequenza di n numeri, sia maggioritario il numero che compare più
di n/2 volte.
Sviluppare un algoritmo O(n) che trovi il maggioritario di una sequenza di n
numeri non ordinati.
Non penso che sia un problema molto conosciuto e infatti su Internet si
trova poco al riguardo.
(a quel tempo non trovai niente!)
Naturalmente cercate anche di limitare l'utilizzo di memoria.
Kiuhnm

 numeri non ordinati.
La mia soluzione (molto banale) e' la seguente:
creo una mappa numero -> frequenza
per ogni numero nel vettore:
	mappa[numero] = mappa[numero] + 1
frequenzamax = -1
numeromax = 0
per ogni elemento nella mappa:
	se mappa[numero] > frequenzamax:
		numeromax = numero
		frequenzamax = mappa[numero]
se frequenzamax > (elementi nella mappa / 2):
	stampo numeromax
altrimenti
	stampo Non esiste nessun numero maggioritario
La cosa piu' bella e' che se traduco questa pseudocodifica in inglese ho 
quasi ottenuto il listato in python senza errori ;-). Pero' non so se sono 
dentro i limiti di complessita', e di analisi di algoritmi in 3 ITIS non 
ne abbiamo ancora fatta molta...
-- 
Andrea Bergia - studente
Linux Registred User #281550

 numeri non ordinati.
Carino il problema, la mia soluzione non è una O(n) purtroppo, e peggio
ancora non comunica all'utente che non esiste un massimale ma resituisce un
numero a caso.. :)  detto ciò, credo che per il resto funzioni bene, anche
se ho fatto (relativamente) poche prove :
int massimale(int* ar,int size,int bit)
{
 int numero=0,ms=(size/2)+1,p=0,pb=0;
 for(int i=0,j=size+1;i<j&&pb<=bit;i++)
 { if(i==size)
  {
   if(p>=ms) numero|=(1<<pb);
   else numero&=~(1<<pb);
   i=0; pb++; p=0;
  }
  if(((ar[i]>>pb)&~(~0<<1))) p++;
 }
 return numero;
}
in pratica analiza l'espansione binaria di ogni numero, e in base alle
occorrenze degli 0 e1 produce un massimale. I risutati che ho ottentuto li
ho testati con una funzione che sicuramente trova il massimale, combaciano
sempre(apparte quando non c'è un massimale.. :)), quindi penso funga.. :)))
int versioneBruta(int* ar,int size)
{
 int pos=-1,ms=(size/2)+1,max=0,c;
 for(int i=0;i<size;i++)
 { c=0;
  for(int j=i;j<size;j++)
   if(ar[i]==ar[j]) c++;
  if(c>max&&c>=ms)
  { max=c;
   pos=i; }
 }
 return pos!=-1?ar[pos]:-1;
}
sono curioso di vedere la tua versione..
Ola
ps:
Non c'è bisogno che posti la soluzione troppo presto, magari riesco ad
inventarmi qualcosa di meglio.. :-)))

 ne abbiamo ancora fatta molta...
Per funzionare funziona ed è pure O(n) dato che scandisce gli n numeri una
sola volta.
Il problema nasce se hai una lista di questo tipo:
1; 4; 40234234; 145; 345327656; 654
Ovviamente puoi usare una hash, ma allora a questo punto ti conviene
ordinare la lista col Bucket Sort (ordina in O(n)) e poi prendere l'elemento
di indice n/2. Se esiste, quello è il maggioritario.
Kiuhnm
P.S. Se non conosci il Bucket Sort, fattelo spiegare oppure cercalo su
qualche libro o su Internet: è veramente simpatico :-)

 numeri non ordinati.
Esiste sempre, per qualsiasi input, un numero maggioritario?
Ci sono particolari assunzioni? (tipo massimo valore di N, massimo 
valore di x, dove x è un numero qualsiasi all'interno della sequenza )
Maurizio

 valore di x, dove x è un numero qualsiasi all'interno della sequenza )
No, nessuna, comunque nella pratica si può pensare che i numeri siano
rappresentati da un numero massimo di bit, costante per l'intero processo
(per es. 32)
Kiuhnm

 :)), quindi penso funga.. :)))
Bellino bellino....
In pratica hai usato il seguente teorema (che m'invento in questo momento
:-))) ):
Un numero è maggioritario se e soltanto se lo è anche ogni suo bit!
Più generale:
Un numero è maggioritario se e soltanto se lo è anche ogni sua cifra in base
b!
Però ti prego! La prossima volta scrivi direttamente 1 al posto di ~(~0 <<
1)!!!!!!!
Ho il forte sospetto che il metodo del mio prof. fosse proprio questo.
Chiamalo sesto senso...
Devo infatti farti notare che la tua funzione *è* O(n)!
Perchè non dovrebbe esserlo?
*bit* è una costante e perciò t = bit*n....più O(n) di così si muore!
Cercando di renderlo il più intuitivo possibile, si dice che:
f(x) = O(n)
se esiste k tale che
g(x) = k*n > f(x) per x > x0
cioè se disegnando f(x) e g(x), per x > x0, g(x) resta sempre (all'infinito)
sopra f(x).
x0 serve perchè alcune funzioni all'inizio potrebbero essere maggiori per
diventare minori in seguito (pensa a f(x) = log2(n) e a g(x) = x/5. Tra
l'altro f(x) è O(n) però è anche O(log2(n)) che è ancora meglio!).
Ovviamente la definizione può essere estesa a O(n^2), ecc...
La tua funzione è:
f(x) = bit*n
ed è sempre inferiore a:
g(x) = (bit+1)*n
Ovviamente per n > 0.
Per es. f(x) = 3n^3 + 20n^2 + 300
è O(n^3).
:-)))
E' tutto chiaro?
Kiuhnm
P.S. Complimenti! Davvero un bell'algoritmo :-) Adesso aspettiamo gli
altri.....(mi dispiace per i killati, ma farò fatica a vederli :-) )

 altri.....(mi dispiace per i killati, ma farò fatica a vederli :-) )
Sono molto curioso di conoscere le soluzioni altrui, cmq ho risolto il più
grande inconveniente del mio algoritmo.. adesso restituisce -1 se non trova
un massimale. Le prestazioni non sono decadute come potrebbe sembrare
leggendo il codice, ho apportato alcune modifiche al ciclo più interno per
controbilanciare, in media facendo test empirici (con numeri casuali
compresi tra 20000 e 11 milioni con 0>=N<=4mld) ottengo un miglioramento del
tempo d'esecuzione del 25%. (con picchi del 30% e nel caso peggiore che ho
riscontrato solo un misero 5% di incremento).
Ecco l'algoritmo :
int massimale(int* ar,int size,int bit)
{
 int numero=0,ms=(size/2)+1,p=0,p0=0,pb=0;
 for(int i=0,j=size+1;i<j&&pb<=bit;i++)
 { if(i==size||p0>=ms)
  { i=0; pb++; p=0; p0=0; }
  if((ar[i]>>pb)&1) p++;
  else     p0++;
  if(p>=ms)
  { numero|=(1<<pb); i=size-1; }
 }
 for(p=0,p0=0;p0<ms;p0++)
  if(ar[p0]==numero)
  { p++; if(p>=ms) break; }
 return (p>=ms)?numero:-1;
}
Ola.

 }
Pensavo che il tuo metodo potrebbe essere migliorato ulteriormente, ma,
prima di dire fesserie, preferirei pensarci un po' :-)
Kiuhnm

 ma, prima di dire fesserie, preferirei pensarci un po' :-)
A dire la verità è un miglioramento piuttosto scontato a costo di un po' di
memoria...
Anzichè trattare un bit alla volta puoi trattarne K allocando un array di
2^K interi (contatori), così ottieni un tempo di bit/K*n.
Comunque niente di nuovo......l'altra idea che avevo non funziona.
Resta comunque l'algo 2n originale :-)
Kiuhnm

"Filip Janiszewski" ha scritto
: Sono molto curioso di conoscere le soluzioni altrui, cmq ho risolto il più
: grande inconveniente del mio algoritmo.. adesso restituisce -1 se non
trova
: un massimale.
Penso che sarebbe piu` appropriato restituire l'indice di uno degli elementi
o -1 in caso non esista. Altrimenti non puoi distinguere quando l'elemento
trovato vale proprio -1.
: Ecco l'algoritmo :
:
: int massimale(int* ar,int size,int bit)
: {
:  int numero=0,ms=(size/2)+1,p=0,p0=0,pb=0;
:  for(int i=0,j=size+1;i<j&&pb<=bit;i++)
:  { if(i==size||p0>=ms)
:   { i=0; pb++; p=0; p0=0; }
:   if((ar[i]>>pb)&1) p++;
:   else     p0++;
:   if(p>=ms)
:   { numero|=(1<<pb); i=size-1; }
:  }
:  for(p=0,p0=0;p0<ms;p0++)
:   if(ar[p0]==numero)
:   { p++; if(p>=ms) break; }
:  return (p>=ms)?numero:-1;
: }
:
Purtroppo non funziona, quantomeno... non sempre.
#include <iostream>
int main()
{
  using namespace std;
  int i[] = {-1, -1, 0, 0, 0};
  cout  << massimale(i, 5, 32) << endl;
  return 0;
}
stampa -1
ciao
Massimo

 }
Mi hai fatto notare un brutto errore causato dalla distrazione è dal caldo
tropicale di questi giorni :), il problema è che il ciclo che controlla se
numero è maggiore o uguale a ms loppa per ms((size/2)+1) volte!!
Nell'esempio gli 0 sono dopo ms, il loop deve andare avanti per size volte.
for(p=0,p0=0;p0<size;p0++)//Brutto errore ci và size
  if(ar[p0]==numero)
  { p++; if(p>=ms) break; }
Ora funziona bene. Cmq l'indice pb parte da 0, quindi alla funzione devi
passare bit==31, 0..31==32.. ok?.. :)
Ola

 devi passare bit==31, 0..31==32.. ok?.. :)
Secondo me l'errore nasce dal fatto che il parametro 'bit' è un po' ambiguo.
Io userei MSBit o lastbit = 31 oppure bits = 32 (basta eliminare un uguale).
Kiuhnm

 Ci sono riuscito però vorrei vedere se trovate altri metodi...
[CUT]
Oramai penso che nessuno più presenterà altre versioni dell'algoritmo, facci
vedere il tuo.. :)))