Apri il menu principale

L'algoritmo di Berger è un algoritmo usato per stilare un calendario (diviso in giornate o turni) di una competizione sportiva che abbia la formula del girone all'italiana: prende il nome dal suo inventore, lo svizzero Johann Berger.[1]

Il calcoloModifica

Con un numero pari di squadre partecipanti, l'algoritmo calcola "N:2" accoppiamenti per ogni giornata.[2]

  • Per ogni giornata «g» compresa tra 1 e «n−1»;
  • Per ogni incontro «i» compreso tra 1 e «n:2»;
  • L'incontro «i» abbina due squadre in base a questi criteri:
      1. non sono state ancora abbinate
      2. le restanti squadre - non selezionate - non siano state a loro volta già accoppiate.

ImplementazioniModifica

Vi sono funzioni che implementano l'algoritmo ponendo a parametro l'array con i nomi delle squadre, in numero pari, elaborando il calendario di un girone (stampato in video).

Nell'eventualità di un numero dispari di squadre, ad ognuna di esse sarà abbinato l'elemento «riposo» di volta in volta. I vincoli per squadre che condividano lo stesso campo sportivo sono risolvibili tramite un'alternanza tra incontri in casa e fuori casa.[3]

Una implementazione relativa al gioco degli scacchi dove ogni giocatore alterna il bianco ed il nero nei turni si trova nel riferimento[4].

JavaModifica

Algoritmo elaborato tramite Java.

public void AlgoritmoDiBerger(String[] squadre){
        
    int numero_squadre = squadre.length;
    int giornate = numero_squadre - 1;
      
    /* crea gli array per le due liste in casa e fuori */
    String[] casa = new String[numero_squadre /2];
    String[] trasferta = new String[numero_squadre /2];

    for (int i = 0; i < numero_squadre /2; i++) {
        casa [i] = squadre[i]; 
        trasferta[i] = squadre[numero_squadre - 1 - i]; 
    }
    
    for (int i = 0; i < giornate; i++) {
        /* stampa le partite di questa giornata */
        System.out.printf("%d^ Giornata\n",i+1);

        /* alterna le partite in casa e fuori */
        if (i % 2 == 0) {
            for (int j = 0; j < numero_squadre /2 ; j++)
                 System.out.printf("%d  %s - %s\n", j+1, trasferta[j], casa[j]); 
        }
        else {
            for (int j = 0; j < numero_squadre /2 ; j++) 
                 System.out.printf("%d  %s - %s\n", j+1, casa[j], trasferta[j]); 
        }
    
        // Ruota in gli elementi delle liste, tenendo fisso il primo elemento
        // Salva l'elemento fisso
        String pivot = casa [0];
  
        /* sposta in avanti gli elementi di "trasferta" inserendo 
           all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */
        String riporto = shiftRight(trasferta, casa [1]);

        /* sposta a sinistra gli elementi di "casa" inserendo all'ultimo 
           posto l'elemento "riporto" */
        shiftLeft(casa, riporto);

        // ripristina l'elemento fisso
        casa[0] = pivot ;
    } 
}

Variante perfettamente funzionante:

public void AlgoritmoDiBerger(String[] squadre){
 
    int numero_squadre = squadre.length;
    int giornate = numero_squadre - 1;
 
    /* crea gli array per le due liste in casa e fuori */
    String[] casa = new String[numero_squadre /2];
    String[] trasferta = new String[numero_squadre /2];
 
    for (int i = 0; i < numero_squadre /2; i++) {
        casa [i] = squadre[i]; 
        trasferta[i] = squadre[numero_squadre - 1 - i]; 
    }
 
    for (int i = 0; i < giornate; i++) {
        /* stampa le partite di questa giornata */
        System.out.printf("%d^ Giornata\n",i+1);
 
        /* alterna le partite in casa e fuori */
        if (i % 2 == 0) {
            for (int j = 0; j < numero_squadre /2 ; j++)
                 System.out.printf("%d  %s - %s\n", j+1, trasferta[j], casa[j]); 
        }
        else {
            for (int j = 0; j < numero_squadre /2 ; j++) 
                 System.out.printf("%d  %s - %s\n", j+1, casa[j], trasferta[j]); 
        }
 
        // Ruota in gli elementi delle liste, tenendo fisso il primo elemento
        // Salva l'elemento fisso
        String pivot = casa [0];
 
        /* sposta in avanti gli elementi di "trasferta" inserendo 
           all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */
		   
 		String riporto = trasferta[trasferta.length - 1];
		trasferta = shiftRight(trasferta, casa[1]);

        /* sposta a sinistra gli elementi di "casa" inserendo all'ultimo 
           posto l'elemento "riporto" */
		   
        casa = shiftLeft(casa, riporto);
 
        // ripristina l'elemento fisso
        casa[0] = pivot ;
    } 
}
 
 private String[] shiftLeft(String[] data, String add) {
		String[] temp = new String[data.length];
		for (int i = 0; i < data.length-1; i++) {
			temp[i] = data[i + 1];
		}
		temp[data.length - 1] = add;
		return temp;
	}

	private String[] shiftRight(String[] data, String add) {
		String[] temp = new String[data.length];
		for (int i = 1; i < data.length; i++) {
			temp[i] = data[i - 1];
		}
		temp[0] = add;
		return temp;
	}

