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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

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