Need Help: c/cpp prog

Seite 1 von 2 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/need_help_c_cpp_prog_102440/page_1 - zur Vollversion wechseln!

T3XT4 schrieb am 28.12.2003 um 14:08

Hi Leute.

Bin ziemlicher coding newb und bräuchte etwas Hilfe bei einem Programm.

Es geht um sowas änliches wie ein Tischtennisturnier.

Der Benutzer gibt zu erst die Anzahl der Teams ein.
Dann tritt jedes Team gegen jedes an.
Jedes Team darf aber nicht gleich wieder spielen.

und das Programm soll ausgeben welches Team jetzt gegen welches spielt.

(zB: Team 1:2 *tastedrück* Team 3:4 *taste* Team 5:6 ... usw...)

Das Problem ist, ich weiß ned wie ich die schleifen formulieren soll, damit sich das auch ausgeht.

tia!

Cya

T3XT4 schrieb am 28.12.2003 um 15:31

wenns ned verständlich is, bitte posten!

Ringding schrieb am 28.12.2003 um 15:39

Das kann man auf viele Arten machen. Du musst dir halt irgendwie merken, welche Teams zuletzt gespielt haben und welche Paarungen überhaupt schon gespielt haben und dann Kombinationen von Teams suchen, die noch nicht gespielt haben und die auch dürfen.

T3XT4 schrieb am 28.12.2003 um 15:44

mh.. ok... ich werds mal versuchen.

aber wenn ichs ned schaff, könnte dann wer einen beispielcode reinschreiben?

Ringding schrieb am 28.12.2003 um 15:57

Das Problem ist gar nicht so einfach, wie ich zuerst gedacht habe. Es darf z.B nicht passieren, dass am Ende noch die Paarungen 1-2, 1-3 übrigbleiben, sonst muss Team 1 ja direkt hintereinander spielen.

geforceraid schrieb am 28.12.2003 um 19:18

soo... habs jetzt hinbekommen.

Wieder mal exxxxtrreeeeeem schlampig und grotesk gecodet aber was solls.
Als Borgschüler kann ichs halt nicht besser

Ausserdem hab ichs in c#.NET programmiert

naja
hth trotzdem

Ringding schrieb am 28.12.2003 um 19:37

Ja das ist die einfache Version, und natürlich sehr ineffizient. Aber dafür mach ich dir keinen Vorwurf
Mein oben genanntes Problem behandelt sie halt überhaupt nicht (das ist auch nicht so leicht)

Da haben wir's auch schon (Team 4 spielt zweimal hintereinander)

Anzahl der Teams: 6
------------------------
5 6
3 1
4 2
6 3
2 5
1 4
2 6
4 5
6 1
3 5
1 2
1 5
2 3
3 4
4 6

moeglich: 15 gespielt: 15

Hmm, da spielt schon vorher Team 1 zweimal. Da hat's wohl noch irgendwas.

T3XT4 schrieb am 28.12.2003 um 19:47

waa und ich bring überhaupt nix gscheites zam...

wie kann sowas einfaches so schwer werden

mh.. @geforce
das prog rennt aber leider ned ohne .net.
und das sollte es, wenn möglich.

@ringding
du scheinst dich ja ziemlich auszukennen.
Wennst mal Zeit findest, willst es mal versuchen?

Cya

geforceraid schrieb am 28.12.2003 um 19:54

so... hab den fehler schon ausgebessert.

hier der neue und (hoffentlich) funktionierende sourcecode

mfg

edit: scheint immer noch net so richtig zu funzen...
es ist nur der fehler ausgebessert, dass er jetzt bis 2 (statt bisher 4) begegnungen vor schluss die richtlinien beachtet. ->

....
1 2
->>> 1 5
2 3
3 4
4 6

Bei den letzten 2 Begegnugnen kann es leider noch immer vorkommen, dass 1 team 2x hintereinander spielen muss.

Ringding schrieb am 28.12.2003 um 21:18

So, in Ermangelung einer genialen Idee hab ich hier einen simplen Backtracking-Algorithmus implementiert.

Code:

#include <stdio.h>

#define NMAX 100

static int teams, games2;
static unsigned char played[NMAX][NMAX];

