Matematické Fórum

v.bohuslav · 16. 11. 2010 14:51

Dobrý den, tenhle problém jsem zde nadhodil už před 2 lety a nikdo mi nepomohl :( Tak jeste jeden pokus.

Jedná se o střelecké závody. Vstupem je počet střelců a počet střelnic. A mým úkolem je vygenerovat rozpis
střeleckých soubojů (každý s každým - podrobný a fakt pěkný návod jsem našel zde."http://www.tom-kot.cz/clanky/generovani-rozpisu-zapasu-v-systemu-kazdy-s-kazdym/ "),
ale můj problém pokračuje dál ... potřebuju aby se střelci prostřídali na různých střelnicích a ještě navíc na střelnici
na levé nebo pravé straně (na jedné střelnici střílí vždy 2 závodníci). Aby se nestalo, že jeden závodník bude stříle pořád na střelnici
číslo 1 a pořád v levo. Vím, že v tom bude nějáká pravděpodobnost, ale nevím jak na to.
Budu rád, když mi aspoň trošku poradíte.

Zdraví V.Bohuslav

petrkovar · 16. 11. 2010 15:07

↑ v.bohuslav:Kolik je střelců a kolik je střelnic? Je střelnic alespoň tolik, aby všichni mohli střílet současně?
Střídání vlevo/vpravo samozřejmě pro sudý počet střelců nelze dokonale zajistit, začnou-li dva střelci na stejné straně (a různých střelnicích), tak se nikdy nemohou potkat na stejné střelnici. Pro liché počty je pro střídání L/P situace (s ohledem na pauzu) jednodušší.

v.bohuslav

↑ petrkovar: Střelců může být hodně - přes 20 a střelnice jsou 2-4
při posledních závodech to bylo 25 střelců na 3 kurtech

petrkovar · 16. 11. 2010 15:56

Hraje každý s každým jednou nebo dvakrát (jako ve fotbale)?
Je nějaké omezení, zda mezi jednotlivými koly mají hráči mít krátkou nebo dlouhou přestávku. Co je spravedlivější a co příjemnější?

v.bohuslav · 16. 11. 2010 17:44

↑ petrkovar: Střelba probíhá každý s každým jen jednou. Snaha je aby rozpis byl co nejvíc "harmonický" tj. aby jeden soutěžící nestřílel neustále a ostatní jen nečekali.

v.bohuslav

Měl bych i nápad jak tento příklad vyřešit - pro jednoduchost zatím beru v potaz pouze rozhození střelců na střelnice (nerozlišuji pozici L/P na střelnici).

to je příklad 9 střelců na třech střelnicích (kurtech) - předpokládám, že u jiných počtů by to mohlo být podobné.

akorát nevím jak poskládat pořadí zápasů tj. vymyslet nějáký algoritmus, který by se dal realizovat programově.

petrkovar · 16. 11. 2010 21:46

↑ v.bohuslav:Mrknu se na to. Je už znám počet střelců a počet kurtů? Pro některé počty nebude existovat "dokonale spravedlivý" rozpis, zejména když počet dvojic nebude dělitelný počtem střelnic. A dále, pokud nebudeme trvat na tom, aby se jednotlivé střelnice pro každého hráče střídaly pravidelně, ale bude stačit, když každý bude střílet na každé střelnici zhruba stejný počet-krát (v libovolném pořadí), tak bude nalezení rozpisu výrazně jednodušší.
Do kdy má být rozpis hotov?

v.bohuslav

↑ petrkovar:Diky jste zlatej. Neni to nic bez ceho bych nemohl zit. S timto problemem bojuju uz dlouho :) Jinak počty střelců se mění dle počtu příchozích. U střelnic je to podobný - kolik jich je zrovna provozu schopných. To pravidelné střídání střelnic taky není úplně nutnou podmínkou. Důležité je aby se pravidelně střídali střelci (aby to jeden nemel hned odstřílený a další to měl ještě před sebou) a pak aby na každé střelnici odstřílel stejný (podobný) počet soubojů (v libovolném pořadí).

petrkovar · 22. 11. 2010 01:13

