NepřihlášenKSP fórum
Fórum Hlavní stránka Nápověda Hledat Přihlásit
Nahoru Téma KSP / Úložky / 31-3-2 Cennější náhrdelník
- - Od IQuick Dne 13. 02. 2019 16:49
Dobrý den,

chtěl bych se zeptat na to, jak definujete "alespoň s pravděpodobností". Jestli myslíte "Ze všech stavů náhodného generátoru a možných vstupů je pravděpodobnost správnosti odpovědi >= 75%" nebo "Pro jakýkoliv vstup programu je pravděpodobnost správnosti odpovědi >= 75%"

Když už se ptám na tuto úlohu, tak přidám dotaz co mi to ten generátor náhodných čísel vůbec vyhodí, jestli číslo v nějakém fixním rozmezí 0 nebo 1 až N nebo snad jeden bit nebo dokonce jakékoliv přirozené číslo.
Vím, že nemůžu zadávat generátoru rozmezí ze kterého si má vybrat, protože to by muselo ovlivnit jeho výstup, což by porušilo zadání.
Ptám se, protože když si vezmu náhodné číslo R a provedu R % N potřebuji vědět zdali má výsledek rovnoměrnou náhodnou distribuci, protože jinak nemůžu spočítat pravděpodobnost chování algorithmu.

Za odpověď děkuji.
Nadřazený - Od RiHL (Org) Dne 28. 02. 2019 11:06
Ahoj!

Omlouváme se za pozdní odpověď, Tvůj dotaz nám trochu zapadl. Doufáme,
že je pořád relevantní.

> chtěl bych se zeptat na to, jak definujete "alespoň s
> pravděpodobností". Jestli myslíte "Ze všech stavů náhodného generátoru
> a možných vstupů je pravděpodobnost správnosti odpovědi >= 75%" nebo
> "Pro jakýkoliv vstup programu je pravděpodobnost správnosti odpovědi
> >= 75%"


Myslíme tím to druhé. Pokud stavem náhodného generátoru myslíme oba to
samé, pak pro jeden konkrétní stav je přesně dané, co generátor
vygeneruje, takže pro pevný vstup je přesně daná i komunikace, tím pádem
je pravděpodobnost správnosti odpovědi buď 0 %, nebo 100 %.

Mimochodem, předpokládáme, že náš generátor je opravdu náhodný, takže
"stav" generátoru neumíme popsat kompaktněji, než (nekonečnou)
posloupností bitů / čísel (viz další odpověď), kterou vygeneruje.

> Když už se ptám na tuto úlohu, tak přidám dotaz co mi to ten generátor
> náhodných čísel vůbec vyhodí, jestli číslo v nějakém fixním rozmezí 0
> nebo 1 až N nebo snad jeden bit nebo dokonce jakékoliv přirozené
> číslo.
> Vím, že nemůžu zadávat generátoru rozmezí ze kterého si má vybrat,
> protože to by muselo ovlivnit jeho výstup, což by porušilo zadání.
> Ptám se, protože když si vezmu náhodné číslo R a provedu R % N
> potřebuji vědět zdali má výsledek rovnoměrnou náhodnou distribuci,
> protože jinak nemůžu spočítat pravděpodobnost chování algorithmu.


Striktně vzato generátor generuje jednotlivé bity. Existují však
kontrukce, jak pomocí generátoru náhodných bitů generovat rovnoměrně
čísla 1 až N (nebo A až B), můžeš v řešení předpokládat, že je máš k
dispozici.

Mimochodem, vymyslet je není až tak těžké. Nejdřív si můžeš zkusit
rozmyslet, jak pomocí generátoru náhodných bitů generovat rovnoměrně
náhodně číslo z rozsahu 0 až 2^k - 1, a pak, jak z generátoru náhodných
čásel v rozsahu 0 až 2^k - 1 generovat náhodné číslo v obecném rozashu 0
až R - 1. Hint: to druhé nepůjde udělat na jeden dotaz na generátor, ale
v průměru (ve střední hodnotě) těch dotazů bude malý počet.

Ríša
- - Od Kvapca Dne 28. 02. 2019 09:03
Ahoj,

nikde v zadání jsem se nedočetl, může se sluha dozvědět cenu nějakého, případně obou náhrdelníků?

Děkuji za odpověď,
Jirka
Nadřazený - Od RiHL (Org) Dne 28. 02. 2019 11:10
Ahoj!

> nikde v zadání jsem se nedočetl, může se sluha dozvědět cenu nějakého,
> případně obou náhrdelníků?


Může, ale jelikož chudák moc rozumu nepobral, než dojde k druhé sestře,
zapomene ji :-). Řekněme, že sluha dokáže na jednu cestu přenést jen
jeden bit informace.

Ríša
Nahoru Téma KSP / Úložky / 31-3-2 Cennější náhrdelník

Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill