Czy istnieje sposób na znalezienie sumy cyfr 100 !?

Question

Wiem, że istnieje sposób na znalezienie sumy cyfr 100! (Lub dowolnej innej silnej liczby) za pomocą Pythona. Ale uważam, że to naprawdę trudne, jeśli chodzi o C++, ponieważ rozmiar nawet LONG LONG to za mało.

Po prostu chcę wiedzieć, czy jest jakiś inny sposób.

Rozumiem, że nie jest to możliwe, ponieważ nasz procesor ma zazwyczaj 32 bity. To, co mam na myśli, to inny rodzaj skomplikowanej techniki lub algorytmu, który może osiągnąć to samo przy użyciu tych samych zasobów.

Answer 1

long long nie jest częścią C++. g ++ zapewnia to jako rozszerzenie.

Arbitrary Precision Arithmetic to coś, czego szukasz. Sprawdź pseudokod podany na stronie wiki.

Ponadto long long nie może przechowywać tak dużych wartości. Możesz więc utworzyć klasę BigInteger lub korzystać z bibliotek innych firm, takich jak GMP lub C++ BigInteger.

Answer 2

Jeśli chodzi o problem związany z projektem Euler, moim odczytaniem tego jest to, że chce on napisać własną bibliotekę lub klasę całkowitą o dowolnej dokładności, które mogą mnożyć liczby.

Moja sugestia polega na przechowywaniu dziesięciocyfrowych cyfr numeru, w odwrotnej kolejności, niż zwykle piszesz, ponieważ i tak musisz w końcu przekonwertować liczbę na podstawę 10. Przechowywanie cyfr w odwrotnej kolejności sprawia, że ​​pisanie dodawania i mnożenia jest nieco łatwiejsze, moim zdaniem. Następnie zapisz procedury dodawania i mnożenia, które emulują sposób ręcznego dodawania lub mnożenia liczb.

Answer 3

Istnieje wiele bibliotek BigInteger dostępnych w C++. Po prostu Google "C++ BigInteger". Ale jeśli jest to problem z programowaniem, powinieneś lepiej spróbować zaimplementować własną bibliotekę BigInteger.

Answer 4

Jak znaleźć sumę cyfr 100 !. Jeśli obliczysz 100! najpierw, a następnie znaleźć sumę, a następnie jaki jest sens. Będziesz musiał użyć jakiejś inteligentnej logiki, aby go znaleźć bez faktycznego obliczania 100 !. Usuń wszystkie czynniki pięciu, ponieważ będą one tylko dodawać zera. Myśl w tym kierunku, zamiast myśleć o dużej liczbie. Jestem także pewien, że ostateczna odpowiedź to znaczy, że suma cyfr będzie w LONG LONG.

Istnieją duże biblioteki int C++, ale myślę, że nacisk jest położony na algorytm, a nie na bibliotekę.

Answer 5

Możesz wziąć łatwą drogę i użyć perl/python/lisp/scheme/erlang/etc, aby obliczyć 100! używając jednej z ich wbudowanych bibliotek bignum lub faktu, że niektóre języki używają dokładnej liczby całkowitej arytmetyki. Następnie weź ten numer, zapisz go w ciągu znaków i znajdź sumę znaków (z uwzględnieniem "0" = 48 itd.).

Albo, możesz wziąć to pod uwagę w 100 !, dostaniesz naprawdę dużą liczbę z wieloma zerami. Jeśli obliczysz 100! iteracyjnie, rozważ podzielenie przez 10 za każdym razem, gdy aktualna silnia jest podzielna przez 10. Wierzę, że da to wynik w zakresie długiego czasu lub czegoś.

Prawdopodobnie lepszym ćwiczeniem jest napisanie własnej biblioteki int. Będziesz potrzebował go na kilka późniejszych problemów, jeśli nie określisz sprytnych sztuczek.

Answer 6

Użyj tablicy cyfrowej za pomocą standardowej, papierowej metody namnażania.Na przykład, w C  :

#include <stdio.h> 

#define DIGIT_COUNT 256 

void multiply(int* digits, int factor) { 
    int carry = 0; 
    for (int i = 0; i < DIGIT_COUNT; i++) { 
    int digit = digits[i]; 
    digit *= factor; 
    digit += carry; 
    digits[i] = digit % 10; 
    carry = digit/10; 
    } 
} 

int main(int argc, char** argv) { 
    int n = 100; 

    int digits[DIGIT_COUNT]; 
    digits[0] = 1; 
    for (int i = 1; i < DIGIT_COUNT; i++) { digits[i] = 0; } 

    for (int i = 2; i < n; i++) { multiply(digits, i); } 

    int digitSum = 0; 
    for (int i = 0; i < DIGIT_COUNT; i++) { digitSum += digits[i]; } 
    printf("Sum of digits in %d! is %d.\n", n, digitSum); 

    return 0; 
} 

Answer 7

Zauważmy, że pomnożenie przez dowolną liczbę lub nie zmienia sumę cyfr.

Kiedy uznają, że widać, że mnożenie przez 2 i 5, lub przez 20 i 50, również nie zmienia sumę, ponieważ 2x5 = 10 i 20x50 = 1000.

Następnie zauważ, że za każdym razem, gdy twoje obecne obliczenie kończy się na 0, możesz po prostu podzielić przez 10 i kontynuować obliczanie silni.

Wykonaj kilka dodatkowych obserwacji dotyczących skrótów, aby wyeliminować liczby od 1 do 100, i myślę, że możesz dopasować odpowiedź do standardowych int.

Answer 8

Nic w projekcie Euler wymaga więcej niż __int64.

Sugerowałbym próbuje zrobić to za pomocą baza 10000.