Сумма цифр числа 100!

#cpp #алгоритм #математика

Написал код для подсчета суммы цифр в числе 100! для решения задачи на Проекте Эйлера.
До этого успешно использовал кусок кода, который непосредственно подсчитывает сумму
цифр, для решения аналогичной задачи с числом 2 в 1000 степени. Однако в случае с 100!
результат неправильный. В чем проблема?

// Study86.cpp: определяет точку входа для консольного приложения.
// Сумма разрядов в 100!

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
using namespace std;
long int sum = 0;

int main()
{
    setlocale(LC_CTYPE, "rus");
    long double a = 1;
    int n;
    cout << "Введите значение для вычисления факториала: ";
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        a = a * i;
    }
    cout << "Результат: " << a << endl;
    string str = to_string(a);
    cout << "Результат, записанный в строку: " << str << endl;
    cout << "Длина данного числа: " << str.length() << endl;
    for (int j = 0; j < str.length(); j++)
    {
        if ((str[j] != 48) && (str[j]!=46))
        {
            sum = sum + (str[j] - 48);
            cout << j + 1 << "-я цифра" << endl;
            cout << (int)str[j] - 48 << endl;
            cout << "Сумма равна: " << sum << endl << endl;
        }
    }
    cout << "Сумма цифр числа: " << sum << endl;
    system("pause");
    return 0;
}

    

Ответы

Ответ 1

Проблема кроется в потере точности при работе с числами с плавающей точкой. Нужно
использовать библиотеку для больших числе (для C++ только сторонние библиотеки). Для
данной задачи достаточно реализовать функцию умножения.
Такой же вопрос и ответ. По ссылке решение на Си.

Немного изменённая под С++ версия:

#include 
#include 
#include 
using namespace std;

void mul(vector& v, int k) {
    int r = 0;
    for (int i = 0; i < v.size(); i++) {
        int num = v[i];
        num *= k;
        num += r;
        v[i] = num % 10;
        r = num / 10;
    }
    while (r != 0) {
        v.push_back(r % 10);
        r /= 10;
    }
}

int main()
{
    vector v;
    v.push_back(1);
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        mul(v, i);
    }
    cout << accumulate(v.begin(), v.end(), 0);
    return 0;
}


Ответ 2

Задачу по-видимому придется решать в лоб, т.е. через длинную арифметику. Если все
делать "руками", то это сразу приводит к дилемме: 


Реализовывать длинное число в виде массива десятичных цифр, что сделает вычисление
финальной суммы тривиальной операцией, но существенно удлинит и замедлит процесс длинного
умножения.
Реализовывать длинное число в виде массива цифр в системе счисления с основанием
2n/2, где n - это ширина самого широкого умножения, поддерживаемого данной С++ платформой.
Это ускорит длинное умножение, но потребует реализации длинного деления на 10 для того,
чтобы получить цифры для сложения в финале.


Меня больше привлекает именно второй вариант. Например, (не гоняясь за процессорными
тактами в операциях умножения и деления)

#include 
#include 
#include 
#include 

using TDigit = std::uint32_t;
using TDigit2 = std::uint64_t;
const std::size_t BITS = std::numeric_limits::digits;
const TDigit2 BASE = (TDigit2) 1 << BITS;
using TNumber = std::vector;

void mul(TNumber &v, TDigit m)
{
  if (m == 1)
    return;

  TDigit carry = 0;

  for (TDigit &digit : v)
  {
    TDigit2 product = (TDigit2) digit * m + carry;
    digit = product % BASE;
    carry = (TDigit) (product / BASE);
  }

  if (carry > 0)
    v.push_back(carry);
}

unsigned div10(TNumber &v)
{
  TDigit r = 0;

  for (std::size_t n = v.size(); n > 0; --n)
  {
    TDigit2 dd = (TDigit2) r * BASE + v.back();
    std::copy_backward(v.begin(), v.end() - 1, v.end());
    v.front() = (TDigit) (dd / 10);
    r = dd % 10;
  }

  while (!v.empty() && v.back() == 0)
    v.pop_back();

  return r;
}

unsigned factorial_sum(unsigned n)
{
  TNumber v = { 1 };

  for (unsigned i = 1; i <= n; ++i)
  {
    unsigned m = i;
    for (; m % 10 == 0; m /= 10);
    mul(v, m);
  }

  unsigned sum = 0;
  for (; !v.empty(); sum += div10(v));

  return sum;
}

int main() 
{
  std::cout << "100! -> " << factorial_sum(100) << std::endl;
  std::cout << "1000! -> " << factorial_sum(1000) << std::endl;
}


http://coliru.stacked-crooked.com/a/69d4651879a8fad5



Пользуясь идей, предложенной @Германом Борисовым в комментариях, можно получить эффективный
компромисс между этими двумя подходами: используем систему счисления с основанием 10n,
где n выбирается максимально возможным так, чтобы перемножение двух цифр не приводило
к переполнению на данной С++ платформе.

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

#include 
#include 
#include 

using TDigit = std::uint32_t;
using TDigit2 = std::uint64_t;
const TDigit2 BASE = 1000000000u;
using TNumber = std::vector;

void mul(TNumber &v, TDigit m)
{
  if (m == 1)
    return;

  TDigit carry = 0;

  for (TDigit &digit : v)
  {
    TDigit2 product = (TDigit2) digit * m + carry;
    digit = product % BASE;
    carry = (TDigit) (product / BASE);
  }

  for (; carry > 0; carry /= BASE)
    v.push_back(carry % BASE);
}

unsigned factorial_sum(unsigned n)
{
  TNumber v = { 1 };

  for (unsigned i = 1; i <= n; ++i)
  {
    unsigned m = i;
    for (; m % 10 == 0; m /= 10);
    mul(v, m);
  }

  unsigned sum = 0;
  for (TDigit d : v)
    for (; d > 0; d /= 10)
      sum += d % 10;

  return sum;
}

int main() 
{
  std::cout << "100! -> " << factorial_sum(100) << std::endl;
  std::cout << "1000! -> " << factorial_sum(1000) << std::endl;
}


http://coliru.stacked-crooked.com/a/68096eb9ebbb061f



Эксперимент на QuickBench показывает, что это - существенно более эффективный подход

http://quick-bench.com/G-XjO_3VniIvFLX2RWI3cuQLNTM

Разумеется, первый вариант не настолько эффективен, насколько он мог бы быть - из-за
неэффективной реализации операции деления. Однако цели оптимизации и не ставилось.
Все варианты работают за более чем приемлемое время.


Ответ 3

long long fct = 1;
unsigned n, sum{0};
cin >> n;
for (int i = 2; i <= n; i++)
{
    fct *= i;
    if (!(fct % 10))
        fct /= 10;
}
cout << fct << endl;
while (fct)
{
    sum += (fct%10);
    fct /= 10;
}
cout << sum;


Так проще___