Matematické Fórum

↑ hessyk:

Je to zase úloha na dynamické programování. Zkus se zamyslet, jak by mohla vypadat tabulka, do které budeš ukládat nějaké ty "optimální mezivýpočty".

(konkrétně tento příklad mi přijde dost podobný jako ta abeceda, jen o něco snazší)

↑ hessyk:

No, cíl je klasický, jako v polovině úloh na dynamické programování - něco maximaloizovat (výhru).

Hra je následující:

Na začátku má soutěžící proti sobě 100 soupeřů.

V každém kole se vyřadí nějaký nenulový počet soupeřů (v různých kolech různý, ale označme si jej teď pro nějaké konkrétní kolo v) ze zbývajícího počtu soupeřů (označme jej pro to stejné konkrétní kolo p); Za toto uvažované kolo vyhraje soutěžící 100000*p/v peněz. Jakmile vyřadí soutěžící všech sto soupeřů, vyhrává s celkovou sumou, kterou v průběhu hry získal.

No a ty máš napsat program / rozmyslet algoritmus takový, že když ti někdo zadá nějaký počet kol K, po který má soutěž probíhat (tedy přesně v K-tém kole vyřadíme posledního soupeře), tak program určí, kolik se má v konkrétních kolech vyřadit soupeřů tak, aby výhra byla maximální.

Tedy na vstupu programu bude třeba 2 (tj "soutěž bude probíhat 2 kola")
No a program odpoví:
199 000 ("maximální výhra je 199 000")
99
1 ("první kolo vyřaď všechny soupeře až na jednoho - získáš 99 000, a v druhém kole zbývajícího soupeře - získáš dalších 100 000")

Algoritmus i ta stěžejní matice jsou velmi podobné, jako u těch tlačítek a abecedy (na rozdíl od např. těch dvou loděk - ty mi přišly těží, špatně se představují).

↑ hessyk:

A abecedu užs teda pochopil... ? : )

Tady je to totiž dost podobné. V zásadě si jen vytvoříme tabulku Sij velikosti (počet kol) x 100, v políčku Sij bude optimální zisk takový, že po odehrání i-tého kola bude vyřazeno přesně j protihráčů. Políčko tabulky se bude vyplňovat prakticky stejně, jako u abecedy (mrknu na možnosti, kolik jsem jich mohl mít vyřazeno po minulém kole a kolik jsem za to mohl vydělat, přičtu k tomu, kolik bych vydělal, kdybych dovyhazoval zbylý počet hráčů do j, no a z těchto čísel vezmu tentokrát maximum, jelikož mi jde o to, maximalizovat zisk).