[C++] Własna arytmetyka.

spammer
Użytkownik
Użytkownik
Posty: 174
Rejestracja: 15 sty 2009, o 17:28
Płeć: Mężczyzna
Podziękował: 40 razy
Pomógł: 12 razy

[C++] Własna arytmetyka.

Post autor: spammer »

Siemka.

Ostatnio zauważyłem, że w zadankach które robię trzeba wczytywać liczby np. od \(\displaystyle{ 10^{9}}\) do \(\displaystyle{ 10^{150}}\)

Zastanawiałem się jak zaimplementować własną arytmetykę. Wychodzi na to, że wcale nie jest to takie proste .

Męczę się nad takimi 2 zadankami już jakiś czas (z małymi przerwami na coś innego, żeby się rozerwać )

... ie&con=ALG
i


Co do 1 zadanka jakim jest pierwiastkowanie to mam zdaje się chyba prawie wszystko
Ukryta treść:    
Tylko problem jest taki, że zmienna: liczba s; nie jest zmienną typu double a nie wiem jak to zmienić.

A 2 zadanko tu mam problem z wczytaniem 1000000
Ukryta treść:    
Będę bardzo wdzięczny za pomoc.

******************************************************************************************************
*Edit(21.02.09r. godz: 17:49): Heh pomyliłem się w kodzie zadania 2 już go wkleiłem)*
******************************************************************************************************
Ostatnio zmieniony 21 lut 2009, o 17:53 przez spammer, łącznie zmieniany 3 razy.
Xitami

[C++] Własna arytmetyka.

Post autor: Xitami »

W drugim zadaniu nie chodzi o wielkie liczby.
Zapomnij o wielkich liczbach, zapomnij o ograniczeniach typu int,
zapisz rozwiązanie i powiedz ile operacji musisz wykonać zależnie od n?
Wyjdzie pewnie że będzie to około \(\displaystyle{ n^2}\), a zadanie da się rozwiązać w czasie liniowym.
I chodzi właśnie o znalezienie tego sprytnego algorytmu.

-- 22 lutego 2009, 00:35 --

Operację wyn = wyn + x[k]; wykonujesz około \(\displaystyle{ \frac{n^3}{6}}\) razy
jeżeli n wzrośnie dwukrotnie, liczba operacji wzrasta ośmiokrotnie
n może być równe nawet milion, wtedy tę operację wykonasz \(\displaystyle{ \approx\frac{10^{6^3}}{6}\approx1.7\cdot10^{215}}\) razy
wykonując powiedzmy miliard operacji na sekundę potrzebować będziesz około
\(\displaystyle{ \large5\cdot10^{197}}\) lat
Wiek wszechświata szacuje się na około \(\displaystyle{ 10^{10}}\) lat
Jak myślisz, SPOJ to przyjmie?

-- 22 lutego 2009, 00:47 --

łatwo można pozbyć się pętli po k, bo kiedy wzrasta j wystarczy wyn += x[j], prawda?
A wtedy if(wyn>naj) wykona się jakieś \(\displaystyle{ \frac{1}{2}n^2}\) razy,
ale i wtedy czas wykonania programu dla n=milion wielokrotnie przekroczy wiek wszechświata

mała podpowiedź: czy "naj" przedział może zaczynać się lub kończyć liczbą ujemną?

pewnym nie jest, ale możliwe, że nawet nie trzeba zapamiętywać wszystkich elementów tablicy

----------------------------------------------------------------------
a co do zadania pierwszego
łatwo zamienić liczbę s na double, ale wtedy zostanie z niej tylko kilkanaście cyfr, wynik będzie więc przybliżony, a nie o to chodzi.
Wynik ma być dokładny!
Na rozgrzewkę spróbuj to zrobić dla "normalnych" liczb, np. double, ale nie używając exp(), ln() ani pow().
ODPOWIEDZ