Newsgroup: it.comp.lang.c++
Titolo: array con ballottaggio!

Salve a tutti,
oggi mi chiedevo come si potesse implementare un algoritmo che restituisse,
dato un array "popolato" da numeri interi positivi, le posizioni dove si
trovano i due valori più alti tenendo conto però di un sistema di
ballottaggio (tipo grande fratello).
Es.
int AAA[10]={4,7,1,1,1,2,8,7,3,7}
in questo caso la funzione dovrebbe segnalarmi AAA[1], AAA[6], AAA[7],
AAA[9].
Es. numero DUE
int BBB[10]={5,4,8,5,1,1,2,9,2,1}
in questo caso la funzione dovrebbe segnalarmi solo BBB[2], BBB[7].
diciamo le due più alte considerando eventuali parimerito.
Unico punto fisso, non voglio utilizzare un array con detti valori ordinati
poichè io voglio le posizioni di chi va al ballottaggio e non quanti voti
abbiano ricevuto (o quantomeno non mi interessa saperlo)
sia chiaro che non è nessun esercizio assegnatomi a scuola o simili! :-)
chiedo solo un indicazione o un parere, poichè in testa mi vengono algoritmi
un po' troppo complessi.
saluti a tutti
ivan

 AAA[9].
int N  = numero_degli_elementi_nel_vettore__Lunga_questa_variabile_eh;
int i,j,uno,due;
uno = due = -10000;
for (i=0; i<N; i++)   //trovo il max
      if (uno<AA[i]) uno=AA[i];
for (i=0; i<N; i++)   //trovo il max minore del max
      if (due<AA[i] && AA[i]<uno) due=AA[i];
for (j=i=0; i<N; i++) // mi segno le posizioni
      if (uno==AA[i] || due==AA[j]) OK[j++]=i;
fine.
Poi naturalmente uno puo' volere usare a tutti
i costi la STL.. cosa che lascio a qualcun altro.
ciao,
g.

 L'esempio del GF non mi dice nulla, non avendolo mai guardato.
Visto il tuo codice era meglio guardarlo... ;) 
-- 
Luc.


Quale e' il problema ?
g.

      if (uno==AA[i] || due==AA[j]) OK[j++]=i;
Un errore di battitura: la linea sopra voleva essere ovviamente
  if (uno==AA[i] || due==AA[i]) OK[j++]=i;
ciao,
g.

"Giovanni Resta" <g.r...@iit.cnr.it.nospam> ha scritto nel messaggio
news:3E7AE191...@iit.cnr.it.nospam...
| Ivan Sofa n.1 wrote:
| > Salve a tutti,
| >
| > oggi mi chiedevo come si potesse implementare un algoritmo che
restituisse,
| > dato un array "popolato" da numeri interi positivi, le posizioni dove si
| > trovano i due valori più alti tenendo conto però di un sistema di
| > ballottaggio (tipo grande fratello).
|
| L'esempio del GF non mi dice nulla, non avendolo mai guardato.
| Spero di capire correttamente.
|
| > Es.
| >
| > int AAA[10]={4,7,1,1,1,2,8,7,3,7}
| >
| > in questo caso la funzione dovrebbe segnalarmi AAA[1], AAA[6], AAA[7],
| > AAA[9].
|
| int N  = numero_degli_elementi_nel_vettore__Lunga_questa_variabile_eh;
| int i,j,uno,due;
| uno = due = -10000;
| for (i=0; i<N; i++)   //trovo il max
|       if (uno<AA[i]) uno=AA[i];
| for (i=0; i<N; i++)   //trovo il max minore del max
|       if (due<AA[i] && AA[i]<uno) due=AA[i];
| for (j=i=0; i<N; i++) // mi segno le posizioni
|       if (uno==AA[i] || due==AA[j]) OK[j++]=i;
|
ehm, credo che forse non hai capito bene il problema. Rivedi, se vuoi ,
l'esempio numero UNO che ho fatto.
se c'è parimerito vanno tutti al ballottaggio quindi anche il terzo ed il
quarto (Ad esempio).
grazie cmq
ivan

