Silnia dużych liczb

[Arkarius]

Na RecruitCoders jest zadanie

 

GML

You are asked to calculate factorials of some small positive integers.

Input

 

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output

 

For each integer n given at input, display a line with the value of n!

Example

Sample input:

4

1

2

5

3

 

Sample output:

1

2

120

6

 

Napisałem ten algorytm, liczy to co trzeba, jedyny problem jest taki, że limit czasu wykonania programu ustalony jest na 1s.

 

Natomiast mój algorytm potrzebuje co najmniej kilku sekund na obliczenia. Skorzystałem z pomysłu, aby mnożyć stringi, tak jak mnoży się liczby sposobem pisemnym, bo nie ma zmiennej która pomieściłaby silni z liczby 90 chociażby. Jest jakikolwiek inny szybszy sposób?

 

E: z rozpędu dałem to tutaj, siedziałem nad tym od rana i się wku***łem, jak przekroczyło ten limit xd jakby można było przenieść do odpowiedniego działu to byłbym wdzięczny.

[Platyna]

Ale syfny kod. Nie chce mi się go analizować. Jaką ma złożoność? Generalnie pierwsze co mi się w oczy rzuciło to wewnątrz funkcji odwroc() tworzysz jakąś wielką tablicę stringów temp[]. Tablice powinno się raczej zawsze tworzyć globalnie. To też ci zabiera czas jak za każdym razem alokujesz pamięć. A przecież możesz używać cały czas tej samej tablicy.

Generalnie to złożoność oczekiwana jest n^3 na co wskazuje n<=100.

n! jest liczbą rzędu n^n czyli (logarytm o podstawie 10 z n)*n cyfr. Logarytm jest pomijalny bo dla 100 jest równy 2. Czyli mamy n cyfr.

Mnożenie pisemne dwóch liczb x i y ma złożoność (log10 z x)*(log10 z y) czyli iloczyn ilości cyfr. U nas będzie to więc pesymistycznie n^2.

 

Dobrze robisz, że piszesz własną arytmetykę, ale coś w niej musiałeś sknocić. Bo:

n operacji mnożenia dwóch liczb po n cyfr to łącznie daje nam nasz n^3. Powinno być szybko.

 

Nie idzie tego zrobić szybciej więc coś musiałeś implementacyjnie sknocić. Mam Ci to napisać na nowo czy sobie poradzisz?

 

P.S. Skąd jest to zadanie?

 

EDIT: Ach, sorka. Zapomniałem o 100 przypadkach testowych. Czyli mamy t*n^3. To już za dużo. Pomyślę nad czymś szybszym. Generalnie do własnej arytmetyki można zamiast komórki na każdą cyfrę to sklejać ze sobą long longi. To już nam znacznie zmniejszy stałą.

 

EDIT2:

Dobra, już wiem jak ominąć te przypadki testowe. Jaki jest limit na pamięć? Bo moim zdaniem wystarczy zastosować spamiętywanie. Obliczasz raz wszystkie wyniki silni od 1 do 100 i spamiętujesz w tablicy. Żeby obliczyć x! należy również obliczyć (x-1)! więc po co to robić kilka razy? Obliczasz do setki i wyniki pamiętasz. Potem tylko wypisujesz z tablicy.

Masz do spamiętania n liczb po n cyfr. Powinno się bezproblemowo zmieścić w pamięci.

[Arkarius]

Co do kodu to wiem, że syfny, i napewno katorga to analizować, ale przejrzystość kodu to jeszcze nie jest moja mocna strona :P. A co do problemu to tak jak mówiłeś, wystarczyło spamiętywać silnie poszczególnych liczb do tablicy, a później zamiast liczyć to sprawdzać czy nie jest już policzona, i z paru sekund zmieściłem sie w 0,78s :) A zadanie to jest z RecruitCoders.com, nie wiem czy orientujesz się co to jest spoj, ale robiłem tam kilka zadań, i na maila przysłali mi, że zrobili jakąś platformę dla programistów, i tam niby można potwierdzać swoje umiejętności poprzez rozwiązywanie takich zadań.

 

E: A co do tej tablicy temp [], to nie była potrzebna, coś miałem z nią robić, a później o niej zapomniałem, ale w tej wersji co wysyłałem i tak jej nie było, bo przed wysłaniem musiałem usunąć z kodu wszystko co niepotrzebne, białe znaki, poskracać nazwy zmiennych itp, bo limit długości kodu wynosił 2000B.

[Platyna]

Tia. Orientuję się co to SPOJ, ale za dużo zadań stamtąd nie robiłem. Wolę maina.

[Will]

Nie używaj obiektów z biblioteki standardowej cout/cin/stringstream/string w tego typu zadaniach. Obiekty powyżej 4 bytes przekazuj przez referencje. Nie wiem po co też bawisz się w konwersje. Przechowanie jednej liczby jako string to też jest bardzo głupi pomysł.