[C] Efficienza Algoritmo

[Vincenzoflaminio]

Salve, sto cercando un modo per scrivere il seguente codice in meno righe.
Devo stilare un tabellone (stile Mondiali :D ) a 8 squadre e devo fare scontrare le squadre finchè non otterò una squadra vincitrice.
Ora il problema sta qua:

if ( (valoresquadra[0]* numerocasuale) > (valoresquadra[1]* numerocasuale) )
{
printf("valoresquadra prima di giocare 0 = %d e 1=%d \n",valoresquadra[0],valoresquadra[1]);
printf("ha vinto la squadra 0 \n");

if ((valoresquadra[2]* numerocasuale) > (valoresquadra[3]* numerocasuale) )
{
printf("valoresquadra prima di giocare 2 = %d e 3=%d \n",valoresquadra[2],valoresquadra[3]);
printf("ha vinto la squadra 0 e poi la 2 \n");

if ((valoresquadra[4]* numerocasuale) > (valoresquadra[5]* numerocasuale) )
{
printf("valoresquadra prima di giocare 4 = %d e 5=%d \n",valoresquadra[4],valoresquadra[5]);
printf("ha vinto la squadra 0 , poi la 2, poi la 4 \n");

if ((valoresquadra[6]* numerocasuale) > (valoresquadra[7]* numerocasuale) )
{
printf("valoresquadra prima di giocare 6 = %d e 7=%d \n",valoresquadra[6],valoresquadra[7]);
printf("ha vinto la squadra 0 , poi la 2, poi la 4, poi la 6 \n");
}
else
{
printf("valoresquadra prima di giocare 6 = %d e 7=%d \n",valoresquadra[6],valoresquadra[7]);
printf("ha vinto la squadra 0 , poi la 2, poi la 4, poi la 7 \n");

}

}
else
{
printf("valoresquadra prima di giocare 4 = %d e 5=%d \n",valoresquadra[4],valoresquadra[5]);
printf("ha vinto la squadra 0 , poi la 2, poi la 5");

}
}

else {
printf("valoresquadra prima di giocare 2 = %d e 3=%d \n",valoresquadra[2],valoresquadra[3]);
printf("ha vinto la squadra 0 e poi la 3");}
}
else {
printf("valoresquadra prima di giocare 0 = %d e 1=%d \n",valoresquadra[0],valoresquadra[1]);
printf("ha vinto la squadra 1 \n");
Questo è solo una parte di ciò che devo valutare perchè ad ogni ELSE io devo far riscontrare tutte le squadre nuovamente (Ogni squadra vincitrice
si scontrerà con la squadra vincitrice di un’altra partita fino ad arrivare ad una singola squadra vincitrice) . C'è modo di evitare tutte queste righe di codice?

[DanieleC88]

Innanzitutto, se moltiplichi ogni valore per "numerocasuale" e poi confronti, è lo stesso che confrontare i valori originali non moltiplicati.
Cioè, se hai:
k·x < k·y
dove k è costante, ti basta dire:
x < y
per esprimere lo stesso concetto.

Poi magari puoi ricorrere a roba di questo tipo:

http://it.wikipedia.org/wiki/Albero_del_torneo

:D

[Vincenzoflaminio]

Innanzitutto, se moltiplichi ogni valore per "numerocasuale" e poi confronti, è lo stesso che confrontare i valori originali non moltiplicati.

Poi magari puoi ricorrere a roba di questo tipo:

http://it.wikipedia.org/wiki/Albero_del_torneo

:D
Grazie della risposta. Si infatti devo mettere al posto di numerocasuale --> rand()%2 mentre purtroppo il tuo suggerimento preso da wiki credo non vada bene :
io devo aggiungere una riga di codice che mi riporti il conteggio delle vittorie fatte da una squadra
if ( (valoresquadra[0]* rand()%2) > (valoresquadra[1]* rand()%2) )
{
printf("valoresquadra prima di giocare 0 = %d e 1=%d \n",valoresquadra[0],valoresquadra[1]);
printf("ha vinto la squadra 0 \n");
punteggiosquadra[0]++;
punteggiosquadra[1]=0;

questo perchè il testo dell'esercizio chiede:
Una partita viene vinta da una squadra secondo la seguente regola
· la somma dei pesi di una squadra moltiplicata per un numero casuale
nell’intervallo [0, 1] è maggiore della corrispondente operazione sull’altra
squadra
· il processo si ripete finché non si ottiene un vincitore
Simulare 100 volte il torneo e ritornare l’elenco completo delle squadre in ordine decrescente di vincite
Sarò costretto a fare un infinità di nidificazioni di IF :mc:

[DanieleC88]

No, non accetto che si possa fare un codice con decine di if annidati. :D

Fammi capire meglio: con che criterio una squadra sfida l'altra? Cioè, è sempre vero che inizialmente la prima squadra sfida la seconda, e poi la terza sfida la quarta, etc..., e poi si ripete così per i vincitori?

[Vincenzoflaminio]

No, non accetto che si possa fare un codice con decine di if annidati. :D

Fammi capire meglio: con che criterio una squadra sfida l'altra? Cioè, è sempre vero che inizialmente la prima squadra sfida la seconda, e poi la terza sfida la quarta, etc..., e poi si ripete così per i vincitori?

Effettivamente è molto scocciante scrivere tutte queste righe di IF...:mad:
Allora il testo per il criterio di vittoria te l'ho riportato :
la somma dei pesi di una squadra moltiplicata per un numero casuale
nell’intervallo [0, 1] è maggiore della corrispondente operazione sull’altra
squadra
· il processo si ripete finché non si ottiene un vincitore

Per pesi di una squadra si intende il valore dei singoli giocatori sommato, che ho poi inserito in valoresquadra [] un array di 8 come le squadre.
Ma il problema non si presenta qui , il problema sta qua :
-ritornare l’elenco completo delle squadre in ordine decrescente di vincite-
Questo vuol dire che io devo ad ogni scontro tra squadre che avviene per 2 alla volta devo segnarmi in una variabile il numero delle vittorie effettuate dalla stessa.
Quindi non è un semplice ottavi di finale (sarebbero soltanto 4 incontri da disputare) io devo valutare ogni caso. Ti faccio un esempio
Se la prima faccio scontrare SQUADRA 0 vs SQUADRA 1 e vince la 1
aumento il valore dipunteggiosquadra[0]++;
punteggiosquadra[1]=0; se invece dovessere vincere l'altra squadra faccio un ELSE con i valori assegnati al contrario. Intanto le partite continuano nello stesso IF(nidifico) quindi Squadra 2 e Squadra 3 si scontrano . Gli scontri continunao nello stesso IF perchè devo sempre differenziarli i casi .. perchè era successo prima che la Squadra 0 avesse vinto e quindi avrebbe giocato un'altra partita ma se avesse vinto la Squadra 1 si sarebbe avuto un altro tabellone DAL TESTO ORIGINALE "Il torneo viene simulato facendo scontrare due squadre alla volta. Ogni squadra vincitrice
si scontrerà con la squadra vincitrice di un’altra partita fino ad arrivare ad una singola squadra vincitrice"

Spero di essere stato chiaro e grazie mille per l'interessamento

[DanieleC88]

Ok, quindi la situazione è che tu in un'array hai sommato i valori di tutti i giocatori di ogni squadra e li hai salvati nelle corrispondenti posizioni di indici [0 ... 7].

Io quello che cercavo di capire nell'ultimo post è proprio il come scegliere gli scontri da fare: ovvero, se il criterio è "squadra0 contro squadra1", poi "squadra2 contro squadra3", etc..., o se ci fossero particolari disposizioni a riguardo.

Da quanto ho capito, gli scontri diretti sono ad eliminazione, quindi la squadra che perde uno scontro non avrà modo di procedere oltre?

Darò per assunto questo punto, e ti propongo quindi di fare una cosa del tipo: conserva un'array di interi, che saranno corrispondenti ai punteggi finali delle squadre. Poi prepara un'array di struct in cui ogni posizione conterrà almeno due informazioni: il numero della squadra (quindi l'indice in cui recuperare il punteggio nel primo array) ed il suo valore. Partendo da quest'array, che inizialmente avrà 8 elementi, ti basterà fare un ciclo nel quale prendi a due a due le squadre, le fai scontrare tra di loro, e ricopi la vincitrice nella prima metà dell'array, nella posizione corrispondente all'indice dello scontro appena effettuato, e ne incrementerai il punteggio di conseguenza. Alla fine così avrai un array di dimensione dimezzata, e potrai andare avanti così finché non resterà un'unica squadra.

Ti faccio un esempio di ciò che intendo in pseudocodice:
struct _squadra_s {
int numero;
int valore;
};

typedef struct _squadra_s Squadra;
#define N_SQUADRE 8

int main()
{
unsigned int dimensione = N_SQUADRE;
Squadra squadre[N_SQUADRE] = { ... }; /* qui riempi l'array iniziale con le squadre */
int punteggi[N_SQUADRE] = { 0 }; /* array dei punteggi */

while (dimensione != 1) {
for (int i = 0; i < dimensione; i += 2) {
Squadra vincitore;
Squadra s1 = squadre[i + 0];
Squadra s2 = squadre[i + 1];

/* fai scontrare s1 ed s2 e trova il vincitore */
vincitore = (...vince squadra1...) ? s1 : s2;
squadre[i / 2] = vincitore;
++(punteggi[vincitore.numero]);
}

dimensione = (dimensione / 2);
}

/* et cetera */

return 0;
}

Infine avrai un'array di punteggi, che potrai usare per calcolare le squadre vincitrici in ordine decrescente.
Se non ho capito male i requisiti, una cosa del genere potrebbe bastare. :)

ciao ;)

[Vincenzoflaminio]

Sei stato veramente di grande aiuto, non ci sarei mai arrivato da solo ...
solo una cosa non ho capito :rolleyes: in che modo stampo i valori in ordine decrescente
Questo è quanto ho scritto
struct _squadra
{
int player[11]; /* sono gli 11 giocatori della squadra
int valore[8]; /* il punteggio della squadra
int numero[8]; /* per indicare l'indice della squadra
};
typedef struct _squadra Squadra;

typedef struct _squdra Squadra

int main()
{

Squadra arraysquadre[8] = {0,1,2,3,4,5,6,7};
int dimensione = 8;
int numvittoriesquadra[8]={0};
int q=0;

/* Inserisco gli indici delle squadre nel array squadra
for (i=0;i<8;i++)
{
array_squadra.numero[i]=q;
q++;
}



while (dimensione != 1) {
for (i = 0; i < dimensione; i += 2) {
Squadra vincitore;
Squadra s1 = array_squadra[i + 0];
Squadra s2 = array_squadra[i + 1];

if ((s1.valore[0]* rand()%2 ) > (s2.valore[1]* rand()%2)
{
vincitore = s1;
numvittoriesquadra[vincitore.numero]++ ;
}
else
{
vincitore = s2;
numvittoriesquadra[vincitore.numero]++ ;
array_squadra[i/2]=vincitore;
}

}

dimensione = (dimensione / 2);

}


In aggiunta mi segnala un errore sulle righe in rosso :
array subscript is not an integer
C'è qualche problema con vincitore.numero infatti se lo cambi con un valore numerico passa tranquillamente al compilatore

[rеpne scasb]

■

[DanieleC88]

solo una cosa non ho capito :rolleyes: in che modo stampo i valori in ordine decrescente
Ti basterebbe anche un qualsiasi algoritmo di ordinamento: ottieni l'array ordinato in maniera crescente, stamperai al contrario e il gioco è fatto.
In aggiunta mi segnala un errore sulle righe in rosso :
array subscript is not an integer
C'è qualche problema con vincitore.numero infatti se lo cambi con un valore numerico passa tranquillamente al compilatore
Per forza, li hai dichiarati come array! Perché? Un intero basta. ;)

[DanieleC88]

Squadra arraysquadre[8] = {0,1,2,3,4,5,6,7};
Scusa, ma ti compila sta cosa? :eekk:

[Vincenzoflaminio]

Scusa, ma ti compila sta cosa? :eekk:

Si...passa anche se ora che mi fai notare andrebbe inizializzato in questo modo:
Squadra arraysquadre[8] = {{50,0}{30,1} etc. ... }

ma io il primo dei due valori (INT VALORE) non lo devo inizializzare perchè non lo conosco ancora all'iniziio del programma ma è il risultato di questa operazione:

for (w=0;w<8;w++)
{
for (r=0;r<11;r++)
{
array_squadra[w].valore += array_giocatori[array_squadra[w].player[r]].valore;
}

Quindi credo che devo lasciare soltanto Squadra arraysquadre[8] senza dichiarare nulla giusto?


rеpne scasb anche quello tuo andrebbe bene infatti la ricorsione è un argomento di studio che ho incontrato , però tu non hai usato dei tipi Strutturati si possono passare valori di questo tipo : squadra.valore
all'interno di Function e Procedure?

[DanieleC88]

Guarda, non so che compilatore stai usando, ma dovrebbe darti decine di errori. :mbe:
Attiva tutti i warning e dagli ascolto. ;)

[Vincenzoflaminio]

Guarda, non so che compilatore stai usando, ma dovrebbe darti decine di errori. :mbe:
Attiva tutti i warning e dagli ascolto. ;)

Uso Dev c++ e funziona alla grande beh devo ringraziare te che mi hai indirizzato sei stato gentilissimo
Ecco com'è l'output del .exe :
Mi trovo solo in difficoltà con i numeri delle squadre perchè io al momento ho usato il contatore "i" come numero squadra che visualizzo a schermo e quindi al secondo ciclo il numero squadra riparte da 0 ...

http://img821.imageshack.us/img821/6213/torneo.jpg