int play(int t1, int t2, int games)
{
	int ct1=t1, ct2=t2;

	if (games == games2-1)
		return games2;
	played[t1][t2] = 1;
	played[t2][t1] = 1;
	do {
		if (++ct2 == teams) {
			ct2 = 0;
			if (++ct1 == teams)
				ct1 = 0;
		}
		if (ct1 != t1 && ct1 != t2 &&
			ct2 != t1 && ct2 != t2 &&
			ct1 != ct2 && !played[ct1][ct2])
		{
			if (play(ct1, ct2, games+1) == games2)
			{
				int a, b;
				a = (ct1<ct2) ? ct1 : ct2;
				b = (ct1<ct2) ? ct2 : ct1;
				printf("%d %d\n", a+1, b+1);
				return games2;
			}
		}
	} while (ct1 != t1 || ct2 != t2);
	played[t1][t2] = 0;
	played[t2][t1] = 0;
	return 0;
}

int main()
{
	int i, j;

	scanf("%d", &teams);
	if (teams < 2) {
		printf("Zu wenige.\n");
		return 1;
	}
	if (teams > NMAX) {
		printf("Zu viele.\n");
		return 1;
	}
	games2 = (teams-1)*teams/2;
	for (i=0; i<teams; i++)
		for (j=0; j<teams; j++)
			played[i][j] = 0;
	if (!play(0, 1, 0))
		printf("Nicht moeglich.\n");
	else {
		printf("1 2\n");
		printf("\n%d Spiele.\n", games2);
	}

	return 0;
}

Ringding schrieb am 29.12.2003 um 22:24

So, jetzt habe ich eine brauchbare Lösung gefunden. Es ist im Prinzip sehr ähnlich wie vorher, nur wird die Menge der noch ausständigen Spiele nun in einer verketteten Liste gespeichert, was das ganze erheblich schneller macht. Unter Linux komm ich jetzt bis 500 Teams, mit größerem Stack würde auch noch mehr gehen.

Code:

#include <stdio.h>

#define NMAX 1000
#define LMAX (NMAX*(NMAX-1)/2)

static int teams;
static int a[LMAX], b[LMAX], next[LMAX+1];

int play(int before1, int before2)
{
	int p = next[LMAX];
	int l = LMAX;

	if (p == -1)
		return -1;
	do {
		int ll = next[l];
		next[l] = next[p];
		if (a[p] != before1 && a[p] != before2 &&
			b[p] != before1 && b[p] != before2 &&
			play(a[p], b[p]))
		{
			int aa, bb, ct1 = a[p], ct2 = b[p];
			aa = (ct1<ct2) ? ct1 : ct2;
			bb = (ct1<ct2) ? ct2 : ct1;
			printf("%d %d\n", aa+1, bb+1);
			return -1;
		}
		next[l] = ll;
		l = p;
		p = next[p];
	} while (p != -1);
	return 0;
}

int main()
{
	int i, j, k, l;

	scanf("%d", &teams);
	if (teams < 2) {
		printf("Zu wenige.\n");
		return 1;
	}
	if (teams > NMAX) {
		printf("Zu viele.\n");
		return 1;
	}
	for (k=0, l=LMAX, i=0; i<teams; i++)
		for (j=i+1; j<teams; j++) {
			a[k] = i;
			b[k] = j;
			next[l] = k;
			l = k++;
		}
	next[l] = -1;
	next[LMAX] = 0;
	if (play(-1, -1))
		printf("\n%d Spiele.\n", (teams-1)*teams/2);
	else
		printf("Nicht moeglich.\n");

	return 0;
}

xdfk schrieb am 30.12.2003 um 09:28

Zitat von Ringding
So, jetzt habe ich eine brauchbare Lösung gefunden. Es ist im Prinzip sehr ähnlich wie vorher, nur wird die Menge der noch ausständigen Spiele nun in einer verketteten Liste gespeichert, was das ganze erheblich schneller macht. Unter Linux komm ich jetzt bis 500 Teams, mit größerem Stack würde auch noch mehr gehen.

im vergleich zu einem array ist deine verkettete liste aber ein unglaublicher speicherfresser. noch ein weiteres nettes feature waer eine moeglichst gleichmaeszige verteilung.

Ringding schrieb am 30.12.2003 um 11:12

Alles hat seinen Preis. Ich hab inzwischen eh schon wieder eine andere Idee, da werd ich mich wohl heute oder morgen nochmal an die Arbeit machen

atrox schrieb am 30.12.2003 um 14:45

muß das ergebnis deterministisch sein ? sonst liese sich wohl ein sehr einfacher randomisierter algorithmus programmieren, der sein zwischenergebnis einfach durchmischt, wenn er nicht mehr weiter kann.

T3XT4 schrieb am 30.12.2003 um 19:22

omg... wie wird man bitte so ein Guru, dass man das was ihr redet versteht?

habt ihr euch das durch Fachliteratur erarbeiter? Oder lernt man das in einer FH/wwi?

@ringding
Danke für das Programm! Funktioniert einwandfrei