Algoritmul lui Berger
Salt la navigare Salt la căutare
Algoritmul lui Berger este un algoritm folosit pentru a întocmi un calendar (împărțit în zile sau runde) al unei competiții sportive care are formula rundei italiene : își ia numele de la inventatorul său, austriacul Johann Berger . [1]
Calculul
Cu un număr de echipe participante, algoritmul calculează cuplaje „N 2” pentru fiecare zi. [2]
- Pentru fiecare zi „g” între 1 și „n - 1”;
- Pentru fiecare întâlnire „i” între 1 și „n: 2”;
- Meciul „i” combină două echipe conform acestor criterii:
- nu au fost încă potrivite
- celelalte echipe - neselectate - nu au fost deja împerecheate.
Implementări
Există funcții care implementează algoritmul prin setarea matricei cu numele echipelor, în număr par, ca parametru, procesând calendarul unui grup (tipărit pe video).
În cazul unui număr impar de echipe, fiecare dintre ele va fi combinată din când în când cu elementul „odihnă”. Constrângerile pentru echipele care împărtășesc același teren de sport pot fi rezolvate alternând între meciurile de acasă și cele din deplasare. [3]
O implementare legată de jocul de șah în care fiecare jucător alternează alb-negru pe rând se găsește în referință [4] .
Java
Algoritm elaborat prin Java .
public void AlgoritmoDiBerger ( String [] teams ) {
int team_number = echipe . lungime ;
zile int = număr_ de echipe - 1 ;
/ * creați tablouri pentru cele două liste de acasă și de departe * /
String [] house = new String [ number_squots / 2 ] ;
String [] trip = new String [ number_square / 2 ] ;
for ( int i = 0 ; i < number_squots / 2 ; i ++ ) {
acasă [ i ] = echipe [ i ] ;
în deplasare [ i ] = echipe [ număr_curse - 1 - i ] ;
}
pentru ( int i = 0 ; i < zile ; i ++ ) {
/ * tipărește meciurile de astăzi * /
Sistem . afară . printf ( "% d ^ Ziua \ n" , i + 1 );
/ * alternează meciurile acasă și în deplasare * /
if ( i % 2 == 0 ) {
for ( int j = 0 ; j < number_squots / 2 ; j ++ )
Sistem . afară . printf ( "% d% s -% s \ n" , j + 1 , departe [ j ] , acasă [ j ] );
}
altceva {
for ( int j = 0 ; j < number_squots / 2 ; j ++ )
Sistem . afară . printf ( "% d% s -% s \ n" , j + 1 , acasă [ j ] , departe [ j ] );
}
// Rotiți elementele listelor, păstrând primul element fix
// Salvați elementul fix
String pivot = casă [ 0 ] ;
/ * deplasați elementele „departe” înainte prin inserarea
la început elementul de casă [1] și salvați elementul de ieșire în „carry” * /
String carry = shiftRight ( departe , acasă [ 1 ] );
/ * mutați elementele „acasă” la stânga inserând în ultimul
plasează elementul „carry” * /
shiftLeft (acasă, reportare);
// restabiliți elementul fix
casa [ 0 ] = pivot ;
}
}
Varianta complet funcțională :
public void AlgoritmoDiBerger ( String [] teams ) {
int team_number = echipe . lungime ;
zile int = număr_ de echipe - 1 ;
/ * creați tablouri pentru cele două liste de acasă și de departe * /
String [] house = new String [ number_squots / 2 ] ;
String [] trip = new String [ number_square / 2 ] ;
for ( int i = 0 ; i < number_squots / 2 ; i ++ ) {
acasă [ i ] = echipe [ i ] ;
în deplasare [ i ] = echipe [ număr_curse - 1 - i ] ;
}
pentru ( int i = 0 ; i < zile ; i ++ ) {
/ * tipărește meciurile de astăzi * /
Sistem . afară . printf ( "% d ^ Ziua \ n" , i + 1 );
/ * alternează meciurile acasă și în deplasare * /
if ( i % 2 == 0 ) {
for ( int j = 0 ; j < number_squots / 2 ; j ++ )
Sistem . afară . printf ( "% d% s -% s \ n" , j + 1 , departe [ j ] , acasă [ j ] );
}
altceva {
for ( int j = 0 ; j < number_squots / 2 ; j ++ )
Sistem . afară . printf ( "% d% s -% s \ n" , j + 1 , acasă [ j ] , departe [ j ] );
}
// Rotiți elementele listelor, păstrând primul element fix
// Salvați elementul fix
String pivot = casă [ 0 ] ;
/ * deplasați elementele „departe” înainte prin inserarea
la început elementul de casă [1] și salvați elementul de ieșire în „carry” * /
String carry-over = călătorie [ călătorie . lungime - 1 ] ;
away = shiftRight ( deplasare , acasă [ 1 ] );
/ * mutați elementele „acasă” la stânga prin inserarea la ultima
plasează elementul „carry” * /
casa = shiftLeft ( casa , reportare );
// restabiliți elementul fix
casa [ 0 ] = pivot ;
}
}
private String [] shiftLeft ( String [] data , String add ) {
String [] temp = new String [ data . lungime ] ;
for ( int i = 0 ; i < data . length - 1 ; i ++ ) {
temp [ i ] = data [ i + 1 ] ;
}
temp [ data . lungime - 1 ] = adăuga ;
revenire temp ;
}
private String [] shiftRight ( String [] data , String add ) {
String [] temp = new String [ data . lungime ] ;
for ( int i = 1 ; i < data . length ; i ++ ) {
temp [ i ] = data [ i - 1 ] ;
}
temp [ 0 ] = add ;
revenire temp ;
}
C #
Transpunerea algoritmului Java în C # .
public void AlgoritmoDiBerger ( șir [] echipe ) {
int team_number = echipe . Count ();
zile int = număr_ de echipe - 1 ;
/ * creați tablouri pentru cele două liste de acasă și de departe * /
string [] house = new string [ number_squots / 2 ];
șir [] match away = șir nou [ number_squins / 2 ];
for ( int i = 0 ; i < number_squots / 2 ; i ++) {
acasă [ i ] = echipe [ i ];
în deplasare [ i ] = echipe [ număr_curse - 1 - i ];
}
pentru ( int i = 0 ; i < zile ; i ++) {
/ * tipărește meciurile de astăzi * /
Consolă . WriteLine ( $ "{i + 1} Day \ n" );
/ * alternează meciurile acasă și în deplasare * /
if ( i % 2 == 0 ) {
for ( int j = 0 ; j < number_squots / 2 ; j ++)
Consolă . WriteLine ( $ "{j + 1} {away [j]} - {home [j]} \ n" );
}
altceva {
for ( int j = 0 ; j < number_squots / 2 ; j ++)
Consolă . WriteLine ( $ "{j + 1} {home [j]} - {away [j]} \ n" );
}
// Rotiți elementele listelor, păstrând primul element fix
// Salvați elementul fix
String pivot = casă [ 0 ];
/ * deplasați elementele „departe” înainte prin inserarea
la început elementul de casă [1] și salvați elementul de ieșire în „carry” * /
string carry = away [ away . Număr () - 1 ];
away = shiftRight ( deplasare , acasă [ 1 ]);
/ * mutați elementele „acasă” la stânga prin inserarea la ultima
plasează elementul „carry” * /
casa = shiftLeft ( casa , reportare );
// restabiliți elementul fix
casa [ 0 ] = pivot ;
}
}
șir privat [] shiftLeft ( șir [] date , șir adăugați ) {
șir [] temp = șir nou [ date . Numără ()];
for ( int i = 0 ; i < data . Count () - 1 ; i ++) {
temp [ i ] = data [ i + 1 ];
}
temp [ data . Count () - 1 ] = add ;
revenire temp ;
}
private String [] shiftRight ( String [] data , String add ) {
String [] temp = new String [ data . Numără ()];
for ( int i = 1 ; i < data . Count (); i ++) {
temp [ i ] = data [ i - 1 ];
}
temp [ 0 ] = add ;
revenire temp ;
}
PHP
Transpunerea algoritmului Java în PHP .
<? php
funcție AlgoritmoDiBerger ( $ arrSquadre )
{
$ number_squares = count ( $ arrSquadre );
if ( $ team_number % 2 == 1 ) {
$ arrSquadre [] = "BYE" ; // număr impar de jucători? adaugă o odihnă (BYE)!
$ number_squots ++ ;
}
$ zile = $ number_squins - 1 ;
/ * creați tablouri pentru cele două liste de acasă și de departe * /
pentru ( $ i = 0 ; $ i < $ number_squots / 2 ; $ i ++ )
{
$ casa [ $ i ] = $ arrSquadre [ $ i ];
$ away [ $ i ] = $ arrSquadre [ $ number_squires - 1 - $ i ];
}
pentru ( $ i = 0 ; $ i < $ zile ; $ i ++ )
{
/ * tipărește meciurile de astăzi * /
ecou „<br />” . ( $ i + 1 ) . „o zi <br />” ;
/ * alternează meciurile acasă și în deplasare * /
if (( $ i % 2 ) == 0 )
{
pentru ( $ j = 0 ; $ j < $ number_squots / 2 ; $ j ++ )
{
ecou '' . $ travel [ $ j ] . „-” . $ casa [ $ j ] . „<br />” ;
}
}
altceva
{
pentru ( $ j = 0 ; $ j < $ number_squots / 2 ; $ j ++ )
{
ecou '' . $ casa [ $ j ] . „-” . $ travel [ $ j ] . „<br />” ;
}
}
// Rotiți elementele listelor, păstrând primul element fix
// Salvați elementul fix
$ pivot = $ casă [ 0 ];
/ * deplasați elementele „departe” înainte prin inserarea
la început elementul de casă [1] și salvați elementul de ieșire în „carry” * /
array_unshift ( $ departe , $ acasă [ 1 ]);
$ carry = array_pop ( $ transfer );
/ * mutați elementele „acasă” la stânga prin inserarea la ultima
plasează elementul „carry” * /
array_shift ( $ casă );
array_push ( $ casă , $ transport );
// restabiliți elementul fix
$ casa [ 0 ] = $ pivot ;
}
}
?>
JavaScript
Transpunerea algoritmului Java în JavaScript .
< script >
funcția AlgoritmoDiBerger ( arrSquadre )
{
// Adăugarea unei „echipe” de comoditate dacă sunt ciudate
( arrSquadre . length % 2 ) && arrSquadre . împingeți ( „Rest” );
for ( var i = 0 ; i < arrSquadre . length - 1 ; i ++ ) {
document . write ( "<h1>" + ( i + 1 ) + "o zi </h1> \ n" );
for ( var j = 0 ; j < arrSquadre . length / 2 ; j ++ ) {
// alternează jocuri acasă și în deplasare
document . scrie (
( i % 2 ) ?
arrSquadre [ arrSquadre . lungime - j - 1 ] + '-' + arrSquadre [ j ] + "\ n" :
arrSquadre [ j ] + '-' + arrSquadre [ arrSquadre . lungime - j - 1 ] + "\ n"
);
}
// Ultima echipă este plasată în poziția 1
ar Echipe . splice ( 1 , 0 , arrSquadre . pop ());
}
}
< / script>
Perl
Transpunerea algoritmului Java în Perl
sub AlgoritmoDiBerger {
my (@squadre) = @_;
my $ number_square = scalar @square ;
if ( $ team_number % 2 ) {
$ number_squots ++ ;
push @ teams , „Rest” ;
}
$ number_ meu de meciuri = $ number_ de echipe / 2 - 1 ;
mele echipe $ number_ofdays = $ NUMBER_OF - 2;
@home my = @square [ 0 .. $ number_of matches ];
my @transferta = @teams [ $ number_ of matches + 1 .. $ number_ of teams - 1 ];
ziua mea @ ;
pentru $ mea (0 .. $ number_ofdays) {
$ zi [ $ i ] = [ hartă { $ i % 2 ? [ $ home [ $ _ ], $ away [ $ _ ] ] : [ $ away [ $ _ ], $ home [ $ _ ] ] } ( 0 .. $ number_of matches ) ];
printf "% d ^ Ziua \ n" , $ i + 1 ;
pentru meciul meu $ ( @ { $ matchday [ $ i ]} ) {
my ( $ acasă , $ departe ) = @ { $ joc };
printf "*% 20s -% -20s \ n" ,
$ acasă ,
$ călătorie ,
;
}
$ pivotul meu = shift @home ;
unshift @transfer , shift @home ;
push @home , pop @transfer ;
unshift @home , $ pivot ;
}
reveniți @ zi ;
}
Notă
- ^ Paolo Alessandrini, Matematica în balon , 40K, 2015, p. 140.
- ^ Cu „N = N - 1”.
- ^ Lega Serie A, extragerea calendarelor. , pe gazzetta.it , 25 iulie 2017.
- ^ Le livre de l'abitre: ediția 2008 (PDF) (în franceză). Fédération Française des Échecs. p. 56. ISBN 978-2-915853-01-8 .
