Spielgenerierung < Algorithmen < Schule < Informatik < Vorhilfe
|
| Aufgabe | geg.: ein Array ( Team[] teams ) variabler Länge
ein Array ( Spiel[] spiele ) Länge : ( teams.length -1 ) * 2
ges.: Generierung der Spiele |
ich brauche einen algorithmus, der folgende spiele generiert, und diese im Spielearray speichert:
und zwar spielt jeder gegen jeden ( zum Speichern: spiele[index] = new Spiel(teams[x], teams[y]) )
also zB: 1:2, 3:4, 5:6, 7:8, ...
und dann die rückrunde mit umgekehrten begegnungen.
bitte in Java lösen.
mfg stovi0040
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
ich denke nicht, dass dieses Forum dazu da ist, dir ein vorgefertigten Algorithmus zu geben.
Vielmehr hast du die Möglichkeit uns deine eigene Version zu zeigen und wir schauen, ob die in Ordnung ist und was man verbessern könnte.
Versuche es also erstmal selber, wenn du Probleme hast, dann poste sie hier.
Schöne Grüsse
|
|
|
| |
|
Das wäre auch zu schön....
Was mir eigentlich fehlt ist der Ansatz:
meine Gedanken waren:
ich schätze es als fast unmöglich (bzw. viel zu aufwändig) ein, diese Algorithmus mit for-Schleifen zu lösen.
Ich glaube es wäre simpler, einfach alle Möglichkeiten von Spielen abzufragen, und diese dann auf Duplikate zu überprüfen... Allerdings ist dann die Reihenfolge der Spiele sehr dem Zufallüberlassen.
Kann man es in einer mathematischen Reihe lösen (zB. 1:2, 1:3, 1:4, ..) ?
|
|
|
| |
|
Hallo und guten Tag
Dir, werter Fragesteller, und allen Freunden der Laufzeit von Programmen,
vermutlich wirst Du beim ''Generieren aller Moeglichkeiten'' das benutzen, was Du eigentlich vermeiden willst: for-Schleifen.
Also Du hast n Spieler, nennen wir sie [mm] s_1 [/mm] bis [mm] s_n, [/mm] und Du möchtest eine Liste aller Spiele generieren, so dass also
jeder gegen jeden einmal spielt, richtig ? (Wobei ein Spiel dann ein Paar [mm] (s_i,s_j) [/mm] ist oder so, gell ?)
Generiere erst alle Spiele mit [mm] s_1, [/mm] dann alle mit [mm] s_2, [/mm] die noch fehlen (d.h. mit Partnern [mm] s_j [/mm] mit j>2 usw, also:
pos :=1
(Position im Array Spiele, in dem das naechste generierte Spiel
gespeichert wird, wir fangen bei 1 an zu zaehlen, d.h. ggf abaendern !)
for i=1 to n-1
for j=i+1 to n
Generiere Spiel [mm] (s_i,s_j) [/mm]
Speichere Spiel [mm] (s_i,s_j) [/mm] in Spiele[pos]
pos := pos +1
Das war es fuer die Hinrunde.
Richtig und klar soweit ?
(Dachtest Du, Du muesstest eine nicht-konstante Zahl von for-Schleifen
ineinander verschachteln ?)
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:08 Mi 08.03.2006 | | Autor: | Frank05 |
> vermutlich wirst Du beim ''Generieren aller
> Moeglichkeiten'' das benutzen, was Du eigentlich vermeiden
> willst: for-Schleifen.
Oder nimmst stattdessen lieber die bewährten while-Schleifen  *scnr*
> Also Du hast n Spieler, nennen wir sie [mm]s_1[/mm] bis [mm]s_n,[/mm] und Du
> möchtest eine Liste aller Spiele generieren, so dass also
> jeder gegen jeden einmal spielt, richtig ? (Wobei ein Spiel
> dann ein Paar [mm](s_i,s_j)[/mm] ist oder so, gell ?)
>
> Generiere erst alle Spiele mit [mm]s_1,[/mm] dann alle mit [mm]s_2,[/mm] die
> noch fehlen (d.h. mit Partnern [mm]s_j[/mm] mit j>2 usw, also:
>
> pos :=1
> (Position im Array Spiele, in dem das naechste generierte
> Spiel
> gespeichert wird, wir fangen bei 1 an zu zaehlen, d.h. ggf
> abaendern !)
>
> for i=1 to n-1
> for j=i+1 to n
> Generiere Spiel [mm](s_i,s_j)[/mm]
> Speichere Spiel [mm](s_i,s_j)[/mm] in Spiele[pos]
> pos := pos +1
>
> Das war es fuer die Hinrunde.
Achso.. ich dachte das Problem wäre vielmehr die Spiele so anzuordnen wie in einem Turnier, so dass in jeder Runde alle Teams ein Spiel gegen ein gegnerisches Team haben, dabei aber kein Team gegen ein Team spielt, gegen das es schon in einer der vorigen Runden gespielt hat. Also für n Teams dann (n-1) Runden mit je n/2 Spielen, so dass nach den (n-1)*n/2 Spielen jeder gegen jeden genau einmal gespielt hat. Zugegeben diese Spiele passen nicht unbedingt in das Array das in der Aufgabenstellung gegeben war..
Anschlussfrage: Ist das so modifizierte Problem Greedy/effizient lösbar?
|
|
|
|
