Elegante Lösung für ein algorithmisches Problem (mit Modulo?)

Hallo,

ich habe ein kniffliges algorithmisches Problem:

Ich will rundenweise Pärchen bilden. Die Teilnehmer sind durchnummeriert von 1 bis n. Der Einfachheit halber nehmen wir
n=18 an. Damit jedes Pärchen 1x gebildet werden kann, sind also
n-1=17 Runden notwendig. Pro Runde werden n/2=9 Pärchen gebildet. Der Algorithmus ist anschaulich ziemlich einfach:

Teilnehmer 1 hat eine Sonderrolle, die bilden einen Kreis von
[2,3,4,..,17,18,2,...]. Die erste Runde sieht dann so aus:

Für die nächste Runde rotiert der Ring gegen den Uhrzeigersinn:

Und so weiter. Jetzt müsste ich das ganze für einen Algorithmus formalisieren. So würde es gehen:

for (runde = 1 to 17) {
   k = 18-runde;
   Pärchen1 := 1 und k;
   for (i = 1 to 8) {
      Person1 := k+i;
      if (Person1 > 18) {
         Person1 := Person1 - 17
      }
      Person2 := k-i;
      if (Person2 < 2) {
         Person2 := Person2 + 17;
      }
      Pärchen (1+i):= Person1 und Person2;
   }
}

Das ist allerdings ziemlich unschön und umständlich. Es muss einfach einen eleganten Weg geben (ohne die Fallunterscheidungen). Wenn man die Personen so von 0 bis 17 durchnummeriert, gibt es einen eleganten Weg:

Dann könnte man immer bequem mit Modulo-Operatoren arbeiten:

(k+i) mod 17 und (k-i) mod 17
...

Aber leider darf ich die Nummerierung nicht ändern. Fällt jemandem vielleicht eine elegantere Lösung ein? Ich hab das Gefühl, dass man vielleicht doch irgendwie elegant mit Modulo arbeiten kann, komm aber nicht auf die Lösung.

Krösus

Das ist das Rutsch-System bei Schachturnieren (z. B. Blitzschach)

In Deinem Beispiel sollten aber in der ersten Runde die Paarungen wie folgt lauten:
1 - 18
2 - 17
3 - 16
4 - 15
5 - 14
6 - 13
7 - 12
8 - 11
9 - 10

volkard

gib mir den code, der päärchen mit der numerierung 0-17 erzeugt und ich gebe die den code, der päärchen mit der numerierung 1-18 erzeugt.

Krösus

rutschsystem.h:

#ifndef RUTSCHSYSTEM_H
#define RUTSCHSYSTEM_H

typedef struct
{
	int weiss;
	int schwarz;
	int erg;
} TISCH;

#define FREILOS_NR 9999

typedef int (* SpieleFunc)(int, int, TISCH*, int);

void RutschSystem(int, SpieleFunc);

#endif /*RUTSCHSYSTEM_H*/

rutschsystem.c:

#include <stdlib.h>
#include "rutschsystem.h"

static void RutschenG(int, TISCH*); //Gerade Anz. Spieler
static void RutschenU(int, TISCH*); //Ungerade Anz. Spieler

void RutschSystem(int iAnzSpieler, SpieleFunc Spielen)
{
	int bMitFreilos = (iAnzSpieler & 1);
	int iAnzTische = (iAnzSpieler >> 1) + bMitFreilos;
	TISCH* aTische = (TISCH*) malloc(iAnzTische * sizeof(TISCH));
	//Tische fuer die erste Runde besetzen
	int iTischNr, iRunde;
	for(iTischNr = 0; iTischNr < iAnzTische - bMitFreilos; ++iTischNr)
	{
		aTische[iTischNr].weiss   = 1 + iTischNr;
		aTische[iTischNr].schwarz = iAnzSpieler - iTischNr - bMitFreilos;
	}
	if(bMitFreilos)
	{
		aTische[iAnzTische - 1].weiss = iAnzSpieler;
		aTische[iAnzTische - 1].schwarz = FREILOS_NR;
	}
	for(iRunde = 1; iRunde < iAnzSpieler + bMitFreilos; ++iRunde)
	{
		if(!Spielen(iRunde, iAnzTische, aTische, bMitFreilos))
			break;
		if(bMitFreilos)
			RutschenU(iAnzTische, aTische);
		else
			RutschenG(iAnzTische, aTische);
	}
	free(aTische);
}

