Tävlingsprogrammering/Uppgifter/Turnering

Turnering

Om man vill ordna t.ex. en bordshockeyturnering där alla möter alla kan man använda sig av ett praktiskt rotationsschema som kallas round robin. Det går till så att spelarna i den första omgången möter varandra enligt figuren ovan (vi antar att antalet spelare n är jämnt). När första omgången är klar förflyttar sig alla spelare ett steg medurs, utom spelaren i det nedre vänstra hörnet som hoppas över (därav namnet, man förflyttar sig “runt” Robin, d.v.s. den sista spelaren). Med detta rotationsschema är man garanterad att alla har mött alla precis en gång efter n-1 omgångar.

Din uppgift är att skriva ett program som skriver ut vilka spelare som ska möta vilka en viss omgång. Indata till programmet är antalet spelare i turneringen (ett jämnt tal n mellan 2 och 100) och omgången (mellan 1 och n−1). Utdata är en lista över n/2 matcher där du anger vilka som möter vilka. Använd utdataformatet i exemplet nedan. Ordningen på matcherna spelar ingen roll.

Körningsexempel:

Antal spelare ? 8 
Omgång ? 3 
6-8 
7-5 
1-4 
2-3 

Lösning

Här handlar det helt enkelt om att rotera objekten, förutom sista förstås, som med fördel kan läggas till efteråt. Så här är en enkel lösning i C++, med functionen std::rotate:

#include <iostream>
#include <algorithm>
#include <vector>

int main(){
	using namespace std;
	int posses,turns;
	cout << "Antal spelare ? ";
	cin >> posses;
	cout << "Omgång ? ";
	cin >> turns;
	--turns; //Räkning sker från 0, inte 1
	vector<int> vec;
	for(int i=1;i<posses;++i)
		vec.push_back(i);
	if(turns) //Om det behövs...
		std::rotate(vec.begin(),vec.end()-turns,vec.end()); //...rotera
	int half=posses/2;
	vec.push_back(posses);
	for(int i=0;i<half;++i)
		cout << vec[i] << '-' << vec[posses-i-1] << endl;
}

Lösningsexempel i Java där vi gör roteringarna manuellt.

import java.util.*;

public class Turnering
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Antal spelare: ");
		int antal = scan.nextInt();

		System.out.print("Omgång: ");
		int rounds = scan.nextInt();

		//Där vi lagrar våra spelare.
		int [] spelare = new int [antal];

		//Skapar spelarna.
		for(int i = 0; i<antal; i++)
		{
			spelare[i] = (i+1);
		}

		//Roterar tills vi kommit fram till vår omgång.
		for(int i = 1; i<rounds; i++)
		{
			//Mellanlagrar spelaren på första platsen.
			int tmp = spelare[0];

			//Flyttar spelaren som är näst sist till plats 1.
			spelare[0] = spelare[antal-2];

			//Flyttar sedan alla spelare en plats framåt. (Med start på näst-näst sista spelaren.)
			//Det är viktigt att vi gör det bakifrån så att
			// vi inte lagrar över någon spelare.
			for(int j = antal-3; j>0; j--)
			{
				spelare[j+1] = spelare[j];
			}

			//Flyttar spelaren som var på första platsen till andra platsen.
			spelare[1] = tmp;
		}

		//Skriver ut svaret.
		for(int i = 0; i<antal/2; i++)
		{
			System.out.println(spelare[i] + "-" + spelare[antal-(i+1)]);
		}
	}
}