View Full Version : algoritmo tornei: BERGER
qualcuno mi sa spiegare come funziona l'algoritmo di berger, o anche degli altri per arrivare allo stesso risultato.
Un algoritmo che possa stilare il calendario di un campionato all'italiana dati i nomi e numero degli iscritti al torneo.
per campionato all'italiana intendo quallo come il nostro di calcio: ci sono piu turni ed a ogni utrno agni squadra gioca, a fine girone ogni squadra deve aver giocato con tutte le altre.
Proprio come quello di serie A.
grazie mille, m serve per un progetto all'università e non so dove sbattere la testa.
copiato da un sito:
L'algoritmo per calcolare gli n/2 accoppiamenti di tutte le n(n-1)/2 del girone di andata di un campionato di n squadre, per le n-1 giornate è il seguente, ed è valido solo per n pari.
* per ogni giornata g che va da 1 a n-1
o per ogni partita i che va da 1 a n/2
+ la partita i è giocata da una qualsiasi coppia di squadre tali che:
# non hanno mai giocato in qualsiasi giornata
# le restanti squadre che non sono state ancora selezionate per giocare nella giornata attuale
non hanno mai giocato nelle giornate precedenti
ok grazie per il programmino .xls, ma come faccio a vederne l'implementazione.
scusa ma non me ne intendo di questo linguaggio, cosa devo fare per risalira all'algoritmo???
ok si c'ero arrivato anche da solo dopo aver scritto il messaggio.
cmq mi potresti dire a parole l'algoritmo? io devo implementarlo in java e non conosco bene il visual basic.
Originariamente inviato da marxt
cmq mi potresti dire a parole l'algoritmo? io devo implementarlo in java e non conosco bene il visual basic.
il mio non va bene? :O
il bulk è questo:
Sub Torneo1(N, Part() As Integer)
N1 = N - 1
For i = 1 To N1
j1 = i - 1: j2 = i + 1
For iP = 1 To N / 2
j1 = j1 + 1: If j1 > N1 Then j1 = 1
j2 = j2 - 1: If j2 < 1 Then j2 = N1
Part(i, iP, 1) = j1: Part(i, iP, 2) = j2
Next iP
Part(i, 1, 2) = N
Next i
End Sub
o questo:
Sub Torneo2(N, Part() As Integer)
N1 = N - 1: N2 = N / 2
For i = 1 To N1
j = i
For iP = 1 To N2
Part(i, iP, 1) = j: j = j + 1: If j > N1 Then j = 1
Next iP
For iP = N2 To 2 Step -1
Part(i, iP, 2) = j: j = j + 1: If j > N1 Then j = 1
Next iP
Part(i, 1, 2) = N
Next i
End Sub
a piacere. :)
kingv: l mio non va bene?
non si capisce niente, io chiedo l'algoritmo....
a2000: il bulk è questo: ..................................................
grazie, al max se hai in giro anche il codice java è perfetto, senno, cerco di capire questo.
i è l'indice della giornata
j sono gli indici di squadra
iP è l'indice di partita della giornata i-esima
Part(i, iP, 1) contiene l'indice della 1a squadra della giornata i-esima, partita iP-esima
Part(i, iP, 2) contiene l'indice della 2a squadra della giornata i-esima, partita iP-esima
gli accoppiamenti alla giornata i-esima vengono creati con un algoritmo circolare (e infatti si chiamano tornei circolari):
es.
6 squadre
seconda giornata i=2
a meno dell'ultima squadra (6), il blu (prima squadra) circola in avanti, il rosso (seconda squadra) circola all'indietro
la partita j-j (2-2) viene sostituita con la partita j-N (2-6)
1 2 3 4 5 (6) >> start
1 2 3 4 5 (6) >> 2-2 >> 2-6
1 2 3 4 5 (6) >> 3-1
1 2 3 4 5 6 >> 4-5
totale nove (9) righe.
nell'isola di Java forse meno. :)
adesso fammi tornare ai bilanci locali all'interfaccia.
ciao.
quindi se uno va in un senso e l'altro nell'altro si arriverà ad avere partite come 3-1 e 1-3, e una delle due va pero scartata giusto??
ma questa rotazione cicolare va fatta ad ogni giornata? e come tengo conto delle partite gia giocate nei turni precendenti?
Originariamente inviato da marxt
quindi se uno va in un senso e l'altro nell'altro si arriverà ad avere partite come 3-1 e 1-3, e una delle due va pero scartata giusto??
no. se ti fermi a N/2 partite non succede e non c'è bisogno di scartare niente.
fatti un esempio a mano.
ma questa rotazione cicolare va fatta ad ogni giornata? e come tengo conto delle partite gia giocate nei turni precendenti?
l'algoritmo ne tiene conto: è tutto automatico e semplice.
(è la differenza tra un algoritmo matematico e uno informatico)
fatti un esempio a mano.
ok ci sono ho capito!!!!!
un ultima cosa:
con questo facendo n/2 passaggi ottengo le partite di un turno.
ma per i turni successivi devo partire da un punto diverso però, altrimenti i risultati sono uguali.
Se invece parto da dove mi sono fermato:
1234 5 6 >>4-5
il prossimo sarà:
1234 5 6 >>5-4
dovrei quindi saltare questo??
dimmi come partire poi per ogni turno successivo
Originariamente inviato da marxt
ok ci sono ho capito!!!!!
un ultima cosa:
con questo facendo n/2 passaggi ottengo le partite di un turno.
ma per i turni successivi devo partire da un punto diverso però, altrimenti i risultati sono uguali.
...
dimmi come partire poi per ogni turno successivo
molto semplice:
N1 = N - 1
For i = 1 To N1
....
Next i
parti da 1 poi 2, 3 .... fino a N-1 (5 nell'esempio).
ossia giornata 1, 2, 3 .... N-1
tutto very light.
ok ci sono.
ho fatto a mano tutto per n=6
il trucco è spostare ogni volta il punto di partenza: es turno 4 allora il blu è sul 3 a il rosso sul 5 giusto???
turno 5 allora il blu sul 4, il rosso dovrebbe essere sul 6 ma non puo quindi va sull'1!!
e giusto???
dimmi di si ti prego!!!!!
quasi ... ma più semplice :)
turno 5:
inizio con il blu sul 4, il rosso sul 6 (regolare)
partita 1: blu su 5, rosso su 5 >>> partita 5-5 sostituita con 5-6
partita 2: blu su 1 (rotazione a N-1 squadre), rosso su 4 >>> partita 1-4
partita 3: blu su 2 , rosso su 3 >>> partita 2-3
tutto regolare.
l'unica eccezione è la sostituzione della partita j-j (5-5) con la partita j-N (5-6).
:)
funziona anche per N dispari. :)
Scusate se riporto in top questa discussione un po' vetusta, ma dall'esempio in xml che ho trovato in allegato qui, l'algoritmo non funziona correttamente per le squadre dispari: ci sono squadre che giocano più delle altre, quando invece ogni squadra dovrebbe avere un turno di riposo a giornata...
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.