05. december 2002 - 16:09Der er
13 kommentarer og 1 løsning
Hjælp til algoritme
Jeg skal bruge en algoritme der kan tage nedenstående hold og gøre så de ikke spiller på hjemmebane eller udebane to gange i streg, samt alle hold skal sidde over en gang, og samme hold må heller ikke spille mod hinanden to gange i streg. Algoritmen skal desuden gerne kunne klare et variabelt antal hold.
Hold 1 - Hold 1 Hold 1 - Hold 2 Hold 1 - Hold 3 Hold 1 – Hold 4 Hold 1 - Hold 5
Hold 2 - Hold 1 Hold 2 - Hold 2 Hold 2 - Hold 3 Hold 2 - Hold 4 Hold 2 - Hold 5
Hold 3 - Hold 1 Hold 3 - Hold 2 Hold 3 - Hold 3 Hold 3 - Hold 4 Hold 3 - Hold 5
Hold 4 - Hold 1 Hold 4 - Hold 2 Hold 4 - Hold 3 Hold 4 - Hold 4 Hold 4 - Hold 5
Hold 5 - Hold 1 Hold 5 - Hold 2 Hold 5 - Hold 3 Hold 5 - Hold 4 Hold 5 - Hold 5
Er kommet frem til at hvis runde = hold nr, eller runde er lige hold nr + antal, så skal holdet side over...
to gange i streg = to gange lige efter hinanden Ja et hold skal være på hjemmebane, men et hold må ikke spille på hjemmebane to runder efter hinanden. Alle hold skal møde hinanden på hjemmebane og udebane.
2 hold = 2kampe 3 hold = 6 kampe 4 hold = 12 kampe 5 hold = 20 kampe'
antal kampe er lig med: (antal hold*antal hold) - antal hold
Hum. dine regler kan ihvertfald ikke 100% overholdes:
Regel 1: der må ikke spilles imod samme modstander 2 kanpdage i træk
med 2 hold kan regel 1 ikke overholdes. de har ikke andre end hinanden at spille med :-( (eller kan vi indføje en extra kampdage hvor begge hold 'sidder over' og på den måde sige at regel 1 wr overholdt ?)
Regel 2: alle hold skal spille skiftevis på udebane og hjemmebane
med 3 hold skal der spilles følgende kampe:
bane 1 2 3 1-2 tom tom tom 2-3 tom tom tom 3-1 1-3 tom tom tom tom 3-2 tom 2-1 tom der findes ingen permutation af de seks linier hvor både regel 1 og regel 2 er overholdt. ( prøv selv, der er kun 6! (720) mulige rækkefølger at arrangere de 6 linier :-))
Så du kommer til enten at opgive eller også give køb på nogen krav :-(
nu er jeg i gruppe med s-christensen. kravet om 2 hjemmebaner/udebaner i træk skal overholdes...det med at 1,2 og så 2,1 kommer lige i træk gør ikke så meget
Gah, nej den går ikke. selv med lempelse af reglel 1:
4 hold: bane 1 2 3 4 1-3 2-4 tom tom tom tom 3-1 4-2 1-4 2-3 tom tom tom tom 3-2 4-1 ... nu skal hold 1 og hold 2 spille imod hinanden, og det kan de ikke komme til uden at regel 2 bliver brudt. ditto for hold 3 og 4 1-2 tom 3-4 tom tom 2-1 tom 4-3
Såvidt jeg kan se vil det samme ske hver gang der er et lige antal hold.
Jeg stopper her,
Det er ikke eentydigt bevist at opgaven er umulig, så lad spørgsmålet stå lidt, måske det kan lade sig gøre selvom jeg ikke kan hitte ud af det.
Jeg har en løsning til jeres problem, den virker med alle antal ulige hold. Der vil dog altid være en gang at hvert hold spiller på hjemme/ude bane to gange i træk!! Det kan ikke undgås... Kan I ikke lige sende en mail på mikkel@hojtider.dk ? Så skal i få en grundig forklaring og et stykke java kode I kan bruge, i løbet af i dag!
Sådan her, dette er alle de kampe der skal spilles i første runde(1. halvdel af sæsonen) Så er det jo bare at spejlvende det hele når der skal spilles returkamp, det kan faktisk gost lase sig gøre at de ikke spiller hjemme to gange i træk, men så ska de til gengæld en gang spille mod samme hold lige efter hinanden og dette synes jeg ikke er optimalt. Hvis i kigger, så er det fra toppen af og mod højre alle de kampe der skal spilles i første runde osv... første kamp i første runde er 1-3. næste kamp er så det første hold -1 (1-1 = 15) så det næste hold er 15 da det er 15 hold I arbejder med, andet hold hold i anden kamp er så udeholdet fra første kamp +1 (3+1 = 4) så det altså er 15-4 i anden kamp i første runde, sådan fortsætter det så indtil holdene begynder at overlappe altså her 10-9. rækkerne nedaf udfyldes i stigende orden 1 2 3 4 5 6 ..... 14 15 1 2 3 osv...
Er I med? Ellers så spørg, men kan I følge meningen lidt, der er selvfølgelig flere måder at programmere det på, men jeg synes det er op til jer at bestemme hvordan i helt præcist vil gøre det. NB. Ovenstående er selvfølgelig ikke den endegyldige turneringsplan runderne skal lige blandes for at overholde reglen om hjemme/ude bane! ta først runde et, så den lige efter den midterste runde (her 8, altså tag så 9)så 2 og 10 osv.. således at det ser sådan ud!
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
