Si tratta di un esercizio molto semplificato inerente i tornei ad eliminazione diretta, la tipologia in assoluto più semplice. Non è richiesto di affrontare il sia pur modesto incremento di complessità introdotto dall'uso di punteggi o graduatorie, o il caso di un numero di squadre che non sia una potenza intera del due.
In questi casi, la struttura dati più idonea è anche una delle più semplici: un array di strutture che contengano, come minimo, il nome del partecipante o squadra ed un flag che indichi l'eliminazione.
Ricordate sempre che, fin dai più remoti tempi del COBOL e delle schede perforate, "eliminare" un record quasi sempre significa solo marcarlo come cancellato...
La stocasticità richiesta può essere validamente implementata scegliendo inizialmente una permutazione dell'ordine lessicografico in cui vengono introdotte le squadre, ad esempio col sempreverde algoritmo di Knuth (per amor di filologia si dovrebbe parlare di "algoritmo in-place di Knuth-Durstenfeld, derivato dal metodo Fisher-Yates" come recentemente riconosciuto da varia letteratura). A questo punto, la richiesta di pseudocasualità è automaticamente soddisfatta, ed è possibile realizzare la prima tornata di accoppiamenti per posizioni fisse: ad esempio, primo vs ultimo, secondo vs penultimo, e così via. La squadra sorteggiata come perdente ad ogni incontro sarà marcata con un valore convenzionale nell'apposito campo della struttura.
Nei passaggi successivi, gli indici delle due squadre di ciascun incontro saranno determinati banalmente con una scansione, ricercando rispettivamente a partire dall'indice più basso e più alto i record non ancora eliminati.
Questa soluzione naif offre tutti i vantaggi di una facilissima implementazione, con un overhead estremamente modesto aggiunto principalmente dalla ricerca lineare (si tratta sempre di numeri estremamente piccoli), e nonostante l'apparenza risulta facilmente adattabile anche a casi più complessi, pur nella stessa tipologia di tornei ad eliminazione diretta.
Ultima nota: alberi binari e matrici torneo (una parte consistente e ben studiata della teoria dei grafi) sono ampissimamente usati per la rappresentazione e l'analisi dei risultati, come pure per più complessi problemi combinatori e di ottimizzazione, ma in casi come il presente sono semplicemente eccessivi. Tuttavia, l'uso di un albero completamente preallocato nei cui nodi copiare, ad ogni tornata, un semplice puntatore alla singola struttura che descrive squadra, punteggi eccetera rientra comunque nel novero delle soluzioni più banali.
Rispondi quotando