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

Question

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

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

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

Answer 1

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

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

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

Answer 3

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

Арифметика произвольной точности - это то, что вы ищете. Проверьте псевдокод, указанный на вики-странице.

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

Answer 4

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

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

Answer 5

Обратите внимание, что умножение любого числа на 10 или 100 не меняет сумму цифр.

Как только вы это узнаете, посмотрите, что умножение на 2 и5, или на 20 и 50, также не меняет сумму, так как 2x5 = 10 и 20x50 = 1000 .

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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