Zkusil jsem setavit rozpis pro 25 střelců a 3 střelnice. Postup umím zobecnit pro liché počty střelců a počet střelnic, který dělí (n-1)/2.
Střídání střelnic jsem ještě nedořešil, ale myslím, že to bude možné (pro 25 střelců a 3 střelnice). Než se pustím do popisu konstrukce, tak by mne zajímalo, zda rozpis vyhovuje požadavkům.
Každý střelec střílí na té straně, kde je zapsaný. Strany se (pokud jsem neudělal chybu) pro každého střelce pravidelně střídají.
kolo 1: 25- 1, 24- 2, 23- 3
kolo 2: 22- 4, 21- 5, 20- 6
kolo 3: 19- 7, 18- 8, 17- 9
kolo 4: 16-10, 15-11, 14-12
kolo 5: 4-23, 3-24, 2-25
kolo 6: 7-20, 6-21, 5-22
kolo 7: 10-17, 9-18, 8-19
kolo 8: 13-14, 12-15, 11-16
kolo 9: 2- 1, 25- 3, 24- 4
kolo 10: 23- 5, 22- 6, 21- 7
kolo 11: 20- 8, 19- 9, 18-10
kolo 12: 17-11, 16-12, 15-13
kolo 13: 1- 3, 5-24, 4-25
kolo 14: 8-21, 7-22, 6-23
kolo 15: 11-18, 10-19, 9-20
kolo 16: 14-15, 13-16, 12-17
kolo 17: 4- 1, 3- 2, 25- 5
kolo 18: 24- 6, 23- 7, 22- 8
kolo 19: 21- 9, 20-10, 19-11
kolo 20: 18-12, 17-13, 16-14
kolo 21: 2- 4, 1- 5, 6-25
kolo 22: 9-22, 8-23, 7-24
kolo 23: 12-19, 11-20, 10-21
kolo 24: 15-16, 14-17, 13-18
kolo 25: 6- 1, 5- 2, 4- 3
kolo 26: 25- 7, 24- 8, 23- 9
kolo 27: 22-10, 21-11, 20-12
kolo 28: 19-13, 18-14, 17-15
kolo 29: 3- 5, 2- 6, 1- 7
kolo 30: 10-23, 9-24, 8-25
kolo 31: 13-20, 12-21, 11-22
kolo 32: 16-17, 15-18, 14-19
kolo 33: 8- 1, 7- 2, 6- 3
kolo 34: 5- 4, 25- 9, 24-10
kolo 35: 23-11, 22-12, 21-13
kolo 36: 20-14, 19-15, 18-16
kolo 37: 3- 7, 2- 8, 1- 9
kolo 38: 4- 6, 11-24, 10-25
kolo 39: 14-21, 13-22, 12-23
kolo 40: 17-18, 16-19, 15-20
kolo 41: 10- 1, 9- 2, 8- 3
kolo 42: 7- 4, 6- 5, 25-11
kolo 43: 24-12, 23-13, 22-14
kolo 44: 21-15, 20-16, 19-17
kolo 45: 3- 9, 2-10, 1-11
kolo 46: 5- 7, 4- 8, 12-25
kolo 47: 15-22, 14-23, 13-24
kolo 48: 18-19, 17-20, 16-21
kolo 49: 12- 1, 11- 2, 10- 3
kolo 50: 9- 4, 8- 5, 7- 6
kolo 51: 25-13, 24-14, 23-15
kolo 52: 22-16, 21-17, 20-18
kolo 53: 3-11, 2-12, 1-13
kolo 54: 6- 8, 5- 9, 4-10
kolo 55: 16-23, 15-24, 14-25
kolo 56: 19-20, 18-21, 17-22
kolo 57: 14- 1, 13- 2, 12- 3
kolo 58: 11- 4, 10- 5, 9- 6
kolo 59: 8- 7, 25-15, 24-16
kolo 60: 23-17, 22-18, 21-19
kolo 61: 3-13, 2-14, 1-15
kolo 62: 6-10, 5-11, 4-12
kolo 63: 7- 9, 17-24, 16-25
kolo 64: 20-21, 19-22, 18-23
kolo 65: 16- 1, 15- 2, 14- 3
kolo 66: 13- 4, 12- 5, 11- 6
kolo 67: 10- 7, 9- 8, 25-17
kolo 68: 24-18, 23-19, 22-20
kolo 69: 3-15, 2-16, 1-17
kolo 70: 6-12, 5-13, 4-14
kolo 71: 8-10, 7-11, 18-25
kolo 72: 21-22, 20-23, 19-24
kolo 73: 18- 1, 17- 2, 16- 3
kolo 74: 15- 4, 14- 5, 13- 6
kolo 75: 12- 7, 11- 8, 10- 9
kolo 76: 25-19, 24-20, 23-21
kolo 77: 3-17, 2-18, 1-19
kolo 78: 6-14, 5-15, 4-16
kolo 79: 9-11, 8-12, 7-13
kolo 80: 22-23, 21-24, 20-25
kolo 81: 20- 1, 19- 2, 18- 3
kolo 82: 17- 4, 16- 5, 15- 6
kolo 83: 14- 7, 13- 8, 12- 9
kolo 84: 11-10, 25-21, 24-22
kolo 85: 3-19, 2-20, 1-21
kolo 86: 6-16, 5-17, 4-18
kolo 87: 9-13, 8-14, 7-15
kolo 88: 10-12, 23-24, 22-25
kolo 89: 22- 1, 21- 2, 20- 3
kolo 90: 19- 4, 18- 5, 17- 6
kolo 91: 16- 7, 15- 8, 14- 9
kolo 92: 13-10, 12-11, 25-23
kolo 93: 3-21, 2-22, 1-23
kolo 94: 6-18, 5-19, 4-20
kolo 95: 9-15, 8-16, 7-17
kolo 96: 11-13, 10-14, 24-25
kolo 97: 24- 1, 23- 2, 22- 3
kolo 98: 21- 4, 20- 5, 19- 6
kolo 99: 18- 7, 17- 8, 16- 9
kolo100: 15-10, 14-11, 13-12

