Есть ли способ найти сумму цифр 100 !?

Question

Я знаю, что есть способ найти сумму цифр 100! (Или факториал любого другого большого числа) с использованием Python. Но я считаю, что это очень сложно, когда дело доходит до C++, как размер даже LONG LONG недостаточно.

Я просто хочу знать, есть ли другой способ.

Я понимаю, что это невозможно, так как наш процессор, как правило, 32 бит. То, что я имею в виду, это какой-то другой сложный метод или алгоритм, который может выполнять то же самое, используя одни и те же ресурсы.

Answer 1

long long не является частью C++. g ++ предоставляет его как расширение.

Arbitrary Precision Arithmetic - это то, что вы ищите. Проверьте псевдокод, указанный на странице вики.

Более того, long long не может хранить такие большие значения. Таким образом, вы можете создать свой класс BigInteger или использовать некоторые сторонние библиотеки, например GMP или C++ BigInteger.

Answer 2

Если вы имеете в виду проблему Project Euler, то мое чтение состоит в том, что он хочет, чтобы вы написали свою собственную целую библиотеку произвольной точности или класс, который может умножать числа.

Мое предложение состоит в том, чтобы хранить базовые 10 цифр числа в порядке, обратном порядку их записи, потому что в конце концов вам нужно будет преобразовать число в базу 10. Сохранение цифр в обратном порядке делает запись, по-моему, более простой и удобной процедуры добавления и умножения. Затем создайте процедуры добавления и умножения, которые эмулируют, как вы будете добавлять или умножать числа вручную.

Answer 3

В C++ имеется несколько библиотек BigInteger. Просто Google "C++ BigInteger". Но если это проблема программирования, то лучше попробовать реализовать собственную библиотеку BigInteger.

Answer 4

Как вы собираетесь найти сумму цифр 100 !. Если вы вычислите 100! сначала, а затем найдите сумму, тогда какая точка. Вам придется использовать некоторую интеллектуальную логику, чтобы найти ее, фактически не вычисляя 100 !. Удалите все коэффициенты из пяти, потому что они только добавят нули. Подумайте в этом направлении, вместо того, чтобы думать о большом количестве. Также я уверен, что окончательный ответ, т. Е. Сумма цифр будет в течение ДЛИННОГО ДОЛГОГО.

Существуют библиотеки C++ с большими int, но я думаю, что здесь основное внимание уделяется алгоритму, а не библиотеке.

Answer 5

Вы можете воспользоваться легкой дорогой и использовать perl/python/lisp/scheme/erlang/etc для расчета 100! используя одну из встроенных библиотек bignum или тот факт, что на некоторых языках используется точная целочисленная арифметика. Затем возьмите это число, сохраните его в строке и найдите сумму символов (с учетом «0» = 48 и т. Д.).

Или вы могли бы подумать, что в 100 !, вы получите действительно большое количество с множеством нулей. Если вы вычислите 100! итеративно, рассмотрим деление на 10 каждый раз, когда текущий факторный делится на 10. Я считаю, что это даст результат в диапазоне длинного длинного или чего-то еще.

Возможно, лучшее упражнение - написать свою собственную большую библиотеку. Вы будете нуждаться в этом для некоторых более поздних проблем, если не найдете умных трюков.

Answer 6

Используйте цифровую матрицу со стандартным методом умножения на бумаге.Например, в 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

Заметим, что умножение любого числа на или не изменяет сумму цифр.

После того, как вы узнаете, что, видно, что умножение на 2 и 5, или от 20 до 50 лет, также не изменяет сумму, так как 2x5 = 10 и 20x50 = 1000.

Затем обратите внимание, что в любое время, когда ваше текущее вычисление заканчивается на 0, вы можете просто делить на 10 и продолжать вычислять факториал.

Сделайте еще несколько замечаний о ярлыках, чтобы устранить цифры от 1 до 100, и я думаю, что вы могли бы подогнать ответ в стандартные ints.

Answer 8

Ничего в проекте Euler не требует больше __int64.

Я хотел бы предложить, пытаясь сделать это, используя базу 10000.