Original title:
Kombinatorické úlohy o mincích
Translated title:
Combinatorial problems with coins
Authors:
Hamáček, Jan ; Slavík, Antonín (advisor) ; Fiala, Jiří (referee) Document type: Master’s theses
Year:
2016
Language:
cze Abstract:
Práce se zabývá otázkami reprezentace zvolené částky pomocí libovolného množství mincí předep- saného typu. V první kapitole odvozujeme vzorce pro počet nereprezentovatelných částek a hodnotu největší nereprezentovatelné částky pro dvoumincové systémy. Dále ukazujeme grafový algoritmus pro výpočet Frobeniova čísla a d·kaz NP-úplnosti rozhodovacího problému reprezentovatelnosti zvolené částky v systému s více mincemi. V druhé kapitole se zabýváme výpočtem počtu reprezentací částky zvláš' v systémech o dvou nebo více mincích. Ve třetí kapitole se věnujeme otázce, zda lze ve zvoleném systému mincí použít hladový algoritmus pro nalezení reprezentace částky pomocí nejmenšího možného množství mincí. Poslední kapitola obsahuje sbírku řešených logických úloh o mincích. 1
Keywords:
coin system; Frobenius number; greedy algorithm; minimal representation; problems with coins; representability; representation count; Frobeniovo číslo; hladový algoritmus; minimální reprezentace; počet reprezentací; reprezentovatelnost; systémy mincí; úlohy o mincích
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/83103