PROBLEMA IN C

[nepero87]

Salve a tutti!

Qualcuno di voi conosce un algoritmo in linguaggio C che mi permetta di individuare, in un vettore di interi, i tre numeri più grandi? Naturalmente il tutto dovrebbe essere generalizzabile...

[lorven]

Basta usare un qualunque algoritmo di sort per ordinare l'array in senso crescente, dal quale, una volta ordinato, selezionare le 3 componenti di indice più alto.

[nepero87]

Si, certo, ma mi è espressamente vietato ordinare il vettore, se no sarebbe troppo facile...

Forse dovrei usare una funzione di appoggio che scorre il vettore cercando ogni volt il max, escludendo ia via gli altri max già trovati...

[lorven]

Allora si può procedere in questo modo:
1. assegnare a 3 variabili distinte, A B C, i primi 3 elementi dell'array V
2. effettuare un ciclo, da 4 a n (se n è la dim. dell'array), nel quale si verifichi se l'elemento corrente dell'array, V(i) risulta maggiore di A, B e C: in caso affermativo, sostituire con V(i) il più piccolo tra A, B, C.
Alla conclusione della iterazione, A, B, C conterranno i 3 valori maggiori dell'array, non necessariamente tra loro ordinati.
Se si vogliono ottenere A B C ordinati, è sufficiente a questo punto qualche confronto.

[nepero87]

Ok, ora ci provo...

[lorven]

Risolto?

[nepero87]

Oh salve...

Diciamo che l'ho praticamente risolto, anche se alla fine non ottengo i tre massimi, ma solo i primi due... Il terzo risulta uguale al secondo... Comunquee è già abbastanza...

Piuttosto, ora devo postare un problema, nell'indice del forum, riguardante una lista... Visto che mi è sembrato che tu ne capisca un bel po' di C, perchè non ci dai un'occhiata?

[lorven]

Vedo di postare la mia soluzione tradotta in C, poi pensiamo ad altro...

[nepero87]

#include
#include
#include
#define N 11

int check (int*,int);

main() {

srand(time(NULL));

int num[N],i,k,podio[3]={-1},imax;

for (i=0;i num=rand()%25;

for (k=0;k do imax=rand()%N;
while (check(podio,imax));
for (i=0;i if (num>num[imax])
if (!(check(podio,i))) imax=i; }
podio[k]=imax; }

for (i=0;i printf ("%d ",num);

for (i=0;i<3;i++)
printf ("\n\n%d",num[podio]);

getchar();
}

int check (int massimi[],int x) {

int i,flag=0;
for (i=0;i<3;i++) if (massimi==x) flag=1;

return flag;
}

Non è la tua soluzione, ma una mia vecchia bozza... La funzione check controlla se nel vettore podio, che deve contenere fli indici dei tre massimi, è già presente un indice che estraggo a caso... Ma qualcosa non va...

[lorven]

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

/******************************************************************************
************ Trova Le 3 Componenti Maggiori In Un Array Di Interi *************
******************************************************************************/

int n,i,a,b,c;  // n: dim. array; i: indice array; a,b,c: le 3 componenti
int num[100];   // maggiori di num; num: array di interi
char cont = 's';
/****************************** ORD_ABC **************************************/
void ord_abc()         // Ordina a b c
{
int x;

if (a>b)
   {
    x=a;
    a=b;
    b=x;
   }
if (a>c)
   {
    x=a;
    a=c;
    c=x;
   }
if (b>c)
   {
    x=c;
    c=b;
    b=x;
   }
return;                // A questo punto, a contiene il minore tra
}                      // i 3 valori maggiori.

/****************************** INP_ARRAY ************************************/
void inp_array()       // Input array.
{
int vmax = 10;

srand(time(0));
cout << "Inserire dimensione array (>=3) : ";

do                     // Acquisisce la dimensione dell'array
  cin >> n;            // controllando che sia >= 3.
while (n<3);

cout << "Inserire valore massimo per le componenti dell'array: ";
cin >> vmax;           // Determina il valore massimo per gli elem. di num

for (i = 1; i<=n; i++) // Riempie array con valori pseudocasuali.
    {
     num[i]=rand()% vmax + 1;
    }
cout << endl;
return;
}
/****************************** RISULTATI ************************************/
void risultati()
{
int i;
cout << "Risultato: " << endl;
cout << "array di input: " << endl;

for (i = 1; i<=n; i++)                  // Stampa array.
      cout << num[i] << " ";

cout << endl;
cout << "I 3 valori maggiori sono: ";
cout << a <<" " << b << " " << c;       // Stampa i 3 valori maggiori,
cout << endl << endl;                   // ordinati.
}
/****************************** M A I N **************************************/
void main()
{

cout << "Trova i tre elementi maggiori in un array di interi" << endl;
do
{
   inp_array();              // Comanda l'acquisizione dell'array.
   a=num[1];                 // Inizializza le 3 componenti maggiori
   b=num[2];                 // con le prime 3 componenti dell'array.
   c=num[3];

   for (i = 4; i<=n; i++)    // Scandisce il resto dell'array.
       {
        ord_abc();           // Comanda il riconoscimento del
                             // minore tra e b c e lo pone in a.
        if (num[i] > a)      // Se la componente in esame è maggiore
                             // di almeno uno tra a b c,
             a=num[i];       // sostituisce il minore tra a b c
       }                     // con la stessa componente.

   risultati();              // Stampa i risultati.
   ord_abc();                // Riordina a b c

   cout << "continua? (S/N):  ";
   cin >> cont;
}
while ((cont != 'n') && (cont != 'N'));

return 0;
}

dovrebbe funzionare, anche se non è molto elegante
p.s.: a che ti serve una generazione di indici casuali?

[nepero87]

Uhm... che strano il tuo programma... ma è in C++, vero? Io sono alle prime armi, e ci sono parole come "cout" che non ho mai trovato nella terminologia C...

Comunque la generazione di indici casuali mi poteva servire, per il fatto che poi nel mio programma la funzione check avrebbe comunque fatto da filtro, controllando che venisse estratto solo un indice che non era già all'interno del vettore podio, successivamente avrei messo un controllo per verificare che l'elemento con quell'indice fosse un massimo, e in caso affermativo lo avrei messo in podio...

Clear?

[lorven]

Con la libreria standard iostream del C++ , input ed output di un programma vengono gestiti da due flussi di dati ( stream): cin per l'input e cout per l'output. Comunque, secondo me, un pò strano è l'uso degli indici casuali!

[Res1]

Ti rispondo in BASIC, è tutto qui:


FOR i% =1 TO UBOUND(V)

IF V(i%)>= Max1 then
Max1 = V(i%)

ELSEIF V(i%)>= Max2 then
Max2 = V(i%)

ELSEIF V(i%)>= Max3 then
Max3 = V(i%)

END IF

NEXT

Ciao
Res

[nepero87]

Ciao, un paio giorni fa mi sono messo al pc e l'ho risolto in un quarto d'ora più o meno... Insieme a un mio amico... Posto il codice:

#include
#include
#include
#define N 11

int check (int*,int);

main() {

srand(time(NULL));

int num[N],i,k,podio[3]={0},max;

for (i=0;i num=rand()%25;
printf ("%3d",num); }

for (k=0;k<3;k++) {
max=0;
for (i=0;i if (num>max)
if (!check(podio,num)) max=num; }
podio[k]=max; }

printf ("\n\nTre massimi:\n\n");
for (i=0;i<3;i++)
printf ("\n%d ",podio);

getchar();
}

int check (int massimi[],int x) {

int i,flag=0;
for (i=0;i<3;i++)
if (massimi==x) flag=1;

return flag;
}

E' un algoritmo molto semplice, la funzione check controlla semplicemente se il massimo estratto sia già contenuto nel vettore di massimi...

[lorven]

Temo che il programma Basic non funzioni sempre: se nel vettore, ad esempio, ci sono valori già ordinati, viene via via modificato MAX1 e restano sempre invariati MAX2 e MAX3. Può comunque succedere anche con altri valori.

[lorven]

@Nepero:
il tuo programma non ammette ex-aequo nel podio!
e se ti sviluppi un programma in 1/4 d'ora, la prossima volta non ti rispondo! Il mio prg ha richiesto 20 minuti!
Scherzo, naturalmente ...

[Res1]

Hai ragione, questo è corretto

FOR i% =1 TO UBOUND(V)

IF V(i%)>= Max1 then ' trovato un altro primo massimo, shiftiamo gli altri due valori, poi assegnamo il nuovo al primo posto
Max3 = Max2
Max2 = Max1
Max1 = V(i%)

ELSEIF V(i%)>= Max2 then ' trovato secondo massimo, shiftiamo il vecchio valore e assegniamo il nuovo secondo
Max3 = Max2
Max2 = V(i%)

ELSEIF V(i%)>= Max3 then ' trovato terzo massimo che assegnamo a Max3.X Se siamo qui V(i%) non può essere nè Max1 nè Max2.
Max3 = V(i%)

END IF

NEXT

[lorven]

Ok!
Però farei confronti solo per >, non >=

[Res1]

E' una mia deformazione, però non vedo la differenza, a meno che nel vettore ci possano essere numeri ripetuti.

[Res1]

Ora ricordo il motivo.
Misurai i tempi di esecuzione e l'istruzione "<=" mi risultò più veloce della "<", forse a causa di un paio di istruzioni assembler di meno e dal tipo di compilatore che usavo.
Facevo spesso questi test ottimizzanti quando si trattava di milioni di records da spazzolare e testare nel minor tempo possibile.
Ovviamente solo se al scelta era indifferente per il risultato.

[nepero87]

e se ti sviluppi un programma in 1/4 d'ora, la prossima volta non ti rispondo! Scherzo, naturalmente ...

@lorven

Il fatto è che certi giorni sono particolarmente ispirato, e fortunatamente il giorno dell'esame era uno di questi...! La soluzione di quel programma non era affatto difficile, in effetti...