void RutschenG(int iAnzTische, TISCH* tische)
{
	int iTischNr, iSpielerNr = tische[0].schwarz;
	for(iTischNr = 1; iTischNr < iAnzTische; ++iTischNr)
	{
		int iSpielerNrNeu = tische[iTischNr].weiss;
		tische[iTischNr].weiss = iSpielerNr;
		iSpielerNr = iSpielerNrNeu;
	}
	for(iTischNr = iAnzTische - 1; iTischNr > 0; --iTischNr)
	{
		int iSpielerNrNeu = tische[iTischNr].schwarz;
		tische[iTischNr].schwarz = iSpielerNr;
		iSpielerNr = iSpielerNrNeu;
	}
	tische[0].schwarz = iSpielerNr;
}

void RutschenU(int iAnzTische, TISCH* tische)
{
	int iTischNr, iSpielerNr = tische[iAnzTische - 1].weiss;
	for(iTischNr = 0; iTischNr < iAnzTische - 1; ++iTischNr)
	{
		int iSpielerNrNeu = tische[iTischNr].weiss;
		tische[iTischNr].weiss = iSpielerNr;
		iSpielerNr = iSpielerNrNeu;
	}
	for(iTischNr = iAnzTische - 2; iTischNr >= 0; --iTischNr)
	{
		int iSpielerNrNeu = tische[iTischNr].schwarz;
		tische[iTischNr].schwarz = iSpielerNr;
		iSpielerNr = iSpielerNrNeu;
	}
	tische[iAnzTische - 1].weiss = iSpielerNr;
	tische[iAnzTische - 1].schwarz = FREILOS_NR;
}

Hauptmodul:

#include <stdio.h>
#include <stdlib.h>
#include "rutschsystem.h"

static int Spielen(int, int, TISCH*, int);

int main(void)
{
	char szAnzSpieler[999];
	printf("Wieviele Spieler nehmen am Turnier teil? ");
	gets(szAnzSpieler);
	RutschSystem(atoi(szAnzSpieler), &Spielen);
}

static char* Paarung(TISCH* tisch)
{
	static char szPaarung[999];
	if(tisch->schwarz != FREILOS_NR)
		sprintf(szPaarung, "%d - %d", tisch->weiss, tisch->schwarz);
	else
		sprintf(szPaarung, "%d - Freilos", tisch->weiss);
	return szPaarung;
}

static void BretterTauschen(int iAnzTische, TISCH* tische, int bMitFreilos, int iRunde)
{
	int iTischNr;
	for(iTischNr = 1; iTischNr < iAnzTische - bMitFreilos; iTischNr += 2)
	{
		int tausch = tische[iTischNr].weiss;
		tische[iTischNr].weiss = tische[iTischNr].schwarz;
		tische[iTischNr].schwarz = tausch;
	}
	if(!bMitFreilos && !(iRunde & 1))
	{
		int tausch = tische[0].weiss;
		tische[0].weiss = tische[0].schwarz;
		tische[0].schwarz = tausch;
	}
}

int Spielen(int iRunde, int iAnzTische, TISCH* tische, int bMitFreilos)
{
	int iTischNr;
	char antw[999];
	printf("%d. Runde\n", iRunde);
	BretterTauschen(iAnzTische, tische, bMitFreilos, iRunde);
	for(iTischNr = 0; iTischNr < iAnzTische; ++iTischNr)
		printf("Tisch %d: %s\n", iTischNr + 1, Paarung(tische + iTischNr));
	BretterTauschen(iAnzTische, tische, bMitFreilos, iRunde);
	if(iRunde < (2 * iAnzTische - 1))
	{
		printf("\nWeiter? [j/n] ");
		gets(antw);
	}
	else
		return 0;
	if((*antw == 'j') || (*antw == 'J') || !*antw)
	{
		printf("\n");
		return 1;
	}
	return 0;
}

Krösus

volkard schrieb:

gib mir den code, der päärchen mit der numerierung 0-17 erzeugt und ich gebe die den code, der päärchen mit der numerierung 1-18 erzeugt.

Es heißt Pärchen und Nummerierung.