Art
18.04.2002, 11:12
ich habe den kram zwar schon in der algosection gepostet, aber die ist eher etwas "zäh" und da ich es nachher eh in php brauche, denke ich mir ich versuchs mal hier.
---cut---
für mein derzeitiges projekt brauche ich ein kleines codetechnisches schmankerl. es geht darum, einen spielplan z.b. einer fußballliga aus einer mysql-tabelle zu generieren. die mysql-abfragen sind dabei natürlich nicht das problem, sondern der algorithmus, mit dem der spielplan erstellt wird.
habe mir da schon den die haare zerrauft. eine befreundeter mittleiweile pensionierter mathelehrer hat mir dazu folgendes gepostet:
--------------------------------------------------------------------------------
In einer Menge mit n (n gerade) verschiedenen Elementen gibt es
(n-1)(n-3)(n-5)...1 Möglichkeiten, Paare zu bilden.
Bei Deinem Beispiel M = (1, 2, 3, 4, 5, 6) sind das 5 mal 3 mal 1 = 15
Möglichkeiten, ich will sie mit 1*, 2*, 3*,...,15* bezeichen:
1* 2* 3* 4* 5* 6* 7* 8* 9* 10* 11* 12* 13* 14* 15*
12 12 12 13 13 13 14 14 14 15 15 15 16 16 16
34 35 36 24 25 26 23 25 26 23 24 26 23 24 25
56 46 45 56 46 34 56 36 35 46 36 34 45 35 34
nun streiche man alle Möglichkeiten, in denen Paare sind, die schon
vorgekommen sind:
1* ok
2* streichen wegen 12 in 1*
3* streichen wegen 12 in 1*
4* streichen wegen 56 in 1*
5* ok
6* streichen wegen 13 in 5*
7* streichen wegen 56 in 1*
8* streichen wegen 25 in 5*
9* ok
10* streichen wegen 46 in 5*
11* ok
12* streichen wegen 26 in 9*
13* ok
14* streichen wegen 16 in 13*
15* streichen wegen 16 in 13*
Es bleiben also die fünf ( = 6 - 1) Paarbildungen ((Spieltage)): 1*, 5*,
9*, 11* und 13*.
--------------------------------------------------------------------------------
ferner habe ich noch was mit divide und conquer gefunden: http://www.niederma.de/Comp/spielplan.html
kriege das aber mit allem nich hin. auswärtsspiele und so ein schnickschnack können allerdings unberücksichtig bleiben.
hat jemand für das prob eine lösung parat oder habt ihr lust hier gemeinsam einen algorithmus zu entwickeln, den am ende jeder versteht?
---cut---
für mein derzeitiges projekt brauche ich ein kleines codetechnisches schmankerl. es geht darum, einen spielplan z.b. einer fußballliga aus einer mysql-tabelle zu generieren. die mysql-abfragen sind dabei natürlich nicht das problem, sondern der algorithmus, mit dem der spielplan erstellt wird.
habe mir da schon den die haare zerrauft. eine befreundeter mittleiweile pensionierter mathelehrer hat mir dazu folgendes gepostet:
--------------------------------------------------------------------------------
In einer Menge mit n (n gerade) verschiedenen Elementen gibt es
(n-1)(n-3)(n-5)...1 Möglichkeiten, Paare zu bilden.
Bei Deinem Beispiel M = (1, 2, 3, 4, 5, 6) sind das 5 mal 3 mal 1 = 15
Möglichkeiten, ich will sie mit 1*, 2*, 3*,...,15* bezeichen:
1* 2* 3* 4* 5* 6* 7* 8* 9* 10* 11* 12* 13* 14* 15*
12 12 12 13 13 13 14 14 14 15 15 15 16 16 16
34 35 36 24 25 26 23 25 26 23 24 26 23 24 25
56 46 45 56 46 34 56 36 35 46 36 34 45 35 34
nun streiche man alle Möglichkeiten, in denen Paare sind, die schon
vorgekommen sind:
1* ok
2* streichen wegen 12 in 1*
3* streichen wegen 12 in 1*
4* streichen wegen 56 in 1*
5* ok
6* streichen wegen 13 in 5*
7* streichen wegen 56 in 1*
8* streichen wegen 25 in 5*
9* ok
10* streichen wegen 46 in 5*
11* ok
12* streichen wegen 26 in 9*
13* ok
14* streichen wegen 16 in 13*
15* streichen wegen 16 in 13*
Es bleiben also die fünf ( = 6 - 1) Paarbildungen ((Spieltage)): 1*, 5*,
9*, 11* und 13*.
--------------------------------------------------------------------------------
ferner habe ich noch was mit divide und conquer gefunden: http://www.niederma.de/Comp/spielplan.html
kriege das aber mit allem nich hin. auswärtsspiele und so ein schnickschnack können allerdings unberücksichtig bleiben.
hat jemand für das prob eine lösung parat oder habt ihr lust hier gemeinsam einen algorithmus zu entwickeln, den am ende jeder versteht?