algoritmo tornei: BERGER

[marxt]

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.

[kingv]

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

[a2000]

g.a.c.

[a2000]

.

[marxt]

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???

[a2000]

Excel > Alt+F11

[marxt]

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.

[kingv]

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?

[a2000]

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.

[marxt]

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.

[a2000]

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

[a2000]

totale nove (9) righe.

nell'isola di Java forse meno.

[a2000]

adesso fammi tornare ai bilanci locali all'interfaccia.
ciao.

[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??

ma questa rotazione cicolare va fatta ad ogni giornata? e come tengo conto delle partite gia giocate nei turni precendenti?

[a2000]

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.

[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.

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

[a2000]

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.

[marxt]

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!!!!!

[a2000]

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).

[a2000]

funziona anche per N dispari.