Sie sind nicht angemeldet. Bitte melden Sie sich an oder registrieren Sie sich.
Seiten 1
Sie anmelden oder registrieren um eine Antwort zu verfassen
Moin<p>Hat jemand eine Idee für einen Algorithmus, wie man bei einer Liga mit unbestimmter Anzahl teilnehmender Manschaften jeden gegen jeden Spielen lässt. Dabei sollen an jedem Spieltag möglichst viele Manschaften spielen(also entweder alle, oder bei einer ungeraden Anzahl alle bis auf eine), aber keine doppelt spielen müssen.<p>Gero
Vielleicht ist dieses Problem mit Recursion zu loesen... denken wir nur mal an die Towers of Hanoi oder die Triangular Numbers.<p>Damit wuerde es vielleicht gehen... bin mir aber nicht ganz sicher.
Nur mal so ne Idee.
ka, ob das ne einfache lösung wäre, aber ihc hätte es so gemacht:<p>2 arrays, und alle mannschaften in die arrays gehauen. um nun jeden gegen jeden spielen zu lassen, bleibt das obere array (das 1) immer unverändert, nur bei dem unteren lässt man die mannschaften je ein array feld nach vorne rücken und dann<p>$array1[5] gegen $array2[5] spielen....<p>so hat man an jedem spieltag neue begegnungen.
axo: wenn ne mannschaft im array auf posi 0 ist, muss sie beim weiterrücken logischerweise ans arrayende [img]images/icons/smile.gif" border="0[/img] <p>so long F. [img]images/icons/grin.gif" border="0[/img]
hä?
wie wärs mit
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i != j)
play(i, j);
</pre><hr></blockquote><p>edit: glaub ich nich so perfekt (?)<p>[ 27.01.2002: Beitrag editiert von: whitehouse ]</p>
hmm:
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
k = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
found = false;
if (i != j) {
for (l = 0; l < k; l++)
if ((i == arr[l][0] && j == arr[l][1]) || (i == arr[l][1] && j == arr[l][0]))
found = true;
if (!found) {
play(i, j);
arr[k][0] = i; arr[k++][1] = j;
}
}
}
</pre><hr></blockquote><p>passd des?<p>[ 27.01.2002: Beitrag editiert von: whitehouse ]</p>
nene, mit 3 verschachtelten schleifen...
mit dem array brauchts nur 1 und ein paar arrayfkten [img]images/icons/smile.gif" border="0[/img]
@whitehouse: Da sind ja jetzt noch garkeine Spieltage mit drin, aber so ähnlich hab ich mir das auch mal gedacht:<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>$members = array(1,2,3,4,5,6,7,8,9,10);
$spiele = array();
function generate ($tag) {
$no = 0;
global $members;
global $spiele;<p> $spiele[$tag] = array();
for ($i=0; $i<count($members); $i++) {
for ($j=$i+1; $j<count($members); $j++) {
if (!spieler_vergeben($i, $tag) && !spieler_vergeben($j, $tag) && !match_vergeben($i, $j)) {
$spiele[$tag][$no] = array();
$spiele[$tag][$no][0] = $i;
$spiele[$tag][$no++][1] = $j;
}
}
}
if (count($spiele[$tag]) < floor(count($members)/2)) {
return "Tag ". ($tag+1) ." geht nicht<BR>";
}
}
echo generate (0);
echo generate (1);
echo generate (2);
echo generate (3);
echo generate (4);
echo generate (5);
echo generate (6);
echo generate (7);
</pre><hr></blockquote>Das funzt aber dann nur bei bestimmten Anzahlen von Spielern, bei den meißten aber nicht. Die Spiele werden dabei nicht optimal berechnet und am Ende sind nurnoch Tage wo nicht alle Mannschaften spielen.<p>@zoro: Bei deine Methode kommt, wenn man checkt, dass keine doppelt Spielt genau das selbe raus, wie bei mir: Am Ende nicht optimal.
Z.B. bei 5 Mannschaften muss ja immer einer aussetzen. Optimal wäre es also, wenn am Spieltag 1 die 5. Mannschaft aussetzte, am 2. die 4., am 3. die 3 usw. Wenn man aber deine und meine Methode nimmt, setzt am 1. und am 2. Spieltag Mannschaft 5 aus, kann also nicht optimal werden.<p>Im Notfall müsste man halt durch Rekursion durchprobieren, aber so ne genaue Vorstellung davon hab ich auch noch nicht, aber da musses doch was besseres geben, oder?<p>[ 27.01.2002: Beitrag editiert von: Gero ]</p>
Moin<p>Zunächst einmal sollte man den Zusammenhang zwischen der Anzahl der teilnehmenden Mannschaften, den daraus resultierenden möglichen Begegnungen und der zur Ausführung dieser notwendigen Spieltage für die genannten Bedingungen (=möglichtst alle sollen spielen, bei ungrader Teilnehmerzahl setzt einer aus) eruieren.<p>Also:
A=Anzahl der Mannschaften,B=mögliche Begegnungen, S=Spieltage<p>B=(A*(A-1))/2<p>S=B/(A/2) für A%2=0<p>S=B/((A-1)/2) für A%2=1<p>Ich mach das mal als Beispiel für den Fall für 5 oder 6 Mannschaften, weil die Fälle A%2=1 und A%2=0 identisch sind, das heißt, wenn A grade, ergibt sich das gleiche Ergebnis wie für A-1, die spielfreien Tage für den ungraden Fall ergeben sich dann durch Rausstreichen von A. <p>A=6, B=15, S=5<p>Als Array:<p>A=[1,2,3,4,5,6]<p>B=[12,13,14,15,16,23,24,25,26,34,35,36,45,46,56]<p>Sortierung: das Kleinstmögliche zum Kleinstmöglichen unter Ausschluß des bereits Gefundenen.<p>S1=[16,25,34]
S2=[15,24,36]
S3=[14,23,56]
S4=[13,26,45]
S5=[12,35,46]<p>Sortierung: das Kleinstmögliche zum Größtmöglichen unter Ausschluß des bereits Gefundenen.<p>Für den Fall<p>A=5,B=10,S=5<p>ergibt sich nach Rausstreichen von 6 <p>S1=[25,34] 1 hat spielfrei
S2=[15,24] 3 hat spielfrei
S3=[14,23] 5 hat spielfrei
S4=[13,45] 2 hat spielfrei
S5=[12,35] 4 hat spielfrei<p>
Jetzt muß ich mal guggen, wie die Sortierung am schnellsten geht, aber weil man ja wahrscheinlich nicht so viele Mannschaften hat wie Atome im Universum, ist die Schnelligkeit in diesem speziellen Fall vielleicht gar nicht so wichtig.
Alldieweil ich heut' Haushaltstag habe, kann ich mich wahrscheinlich erst heut abend melden.<p>
gruß<p>matho
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr>Sortierung: das Kleinstmögliche zum Größtmöglichen unter Ausschluß des bereits Gefundenen.<hr></blockquote>Gut, aber wie kommst du dann darauf?
S1=[16,25,34]
S2=[15,24,36]
S3=[14,23,56]
S4=[13,26,45]
S5=[12,35,46]<p>Kleinsmögliches mit Größtmöglichen heißt bei mir:
S1=[16,25,34]
S2=[15,26,34] und dann is vorbei [img]images/icons/frown.gif" border="0[/img]<p>[ 28.01.2002: Beitrag editiert von: Gero ]</p>
@ gero<p>tschulligung, hat a weng gedauert, war unterwechs.<p>-Gut, aber wie kommst du dann darauf?-<p>Tja, wie kommt man auf was zwischen Windelwechseln und Pfannkuchenbacken?
Da dacht ich noch, ich könnt's ohne
Stringvergleich machen.
Aber wie ich's auch dreh und wende: ohne so nen Vergleich komm ich nicht hin, dabei wäre das recht eigentlich ein Algorithmus, zumindest, wie mir das so vorschwebt.<p>Solang ich dazu keine Lösung habe, kann ich Dir folgendes anbieten - die Dampfhammermethode,
sozusagen:<p>
<html>
<head>
<title>liga</title>
<script>
A=[1,2,3,4,5,6,7,8];
al=A.length;
s='';
x=0;
z=0;
zz=0;
g=10*Math.pow(2,al);
X=[];<p>function Z()
{while(s.length<(al+1)*(al-1))
{for(i=0;i<al-1;i++)if(i%2==0)if(A[i]>A[i+1])x++;
for(i=0;i<al/2;i++){X[i]=A[i*2]+''+A[i*2+1];if(M(i))x++;}
if(x==0)s+=A.join('')+'n';
A.sort(SO);
x=0;
z++;
if(z>g){z=0;s='';zz++;g+=al*20};
};
alert(s+z+' '+zz+' '+Math.round(g));
};<p>function M(m){return eval("s.match(/"+X[m]+"/)");};
function SO(){return Math.random()-Math.random()};
</script>
</head>
<body onload='Z()' onclick='location.reload()'>
<div></div>
</body>
</html><p>Schön ist anders, wie Kurt Ostbahn so überaus treffend in solchen Fällen zu bemerken pflegt, dafür funktioniert's wenigstens.<p>Für al=4 braucht's ein Augenzwinkern, für al=6 durchschnittlich so zwischen 5 sec und 1 Min, für al=8 zwischen ner halben und so ca. dero 3 - hängt halt von Freund Zufall ab.
Danach wird's eher düster, also das Gelbe vom Ei isses nich. Aber vielleicht kannst Du ja mit dem zugrundeliegenden Gedankengang was anfangen und es hilft Dir ein bißchen weiter.<p>Wie gesagt, hier nur gradzahlige Arrays, die spielfreien Tage bei ungrader Anzahl ergeben sich durch Rausstreichen des Spiels mit dem höchsten gradzahligen Eintrag.<p>
gruß<p>matho
@ gero
wenn man dann aber die Lösung hat, kommt man sich richtig blöd vor.<p>Sortierung wie folgt;<p>Ausgangsarray :[1,2,3,4,5,6,7,8,9,0]<p>1.Tag:10-29-38-47-56<p>2.Array: [1,3,4,5,6,7,8,9,0,2]<p>2.Tag:12-30-49-58-67<p>3.Array [1,4,5,6,7,8,9,0,2,3]<p>3.Tag:13-42-50-69-78<p>4.Array[1,5,6,7,8,9,0,2,3,4]<p>4.Tag:14-53-62-70-89<p>5.Array:[1,6,7,8,9,0,2,3,4,5]<p>5.Tag:15-64-73-82-90<p>6.Array:[1,7,8,9,0,2,3,4,5,6]<p>6.Tag:16-75-84-93-02<p>7.Array:[1,8,9,0,2,3,4,5,6,7]<p>7.Tag:17-86-95-04-23<p>8.Array:[1,9,0,2,3,4,5,6,7,8]<p>8.Tag:18-97-06-25-34<p>9.Array[1,0,2,3,4,5,6,7,8,9]<p>9.Tag:19-08-27-36-45<p>
10-29-38-47-56
12-30-49-58-67
13-42-50-69-78
14-53-62-70-89
15-64-73-82-90
16-75-84-93-02
17-86-95-04-23
18-97-06-25-34
19-08-27-36-45<p>Dir das Programm dafür zu schreiben, ist mir jetzt einfach zu peinlich,
Das schreibt man ja schneller mit der Hand........<p>
gruß <p>matho
Peinlich hin - peinlich her<p>bevor ich mich ins Bettchen verfüge, als Documentation für die Nachwelt:<p><html>
<head>
<title>liga</title>
<script><p>x=l=17;<p>A=[];
s='';<p>function Z()
{if(l%2==1)l+=1;
for(i=0;i<l;i++)A[i]=i+1;
al=A.length;
st=al-1;
while(st>0)
{for(i=0;i<al/2;i++)s+='-'+A[i]+':'+A[(al-1)-i]+'-';
A.splice(al,1,A[1]);
A.splice(0,2,A[0]);
s+='nn';
st--;
};
if(x%2==1)s=eval("s.replace(/"+l+"/g,'spielfrei')");
alert(s);
s='';
};
</script>
</head>
<body onclick='Z()'>
</body>
</html><p>
chuts nächtle<p>matho<p>[ 03.02.2002: Beitrag editiert von: matho ]</p>
Is irgendwie besser als die 3min-Lösung [img]images/icons/grin.gif" border="0[/img] <p>1000 Dank für den genialen Algorithmus.
@ gero<p>Ich danke aufrichtig für die Blumen.
Wenn Du mal wieder sowas hast, gib Laut.
Das hat nämlich neben dem ganzen browser-gehuber
mal Spass gemacht.<p>gruß<p>matho
Seiten 1
Sie anmelden oder registrieren um eine Antwort zu verfassen
Powered by PunBB, unterstützt von Informer Technologies, Inc.
Currently installed 7 official extensions. Copyright © 2003–2009 PunBB.