4. úloha - Zápasy s hokejkami

[BašKa]

ja sa chcem opýtať prečo mi to vyhadzuje Zlé odpovede, lebo ja som si všetko skontrolovala, a fakt neviem čo tam mám zle, aj všetky premenné, či mi náhodou nepretekajú

[USAmec]

si si fakt ista, ze tam chces long doubly?

akoze to, co ti spravi pri vyssich cislach je, ze to vypise:
1.2333+e15

(tomuto sa da vyhnut kebyze to vypisujes cez printf, ale fakt bych sa nad tymi doublami zamyslel)

[BašKa]

ďakujem

[Askar_Gafurov]

mám považovať základné operácie za konštantné (násobenie, porovnávanie)?

[USAmec]

ano.

[kabell]

funkcia pow() má konštantnú časovú zložitosť??, alebo lineárnu

[Askar_Gafurov]

@kabell:
skor logaritmicku

[Xellos]

da sa spravit umocnenie v logaritmickej casovej zlozitosti, ale o
konstantnej dost pochybujem
na tvojom mieste ale trochu popremyslam nad jednoduchsim riesenim

[Bob]

ak chceš umocňovať rýchlejšie ako v lineárnom čase (v závislosti od exponenta), mal by si v popise spomenúť, ako to robíš

na doplnenie: aj základné binárne operácie (and, or, not, xor, left/right shift) môžete považovať za pracujúce v konštantnom čase

[mišof]

(04.01.2012 22:40:43)kabell Napísal:  funkcia pow() má konštantnú časovú zložitosť??, alebo lineárnu

Funkcia pow() má časovú zložitosť konštantnú, ale to len preto, že pracuje s nepresnými reálnymi číslami, ktoré majú presnosť len na konštantne veľa cifier.

Dá sa napr. naskladať z funkcií e^x a ln(x) takto: pow(x,y) = exp(y*ln(x))

Používať pow() na výpočty na celých číslach nie je zrovna výhra. A ak konkrétne treba mocninu dvoch, tú je najlepšie vyrábať cez bitové posuny: 2^x je v pascale (1 shl x), resp. v c++ to je (1 << x).