AAA[1], AAA[6], AAA[7], AAA[9].
Quanto ti chiedi SE si puo' implementare, ricordati che il 99% delle volte
la domanda deve essere come....
Ecco i passi da fare:
- trovare i due valori piu' alti
- creare una lista degli indici a cui tali 2 valori si trovano (che puo'
essere di 2 o piu' elementi)
- ritornare la lista.
Per comodita' non ti creo la funzione, ma ti metto tutto in main.
Eccolo:
<CODE>
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int AAA[10]={4,7,1,1,1,2,8,7,3,7};
    // Mettiamo in max1 e max2 i due valori piu' alti!
    int max1=AAA[0];
    int max2=AAA[1];
    for(int i=2;i<10-1;i+=2){
        if(AAA[i]>max1)max1=AAA[i];
        if(AAA[i+1]>max2)max2=AAA[i+1];
    }
    // Creiamo una lista con tutti gli indici in cui appaiono:
    queue<int> index_q;
    for(int i=0;i<10;++i){
        if((AAA[i]==max1)||(AAA[i]==max2))
            index_q.push(i);
    }
    // Ora leggiamo tutti i valori nella queue
    // e stampiamo quindi tutti gli indici in
    // cui questi due valori appaiono!
    while(!index_q.empty()){
        cout << index_q.front() << endl;
        index_q.pop();
    }
    return 0;
}
</CODE>
</OUTPUT>
1
6
7
9
</OUTPUT>
Se hai qualche domanda, commento etc... posta pure.
Il primo pezzo per trovare i due val piu' alti ti puo' apparire strano, ma
e' un trucchetto per iterare una sola volta nell'array.
Tommy

 Se hai qualche domanda, commento etc... posta pure.
Dici che funziona se c'č: 1,2,3,7,8,8
Cioč ritorna solo gli ultimi due?
-- 
Luc.

       if (due<AA[i] && AA[i]<uno) due=AA[i];
Ad ogni modo e' logico e funziona.
Che ne dici di questo per iterare una volta sola?
// Mettiamo in max1 e max2 i due valori piu' alti!
int max1=AAA[0];
int max2=AAA[1];
for(int i=2;i<10-1;i+=2){
    if(AAA[i]>max1)max1=AAA[i];
    if(AAA[i+1]>max2)max2=AAA[i+1];
}
L'unico svantaggio apparente e' che max1 non e' detto sia maggiore di max2.
Si puo' sempre testare e scambiarli (swap), ma per l'esercizio di Ivan non
importa nemmeno fare questo in quanto vanno stampati gli indici in ordine
crescente (e quindi l'ordine di max1 e max2 non cambia per nulla l'output).
Tommy


ehm, a parte l'errore di battitura che avevo corretto in un messaggio
successivo, mi sembra di aver capito... almeno come hanno capito altri
ti commento il programma:
// inizializzo i due valori
// che dovranno essere il valore piu' alto
// ed il secondo piu' alto
uno = due = -10000;
trovo il valore massimo (che memorizzo in uno)
che compare nell'array.
  for (i=0; i<N; i++)
          if (uno<AA[i]) uno=AA[i];
trovo, fra tutti i valori minori di uno,
quello massimo (che memorizzo in due)
for (i=0; i<N; i++)
   if (due<AA[i] && AA[i]<uno) due=AA[i];
A questo punto, nel tuo primo esempio ho uno=8 e due=7
ora scandisco l'array e mi segno dentro l'array OK[]
gli indici dell'array AA dove compaiono valori
che sono uguali al massimo o al quasi-massimo (cioe' uno e due):
for (j=i=0; i<N; i++) /
      if (uno==AA[i] || due==AA[i]) OK[j++]=i;
alla fine avrai OK[0]=1 OK[1]=6 OK[2]=7 OK[3]=9
e j=4 che mi dice quanti indici ho memorizzato.
Se ancora mi sfugge qualcosa, dimmelo.
ciao,
g.

 Cioè ritorna solo gli ultimi due?
<OUTPUT>
4
5
</OUTPUT>
Prova tu stesso devi cambiarlo in:
int AAA[6]={1,2,3,7,8,8};
 // Mettiamo in max1 e max2 i due valori piu' alti!
 int max1=AAA[0];
 int max2=AAA[1];
 for(int i=2;i<6-1;i+=2){
  if(AAA[i]>max1)max1=AAA[i];
  if(AAA[i+1]>max2)max2=AAA[i+1];
 }
In pratica mettere 6 e 6-1.
Si funziona!
Per evitare di dover cambiare costanti numeriche ti riscrivo una versione
con vector (ho usato arrays in quanto era la richiesta di Ivan!)
Tommy

 wrote
ECCO il codice, ho deciso di tenere gli array normali tuttavia.
Ora basta cambiare la riga con AAA per avere un risultato diverso.
Nota che devi almeno avere 2 elementi nell'array! (si potrebbe controllare
SIZE!).
<CODE>
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int AAA[]={1,2,3,7,8,8};
    int SIZE=sizeof(AAA)/sizeof(int);
    // Mettiamo in max1 e max2 i due valori piu' alti!
    int max1=AAA[0];
    int max2=AAA[1];
    for(int i=2;i<SIZE-1;i+=2){
        if(AAA[i]>max1)max1=AAA[i];
            if(AAA[i+1]>max2)max2=AAA[i+1];
    }
    // Creiamo una lista con tutti gli indici in cui appaiono:
    queue<int> index_q;
    for(int i=0;i<SIZE;++i){
        if((AAA[i]==max1)||(AAA[i]==max2))
            index_q.push(i);
    }
    // Ora leggiamo tutti i valori nella queue
    // e stampiamo quindi tutti gli indici in
    // cui questi due valori appaiono!
    while(!index_q.empty()){
        cout << index_q.front() << endl;
        index_q.pop();
    }
    return 0;
}
</CODE>
Tommy

 wrote