v.bohuslav

↑ petrkovar:
V tom to rozpisu má třeba závodník číslo 25 většinu střeleckých soubojů na střelnici 3 :(.
Podobný rozpis jsem vygeneroval dle návodu zde : Odkaz.

petrkovar

Ano, střídání střelnic ještě není bráno v potaz. Zatím jsem se snažil o pravidelné střídání stran a přibližně rovnoměrné rozdělení pro každého mezi 100 kol.
EDIT: Hlavně mi šlo o to, zda jsem správně pochopil parametry zadání a nepřehlédl jsem jiné důležité vlastnosti. Zkusím se teď zaměřit na střídání střelnic.

petrkovar · 23. 11. 2010 23:42

Zkusil jsem se zaměřit na třídání střelnic a snažil dodržet střídání stran. Snad jsem nezavlekl jiné chyby.
Opět pořadí vlevo/vpravo znamená levá/pravá dráha a číslo v závorce udává číslo střelnice, na které se zápas odehrává. Každý střílí na každé střelnici alespoň 6x a nejvíce 10x a myslím, že nikdo nestřílí více než 2x za sebou na téže střelnici. Mělo by být dodrženo i *zhruba* pravidelné rozložení zápasů během turnaje pro každého střelce. Uvedený postup může fungovat *pouze* pro lichý počet střelců n, kdy počet střelnic s dělí (n-1)/2.

kolo 1: 24- 2(1), 23- 3(2), 25- 1(3),
kolo 2: 22- 4(1), 21- 5(2), 20- 6(3),
kolo 3: 17- 9(1), 19- 7(2), 18- 8(3),
kolo 4: 15-11(1), 14-12(2), 16-10(3),
kolo 5: 2-25(1), 3-24(2), 4-23(3),
kolo 6: 7-20(1), 5-22(2), 6-21(3),
kolo 7: 9-18(1), 10-17(2), 8-19(3),
kolo 8: 11-16(1), 12-15(2), 13-14(3),
kolo 9: 24- 4(1), 2- 1(2), 25- 3(3),
kolo 10: 22- 6(1), 21- 7(2), 23- 5(3),
kolo 11: 20- 8(1), 19- 9(2), 18-10(3),
kolo 12: 15-13(1), 17-11(2), 16-12(3),
kolo 13: 4-25(1), 5-24(2), 1- 3(3),
kolo 14: 6-23(1), 7-22(2), 8-21(3),
kolo 15: 11-18(1), 9-20(2), 10-19(3),
kolo 16: 13-16(1), 14-15(2), 12-17(3),
kolo 17: 4- 1(1), 3- 2(2), 25- 5(3),
kolo 18: 22- 8(1), 24- 6(2), 23- 7(3),
kolo 19: 20-10(1), 19-11(2), 21- 9(3),
kolo 20: 18-12(1), 17-13(2), 16-14(3),
kolo 21: 6-25(1), 1- 5(2), 2- 4(3),
kolo 22: 8-23(1), 9-22(2), 7-24(3),
kolo 23: 10-21(1), 11-20(2), 12-19(3),
kolo 24: 15-16(1), 13-18(2), 14-17(3),
kolo 25: 5- 2(1), 4- 3(2), 6- 1(3),
kolo 26: 25- 7(1), 24- 8(2), 23- 9(3),
kolo 27: 20-12(1), 22-10(2), 21-11(3),
kolo 28: 18-14(1), 17-15(2), 19-13(3),
kolo 29: 1- 7(1), 2- 6(2), 3- 5(3),
kolo 30: 10-23(1), 8-25(2), 9-24(3),
kolo 31: 12-21(1), 13-20(2), 11-22(3),
kolo 32: 14-19(1), 15-18(2), 16-17(3),
kolo 33: 6- 3(1), 8- 1(2), 7- 2(3),
kolo 34: 25- 9(1), 24-10(2), 5- 4(3),
kolo 35: 23-11(1), 22-12(2), 21-13(3),
kolo 36: 18-16(1), 20-14(2), 19-15(3),
kolo 37: 2- 8(1), 3- 7(2), 1- 9(3),
kolo 38: 4- 6(1), 10-25(2), 11-24(3),
kolo 39: 14-21(1), 12-23(2), 13-22(3),
kolo 40: 16-19(1), 17-18(2), 15-20(3),
kolo 41: 10- 1(1), 9- 2(2), 8- 3(3),
kolo 42: 25-11(1), 7- 4(2), 6- 5(3),
kolo 43: 23-13(1), 22-14(2), 24-12(3),
kolo 44: 21-15(1), 20-16(2), 19-17(3),
kolo 45: 3- 9(1), 1-11(2), 2-10(3),
kolo 46: 5- 7(1), 12-25(2), 4- 8(3),
kolo 47: 13-24(1), 14-23(2), 15-22(3),
kolo 48: 18-19(1), 16-21(2), 17-20(3),
kolo 49: 11- 2(1), 10- 3(2), 12- 1(3),
kolo 50: 9- 4(1), 8- 5(2), 7- 6(3),
kolo 51: 23-15(1), 25-13(2), 24-14(3),
kolo 52: 21-17(1), 20-18(2), 22-16(3),
kolo 53: 1-13(1), 2-12(2), 3-11(3),
kolo 54: 6- 8(1), 4-10(2), 5- 9(3),
kolo 55: 15-24(1), 16-23(2), 14-25(3),
kolo 56: 17-22(1), 18-21(2), 19-20(3),
kolo 57: 12- 3(1), 14- 1(2), 13- 2(3),
kolo 58: 10- 5(1), 9- 6(2), 11- 4(3),
kolo 59: 8- 7(1), 25-15(2), 24-16(3),
kolo 60: 21-19(1), 23-17(2), 22-18(3),
kolo 61: 2-14(1), 3-13(2), 1-15(3),
kolo 62: 4-12(1), 5-11(2), 6-10(3),
kolo 63: 17-24(1), 7- 9(2), 16-25(3),
kolo 64: 19-22(1), 20-21(2), 18-23(3),
kolo 65: 16- 1(1), 15- 2(2), 14- 3(3),
kolo 66: 11- 6(1), 13- 4(2), 12- 5(3),
kolo 67: 9- 8(1), 25-17(2), 10- 7(3),
kolo 68: 24-18(1), 23-19(2), 22-20(3),
kolo 69: 3-15(1), 1-17(2), 2-16(3),
kolo 70: 5-13(1), 6-12(2), 4-14(3),
kolo 71: 7-11(1), 8-10(2), 18-25(3),
kolo 72: 21-22(1), 19-24(2), 20-23(3),
kolo 73: 17- 2(1), 16- 3(2), 18- 1(3),
kolo 74: 15- 4(1), 14- 5(2), 13- 6(3),
kolo 75: 10- 9(1), 12- 7(2), 11- 8(3),
kolo 76: 24-20(1), 23-21(2), 25-19(3),
kolo 77: 1-19(1), 2-18(2), 3-17(3),
kolo 78: 6-14(1), 4-16(2), 5-15(3),
kolo 79: 8-12(1), 9-11(2), 7-13(3),
kolo 80: 20-25(1), 21-24(2), 22-23(3),
kolo 81: 18- 3(1), 20- 1(2), 19- 2(3),
kolo 82: 16- 5(1), 15- 6(2), 17- 4(3),
kolo 83: 14- 7(1), 13- 8(2), 12- 9(3),
kolo 84: 24-22(1), 11-10(2), 25-21(3),
kolo 85: 2-20(1), 3-19(2), 1-21(3),
kolo 86: 4-18(1), 5-17(2), 6-16(3),
kolo 87: 9-13(1), 7-15(2), 8-14(3),
kolo 88: 22-25(1), 23-24(2), 10-12(3),
kolo 89: 22- 1(1), 21- 2(2), 20- 3(3),
kolo 90: 17- 6(1), 19- 4(2), 18- 5(3),
kolo 91: 15- 8(1), 14- 9(2), 16- 7(3),
kolo 92: 13-10(1), 12-11(2), 25-23(3),
kolo 93: 3-21(1), 1-23(2), 2-22(3),
kolo 94: 5-19(1), 6-18(2), 4-20(3),
kolo 95: 7-17(1), 8-16(2), 9-15(3),
kolo 96: 24-25(1), 10-14(2), 11-13(3),
kolo 97: 23- 2(1), 22- 3(2), 24- 1(3),
kolo 98: 21- 4(1), 20- 5(2), 19- 6(3),
kolo 99: 16- 9(1), 18- 7(2), 17- 8(3),
kolo100: 14-11(1), 13-12(2), 15-10(3),

v.bohuslav · 24. 11. 2010 12:27

Zatím je to nejlepší výsledek ... :) Když jsem se o tomhle problému dozvěděl, tak jsem říkal zítra to bude hotovo ... ale už se to táhne proklatě dlouho a toho času (a nejen mojeho a vašeho) co to zabralo :)

