Diskuze: Algoritmus na rozřazení žáků do třídy

Naučíme tě pracovat na home-office.

Zjistit více...

V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Petr Šťastný

Tvůrce

Petr Šťastný:11.12.2017 19:43

Ahoj, chtěl bych napsat jednu aplikaci a potýkám se s jedním algoritmem. Musím vytvořit nějaký, který by vyřešil následující:

Mám jednu místnost, která je otevřená některé dny v týdnu od # do # hodin. (Každý den může být otevřená v jiný čas)

Mám N žáků, kde každý musí během týdne místnost navštívit právě jednou. V místnosti může být najednou maximálně jeden žák.

Každý žák v místnosti musí strávit # minut.

Jakým způsobem určím, kdy má který žák jít do místnosti? Nemůžu to vymyslet, potřeboval bych trochu popostrčit.

Díky, Petr

Odpovědět

11.12.2017 19:43

DarkCoder

Člen

DarkCoder:11.12.2017 22:22

if (pocet_zaku > (kapacita_zaku = (otevreno_dnu_v_tydnu * (((otevreno_do - otevreno_od) * 60) / pocet_minut))))
                printf("Pro %d zaku neni mozne najit termin a je treba je pro nadbytecnost vyhodit.\n", pocet_zaku - kapacita_zaku);
else printf("Denne muze navstivit mistnost misto hospody postupne az %d zaku.\n", ((otevreno_do - otevreno_od) * 60) / pocet_minut);

Editováno 11.12.2017 22:22

Nahoru Odpovědět

11.12.2017 22:22

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Petr Šťastný

Tvůrce

Petr Šťastný:12.12.2017 7:20

Díky Ale teď mi došlo, že jsem blbě napsal, co potřebuji.

Každý žák má volno pouze některé dny v týdnu a v určité hodiny. A já potřebuju zjistit, kdy tam který má jít.

Promiň, asi jsem tě tím zbytečně okradl o čas

Nahoru Odpovědět

12.12.2017 7:20

DarkCoder

Člen

DarkCoder:12.12.2017 17:40

To už tak triviální není, ale není to těžké. Je třeba hlídat dva stavy. Tím prvním je počet termínů pro každého žáka, na který se může dostavit. A tím druhým je počet žáků, kteří se mohou dostavit na daný termín. Prioritně pracuji s tím žákem, který má nejméně možných termínů. Stejně tak u termínů, pracuji s tím, na který se může dostavit co nejméně žáků. Pokud tedy mám žáka, který se může dostavit na jeden jediný termín, automaticky jej k tomuto termínu přiřazuji. Pokud mám termín, na který se může dostavit jeden jediný žák, automaticky jej k němu přiřazuji. V okamžiku, kdy přiřazuji žáka k nějakému termínu je třeba aktualizovat počet termínů u žáků, kteří se mohli na tento termín dostavit. Stejně tak pro každý termín je třeba aktualizovat počet žáků, na který se daný žák mohl dostavit. Žáka, který může kdykoli, s tím pracuji jako poslední, neboť ho lze použít jako výplň kamkoli. To jsou hlavní pravidla pro přiřazení žáka na konkrétní termín.

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

12.12.2017 17:40

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Petr Šťastný

Tvůrce

Petr Šťastný:12.12.2017 18:37

Dobře, díky :-) Trochu mi to připomíná, když jsem jednou dělal algoritmus na sudoku Zkusím z toho nějak vyjít, mělo by to tak fungovat. Díky.

Jenom nevím, co budu dělat za předpokladu, že není ani na začátku žádný žák, který by měl nějaký termín 100% jistý. Taky by další problém mohl být, že časy nejsou rozfázované jako hodiny ve škole: Žák může být v místnosti 13:00-13:45 stejně jako 13:10-13:55 atd. Ale to už asi zvládnu vymyslet. Díky

Nahoru Odpovědět

12.12.2017 18:37

David Dostal

