[C++]Consiglio struttura dati da utilizzare

[lipoto]

Ho un numero pari a 2^n di oggetti di tipo "squadra" (ad esempio ho la squadra milan, inter, roma ecc)

Devo estrarre casualmente della coppie da fare affrontare tra di loro, al secondo turno dovrò di nuovo estrarre casualmente delle coppie da far affrontare tra i vincitori, e così via fino al vincitore del torneo.

Per ora sto utilizzando un vettore di tipo "squadra" in cui tengo memorizzate le varie squadre, ma sto avendo molti problemi ad implementare questa funzione di accoppiamento tra le squadre.

Potrei utilizzare una struttura dati più adatta, rispetto ad un vettore, per affrontare questo tipo di problema?

[minomic]

Ciao,
quali problemi stai incontrando, di preciso?

[lipoto]

Come prima idea avevo pensato di ordinare il vettore in modo che le squadre che si dovessero affrontare si trovassero in posizione adiacente, ad es se ho juve vs milan e juve si trova in posizione i milan si troverà in posizione i+1. Questa soluzione ha diverse pecche, soprattutto nel caso dei turni successivi al primo dove dovrei eliminare o comunque "dimenticarmi" della presenza delle squadre perdenti. Inoltre, per determinare se una squadra vince o perde, devo implementare una funzione che effettua diverse operazioni sulle squadre estratte, quindi mi sarebbe utile memorizzare le coppie come unità singola, invece che in modo adiacente nel vettore. Spero di essermi spiegato al meglio....

[minomic]

Ok, quindi se una squadra perde viene eliminata, giusto?

Secondo me puoi farlo sempre con un vettore, ma eviterei di riordinarlo come fai tu... Una possibile idea sarebbe di definire una classe o una struttura "squadra", poi creare un array di squadre come hai fatto. L'operazione di sorteggio di due squadre la puoi ricondurre alla generazione di due numeri casuali compresi tra zero e n-1, dove n è il numero di squadre.

Per quanto riguarda la decisione tra chi vince e chi perde puoi sempre implementare una funzione

... gioca_partita(Squadra a, Squadra b)

che prenda in input le due squadre che hai sorteggiato e restituisca in output quello che vuoi: la vincente, un valore convenzionale, il risultato, ecc.

Al passaggio successivo puoi memorizzare le squadre rimaste in un vettore più piccolo (la sua dimensione sarà la metà di quello di partenza) e proseguire fino al match finale.

[lipoto]

Sisi, infatti le squadre sono già degli oggetti su cui operano delle funzioni (tipo gioca_partita e altre) e con delle variabili private (tipo il nome, una variabile di stato che indica se hanno vinto o perso ecc). Inoltre la funzione che genera un valore casuale tra 0 e n-1 l'ho implementata e funziona bene. Però, le richieste del programma mi impongono si stampare a video tutti i sorteggi avvenuti, poi di prendere la prima coppia sorteggiata, farla scontrare, decretare un vincitore, faccio scontrare la seconda coppia ecc. Poi dal secondo turno estrarre solo le squadre vincenti e così via...I mio prblema principale è come estrarre solo squadre vincenti dal secondo turno in poi e come "ricordare" i vari occoppiamenti, dato che prima devo stamparli a video e solo dopo farle scontrare

[minomic]

Allora potresti definire una classe o struttura "Partita" che contenga i nomi delle due squadre che sorteggi. Quindi crei un array di queste partite (così memorizzi gli accoppiamenti) e chiami la funzione gioca_partita direttamente sull'oggetto Partita[i], che appunto conterrà i riferimenti alle due squadre coinvolte.

[lipoto]

Ho appena pensato che potrei allocare dinamicamente una matrice contenente elementi di tipo squadra, che ha "numero di squadre\2" righe e 2 colonne (al primo turno). Potrei scorrere la matrice per righe in modo da memorizzare nelle due celle adiacenti lungo una riga le due squadre che devono affrontarsi ed inserire nella classe squadra un variabile che mi indichi se la squadra ha vinto la partita precedente e memorizzarla in una cella esclusivamente se ha vinto. Sapendo che dovrò riallocare la matrice ad ogni turno con un numero di righe dimezzato di un fattore 2 rispetto a quello precendente. Vedrò quale tipo di implementazione tra quello proposto da te e questo viene meglio. Per il momento grazie. Farò sapere se ce l'ho fatta o se avrò altri problemi (molto probabilmente xD)

[minomic]

Ok, prova e poi ci fai sapere come va.

[lipoto]

Un'ultima domandina, conosco in modo blando gli alberi, secondo voi si potrebbe risolvere utilizzando questo tipo di struttura dati?

[minomic]

Non sono sicuro, ma diciamo che sarebbe un albero binario "al contrario" rispetto a come viene solitamente utilizzato. Nel senso che di solito si rappresenta a partire dalla radice per arrivare alle foglie, mentre a te interesserebbe partire dalle foglie (tutte le squadre) per arrivare alla radice (squadra vincitrice). E qui dovresti gestire la costruzione "al contrario" e la logica padre-figlio dell'albero (di fatto tu genereresti un padre a partire da due figli o comunque un nodo a partire da altri due).
Non so fino a che punto ti convenga implementare un albero: non vorrei che l'overhead introdotto da una struttura dati non banale e con la quale non hai molta pratica finisse per annullare i possibili vantaggi.