petrkovar · 24. 11. 2010 14:05

↑ v.bohuslav:Velmi by mne zajímalo, kde se uvedený rozpis používá. Jedná se o soutěž nebo spolek, máte nějaký odkaz na webu?
Děkuji.

petrkovar · 24. 11. 2010 15:30

↑ v.bohuslav:... protože o problému losování sportovních soutěží něco málo vím, tak nečekám, že se jedná o snadno řešitelnou úlohu. Naopak, jen díky velmi omezujícím podmínkám jsem našel vhodné řešení až nečekaně rychle.

v.bohuslav · 25. 11. 2010 15:47

↑ petrkovar:Požádal mě o to můj kamarád. Pořádá střelecké závody. Vždy musel pořadí soubojů a střelnic rozdělovat ručně a to je dost náročné a taky to není rovnoměrně rozdělené. Tak jsem mu napsal jednouduchý prográmek a ten mu to generoval, dokonce mam pocit, že pro některé kombinace počtů střelců a střelnic dával "dost dobrý" rozpisy . Ale rád by abych program dotáhnul k "dokonalosti". A to je zatím kámen úrazu ...

tkovar · 19. 03. 2014 07:34

Dobrý den. Toto téma je otevřeno již dlouho. Pokud je pro vás problém sestavování rozpisu pro střeleckou soutěž ještě alespoň trochu aktuální, dejte prosím vědět. Myslím, že bych mohla mít k dispozici zajímavé řešení.