Sorry, attimo di delirio, NON funziona!
Tommy

 wrote
Il mio non funziona, attimo di pazzia....
Tommy

 }
dico che e' simpatico, ma (se ho capito bene il problema) e' sbagliato.
In pratica tu trovi il max1 di tutti gli elementi di posto pari
e il max2 di tutti gli elementi di posto dispari.
Pero' se per caso sono uguali, ti freghi il valore del secondo
massimo.
Cioe': su {1,5,4,5} mi restituisce correttamente 5 e 4, ma su {1,4,5,5}
mi restituisce 5 e 5 che e' sbagliato,
ciao,
g.

 Cioč ritorna solo gli ultimi due?
a quanto dice Ivan non deve... dovrebbe dare 3,4,5.... in pratica il mio non
funziona!!!
Tommy

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int AAA[]={1,2,3,7,8,8};
    int SIZE=sizeof(AAA)/sizeof(int);
    // Mettiamo in max1 e max2 i due valori piu' alti!
    int max1=AAA[0];
    int max2=AAA[1];
    for(int i=2;i<SIZE-1;i+=2){
        if(AAA[i]>max1)max1=AAA[i];
        if((AAA[i+1]>max2)&&(AAA[i+1]!=max1))


 }
utlima riga
va cambiata in:
if((AAA[i+1]>max2)&&(AAA[i+1]!=max1)) max2=AAA[i+1];
Tommy

 mi restituisce 5 e 5 che e' sbagliato,
SI, ho fatto un gran casino sul NG. Non devo programmare quando ho la
febbre!
Per oggi basta, ci risentiamo domani!
Grazie,
Tommy

     int max2=AAA[1];
cosa succede se per caso queste due posizioni hanno lo stesso valore?!?
Non funziona!
Ora, e' FACILMENTE risolvibile, ma visto i casini fatti lascio perdere....
Se volete fatelo voi....
Chiedo scusa.
Tommy

int lessermax = -1;
int max = -1;
for (i = 0; i < numelements; i++)
{
    if (array[i] > max)
    {
     lessermax = max;
     max = array[i];
    }
    if ((array[i] > lessermax)&&(array[i] < max))
    {
     lessermax = array[i];
    }
}
// a questo punto i "nominati" sono tutti gli i tali che array[i] >=
lessermax
"Ivan Sofa n.1" <dromeda...@inwind.itDELETE> wrote in message
news:O4Bea.34182$Lr4.1...@twister2.libero.it...


 AAA[9].
Versione generica, che funziona su qualsiasi sequenza, compresi
ovviamente gli array:
  template <typename FwdIt, typename OutIt>
  OutIt ballottaggio( FwdIt begin, FwdIt end, OutIt dest )
  {
    typedef typename iterator_traits<FwdIt>::value_type value_type;
    int const size = distance( begin,  end );
    // controllo necessario per non superare la fine dell'array
    if (size < 3) {
      for (int index = 0; index < size; ++index)
        *dest++ = index;
      return dest;
    }
    // cerca la soglia
    FwdIt it = begin;
    ++it;
    value_type max_value = max( *begin, *it );
    value_type threshold = min( *begin, *it );
    ++it;
    for (; it != end; ++it) {
      if (*it >= max_value) {
        threshold = max_value;
        max_value = *it;
      }
      else if (*it > threshold) {
        threshold = *it;
      }
    }
    // spara fuori gli indici
    it = begin;
    for (int index = 0; it != end; ++index, ++it) {
      if (*it >= threshold)
        *dest++ = index;
    }
    return dest;
  }
