Využij akce až 30 % zdarma při nákupu e-learningu. Více informací. Zároveň je tento týden sleva až 80 % na e-learning týkající se C# .NET
Hledáme nového kolegu do redakce - 100% home office, 100% flexibilní pracovní doba. Více informací.
discount week 30 halloween
Avatar
Ferko
Člen
Avatar
Ferko:5.3.2018 17:06

Ahoj,
mám problém s jedným programom:
Máme pole n čísel <1..100> a q otázok. Každá otázka je tvorená troma číslami (o,d,m). Pre každú otázku treba napísať (súčin čísel ležiacich v poli na pozíciach o až o+d-1) mod m.

Problém je, že n môže byť aj 105, čo zapríčiní, že súčin sa nezmestí ani do long a BigInteger je pomalý.

Nenapadá vás nejaké rozumnejšie riešenie?

Ďakujem

Príklad princípu v Pythone:

for i in range(q):
    o,d,m=input().split()
    o,d,m=int(o),int(d),int(m)
    s=1
    for j in range(o-1,o+d-1):
       s*=p[j]
    print(s%m)
Editováno 5.3.2018 17:07
 
Odpovědět
5.3.2018 17:06
Avatar
DHPICO
Redaktor
Avatar
Odpovídá na Ferko
DHPICO:5.3.2018 17:42

když se ti to nejvejde do Long, tak můžeš rozložit výpočet a ukládat si to do Stringu, ale nedokážu říct, zda to je rychlejší než BigInteger

Nahoru Odpovědět
5.3.2018 17:42
Požehnáni budíš oráj
Avatar
krepsy3
Redaktor
Avatar
krepsy3:5.3.2018 17:58

BigInteger je, alespoň v .NETu, velmi dobře optimalizovaná struktura. Zároveň je bezpečná a spolehlivá. Nevím, zda by specificky tento úkol šel matematicky udělat nějakou rychlejší cestou přes string, nicméně bych ti doporučil bigint.

Zamyslím-li se, tak jako zrovna 105 je celkem v pohodě, protože je to ta desítka, za kterou se ti kumulují nuly, jak víc a víc násobíš, takže by to šlo řešit cestou "dvojího násobení" - v hlavní cestě násobíš čísla a odtrhuješ nulové řády, jejichž exponent pak násobíš v té druhé cestě, a ve finálním výpisu to dáš dohromady. Teoreticky by se tato možnost dala aplikovat na jakákoliv čísla ve "věděcké notaci" a ukládat do typu double, ale hrozilo by znepřesnění výpočtu kvůli desetinné čárce, pokud by čísel bylo moc.

P.S. Vědecká notace = 3278.2 = 3.2782e3 = 3.2782 * 103

Editováno 5.3.2018 18:00
Nahoru Odpovědět
5.3.2018 17:58
Programátor je stroj k převodu kávy na kód.
Avatar
Jindřich Máca
Redaktor
Avatar
Jindřich Máca:5.3.2018 18:13

Pánové, opravdu? :D Jelikož tohle je typický "školní" příklad, tak trik je čistě matematický. Čísla řádu 105, dokonce i vynásobená mezi sebou, se do long bohatě vejdou a víc nepotřebujete, protože Základní pravidla modulární aritmetiky. :-`

Můžete modulovat po každém násobení, dokonce každé to číslo samotné před tím násobením, což většinou značně sníží jeho řád, a pokud modulujete všechno stejným číslem, celkový výsledek se nezmění. ;)

Editováno 5.3.2018 18:14
 
Nahoru Odpovědět
5.3.2018 18:13
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Patrik Valkovič
Člen IT Redactor Gang
Avatar
Nahoru Odpovědět
5.3.2018 18:17
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ferko
Člen
Avatar
Odpovídá na Jindřich Máca
Ferko:5.3.2018 18:39

Ďakujem, toto by teda malo fungovať?

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s mod m);
  end;

alebo aj toto?

for j:=a to a+x-1 do s*=(k[j] mod m);
 
Nahoru Odpovědět
5.3.2018 18:39
Avatar
Jindřich Máca
Redaktor
Avatar
Odpovídá na Ferko
Jindřich Máca:6.3.2018 0:33

Lépe bude fungovat to první, protože v tom druhém Ti s bude pořád narůstat, i když o něco pomaleji a na konci ho pak musíš ještě zmodulovat do výsledné podoby. Naopak u toho prvního držíš celé s pravidelnou modulací v přiměřeném rozsahu a po skončení cyklu už ho ani modulovat nemusíš. ;)

Pro jistotu tedy:

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s); # s již prošlo mod na konci cyklu
  end;

P.S.: Nejlepší bude, když si sám napíšeš nějakou krátkou řadu malých čísel a zkusíš si to spočítat, jestli to sedí. :)

 
Nahoru Odpovědět
6.3.2018 0:33
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 7 zpráv z 7.