Tvůrce

David Dostal:12.12.2017 19:00

Na sudoku jsem si také hned vzpoměl :-)
S těmi minutami to bude trochu problém, pokud každý žák má různě dlouhé časy. Pokud to zvládneš nějak formulovat jako exact cover problém, tak by to jako sudoku mělo jít pomocí Knuthova algoritmu (https://en.wikipedia.org/…_Algorithm_X).

Nahoru Odpovědět

12.12.2017 19:00

DarkCoder

Člen

DarkCoder:12.12.2017 19:04

Přesně tak, určitá spojitost se sudoku tu je a to zejména ta část, kde není vždy na první pohled zřejmé, čím začít. Přemýšlíš nad tím velmi dobře, nestandartní časy to rozhodně trochu zkomplikují. Testů a kontrol tam bude opravdu dost, které bude třeba provádět při každé změně. Určitě si užiješ spoustu řazení či procházení celého pole. Ze začátku bude dobré stanovit si dobu v místnosti na nějakou rozumnou hodnotu a výpočet provést na menším počtu žáků. Tam se zamyslet nad tím proč právě tohoto žáka beru dříve než jiného a přiřazuji mu dostupný termín. Každopádně je to hodně zajímavá úloha, jejíž jádro můžeš následně použít v mnoha dalších aplikacích.

Nahoru Odpovědět

12.12.2017 19:04

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Petr Šťastný

Tvůrce

Petr Šťastný:30.12.2017 11:08

Tak pořád nevím, jakým způsobem bych to formuloval jako exact cover. Už nad tím nějakou chvíli dumám a jediné, co mě napadlo, je nějaký brute force algoritmus, podobně jako psal DarkCoder. Nenapadá tě, jakým způsobem by to šlo udělat pomocí exact cover? Stačí, kdybys mi mohl poradit jakým způsobem to mám brát, abych na to mohl použít ten knuthův algoritmus, zbytek zvládnu. Prostě mi přijde, že brutal force není optimální řešení a protože na dokončení mám čas do května a v posledních týdnech jsem udělal grafickou stránku věci, myslím, že není důvod se hned hrnout k brutal force, když existuje lepší řešení.

Díky, Petr

Nahoru Odpovědět

30.12.2017 11:08

David Dostal

Tvůrce

David Dostal:30.12.2017 22:14

Ahoj, už je to dost dávno, ale zkusím se na to podívat :-) Přes nový rok jsem v zahraničí, takže se k tomu dostanu až za pár dnů.

Nahoru Odpovědět

30.12.2017 22:14

Petr Šťastný

Tvůrce

Petr Šťastný:30.12.2017 22:24

Dobře, díky Jenom bych byl rád, kdybys mi napsal, kdyby tě něco napadlo, nepotřebuji to nijak urgentně a kdyžtak to udělám hrubou silou, jenom sem se chtěl zeptat, jestli tě něco nenapadlo.

Nahoru Odpovědět

30.12.2017 22:24

David Dostal

Tvůrce

David Dostal:3.1.2018 16:34

Ahoj, nemám teď čas to příliš studovat, ale poskytnu pár odkazů na stránky, kde je to dobře popsané a ze kterých jsem tehdy čerpal.

Dobře je exact cover popsaný například na stránkách:
http://garethrees.org/…-generation/ a
https://gieseanw.wordpress.com/…u-revisited/

Případně ještě přímo Knuthova práce, exact cover tam je ale popsaný jen letmo:
https://www.ocf.berkeley.edu/…/0011047.pdf
nebo článek na Wikipedii (trochu teoretičtější):
https://en.wikipedia.org/…/Exact_cover

Snad Ti to pomůže :-)

Nahoru Odpovědět

3.1.2018 16:34

Petr Šťastný

Tvůrce

Petr Šťastný:3.1.2018 16:40

Díky

Nahoru Odpovědět

3.1.2018 16:40

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 12 zpráv z 12.