Questa funzione fa due passate: la prima per cercare la soglia e la
seconda per tirare fuori gli indici.  E` possibile fare una sola
passata, raccogliendo gli indici in 2 contenitori, ma probabilmente
per array piccoli non ne vale la pena.
Esempi di utilizzo:
  vector<int> vec;
  copy( istream_iterator<int>(cin), istream_iterator<int>(), 
        back_inserter(vec) );
  ballottaggio( vec.begin(), vec.end(), ostream_iterator<int>(cout, " ") );
  cout << '\n';
  int AAA[10]={4,7,1,1,1,2,8,7,3,7};
  deque<int> indici;
  ballottaggio( AAA, AAA+10, back_inserter(indici) );
        Mauro
-- 
E` in corso la votazione per creare it.sport.atletica
Se sei interessato vota su news:it.news.votazioni

     }
Questo trova il mazzimo degli elementi di indice dispari e il massimo
degli elementi di indice pari, non i due valori piu` alti.
Per esempio, se AAA vale 2,9,1,8 il programma restituisce 0,1 invece
di 1,3.


     }
Qualcosa mi sfugge ? Inizialmente max_value e threshold
sono settati uguali ad il min e il max di due valori
dell'array (i primi due mi sembra).
Supponiamo che questi valori siano uguali e in particolare uguali al 
massimo, come in {8,8,6,7,1}.
Dopo di che non puoi piu' aggiornare il threshold,
perche' e' stato settato uguale al max_value....
ciao,
g.
Dopo iteri su tutti gli altri eleme

 Dopo iteri su tutti gli altri eleme
... ?


 secondo (o i secondi).
Il mittente del primo messaggio aveva detto:
 > int AAA[10]={4,7,1,1,1,2,8,7,3,7}
 > in questo caso la funzione dovrebbe segnalarmi AAA[1], AAA[6], AAA[7],
 > AAA[9].
 > diciamo le due più alte considerando eventuali parimerito.
ciao,
g.

Giovanni Resta ha scritto...

Ma ha ragione Mauro Casini.
-- 
Luc.

 Ma ha ragione Mauro Casini.
Cioe' allora il meccanismo sarebbe questo ?
1) se ci sono due o piu' elementi uguali al massimo, vengono restituiti
    tutti e soli gli elementi uguali al massimo.
2) altrimenti: Si restituisce l'elemento massimo piu' tutti gli elementi
uguali al secondo in ordine di grandezza.
Tanto per capire (nel qual caso buttate il mio codice...che risolveve un
altro problema....)
ciao,
g.

 uguali al secondo in ordine di grandezza.
Si, questo è l'algoritmo "Grande Fratello".
-- 
Luc.

ballottaggio (tipo grande fratello).
#include <iostream>
#include <cstdlib>
typedef struct { int val, pos; } pos_t;
int descsort(const void *p1, const void *p2)
{
    return (((pos_t*)p2)->val - ((pos_t*)p1)->val);    
}
void findmaxp(int val[], int n, int pos[]) 
{
     pos_t *a = new pos_t[n];
     for (int i = 0; i < n; i++) {
        a[i].val = val[i];
        a[i].pos = i;
     }    
     std::qsort(a, n, sizeof *a, descsort);
     for (int i = 0; i < n; i++) {
         pos[i] = a[i].pos;
     }
     delete [] a;
}
int main()
{
    int AAA[10] = { 4, 7, 1, 1, 1, 2, 8, 7, 3, 7 };
    int BBB[10] = { 5, 4, 8, 5, 1, 1, 2, 9, 2, 1 };
    int pos[10];
    int i, n = sizeof(AAA)/sizeof(AAA[0]);
    findmaxp(AAA, n, pos);          
    for (i = 0; i < 4; i++) {
        std::cout << "AAA pos = " << pos[i] << std::endl;
    }
    std::cout << std::endl;
    findmaxp(BBB, n, pos);          
    for (i = 0; i < 2; i++) {
        std::cout << "BBB pos = " << pos[i] << std::endl;
    }
    return 0;
}
-- 
Andrea Laforgia
www.geocities.com/andrealaforgia
"640kb of memory should be enough for anyone." -- Bill Gates.