Matematické Fórum

#1 16. 11. 2010 14:51

Rozpis zápasů

#2 16. 11. 2010 15:07

Re: Rozpis zápasů

#3 16. 11. 2010 15:14 — Editoval v.bohuslav (16. 11. 2010 15:15)

Re: Rozpis zápasů

#4 16. 11. 2010 15:56

Re: Rozpis zápasů

#5 16. 11. 2010 17:44

Re: Rozpis zápasů

#6 16. 11. 2010 19:31 — Editoval v.bohuslav (16. 11. 2010 19:33)

Re: Rozpis zápasů

#7 16. 11. 2010 21:46

Re: Rozpis zápasů

#8 18. 11. 2010 08:18 — Editoval v.bohuslav (18. 11. 2010 15:51)

Re: Rozpis zápasů

#9 22. 11. 2010 01:13

Re: Rozpis zápasů

#10 23. 11. 2010 20:12 — Editoval v.bohuslav (23. 11. 2010 20:13)

Re: Rozpis zápasů

#11 23. 11. 2010 21:31 — Editoval petrkovar (23. 11. 2010 21:43)

Re: Rozpis zápasů

#12 23. 11. 2010 23:42

Re: Rozpis zápasů

#13 24. 11. 2010 12:27

Re: Rozpis zápasů

#14 24. 11. 2010 14:05

Re: Rozpis zápasů

#15 24. 11. 2010 15:30

Re: Rozpis zápasů

#16 25. 11. 2010 15:47

Re: Rozpis zápasů

#17 19. 03. 2014 07:34

Re: Rozpis zápasů

Zápatí