PHPModifica

Trasposizione dell'algoritmo Java in PHP.

 <?php

function AlgoritmoDiBerger($arrSquadre)
 {
 
    $numero_squadre = count($arrSquadre);
    if ($numero_squadre % 2 == 1) {
    	    $arrSquadre[]="BYE";   // numero giocatori dispari? aggiungere un riposo (BYE)!
    	    $numero_squadre++;
    }
    $giornate = $numero_squadre - 1;
    /* crea gli array per le due liste in casa e fuori */
    for ($i = 0; $i < $numero_squadre /2; $i++) 
    {
        $casa[$i] = $arrSquadre[$i]; 
        $trasferta[$i] = $arrSquadre[$numero_squadre - 1 - $i];

    }
 
    for ($i = 0; $i < $giornate; $i++) 
    {
        /* stampa le partite di questa giornata */
        echo '<br />'.($i+1).'a Giornata<br />';
 
        /* alterna le partite in casa e fuori */
        if (($i % 2) == 0) 
        {
            for ($j = 0; $j < $numero_squadre /2 ; $j++)
            {
                 echo ' '.$trasferta[$j].' - '.$casa[$j].'<br />';
            }
        }
        else 
        {
            for ($j = 0; $j < $numero_squadre /2 ; $j++) 
            {
                 echo ' '.$casa[$j].' - '.$trasferta[$j].'<br />';
            }
                 
        }
 
        // Ruota in gli elementi delle liste, tenendo fisso il primo elemento
        // Salva l'elemento fisso
        $pivot = $casa[0];
 
        /* sposta in avanti gli elementi di "trasferta" inserendo 
           all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */
        array_unshift($trasferta, $casa[1]);
        $riporto = array_pop($trasferta);

        /* sposta a sinistra gli elementi di "casa" inserendo all'ultimo 
           posto l'elemento "riporto" */
        array_shift($casa);
        array_push($casa, $riporto);
 
        // ripristina l'elemento fisso
        $casa[0] = $pivot ;
    } 
} 
?>

JavaScriptModifica

Trasposizione dell'algoritmo Java in JavaScript.

 <script>

function AlgoritmoDiBerger(arrSquadre)
{
    // Aggiunta di una "squadra" di comodo se sono dispari 
    (arrSquadre.length % 2 ) && arrSquadre.push('Riposo');
 
    for (var i = 0; i < arrSquadre.length - 1; i++) {
        
        document.write("<h1>" + (i+1) + "a Giornata</h1>\n");
        
        for (var j = 0; j < arrSquadre.length/2 ; j++) {

            // alterna le partite in casa e fuori
            document.write(
            (i % 2) ?
                arrSquadre[arrSquadre.length -j -1] + ' - ' + arrSquadre[j] + "\n" :
                arrSquadre[j] + ' - ' + arrSquadre[arrSquadre.length -j -1] + "\n"
                );
        }
        
        // Ultima squadra viene inserita nella posizione 1
        arrSquadre.splice(1,0,arrSquadre.pop());
    } 
} 
</script>

NoteModifica

  1. ^ Paolo Alessandrini, La matematica nel pallone, 40K, 2015, p. 140.
  2. ^ Con "N=N−1".
  3. ^ Lega Serie A, il sorteggio dei calendari., su gazzetta.it, 25 luglio 2017.
  4. ^ Le livre de l'arbitre: edizione 2008 (PDF) (in French). Fédération Française des Échecs. p. 56. ISBN 978-2-915853-01-8.

Voci correlateModifica