6

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

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

#include "stdafx.h"
#include <iostream>
#include <string>
#include <Windows.h>
#include <cstdlib>
#include <sstream>
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;
}
3
  • если нужна сумма цифр факториала, то в цикле пропускайте все нули( не нужно умножать на 10 или 20... if ( !(i % 10) ) a *= i / 10; И вместо 48 все таки нужен символ '0' 6 дек 2018 в 21:18
  • 1
    @ARHovsepyan не очень понятно зачем это. От потери точности double это никак не спасёт
    – IR42
    6 дек 2018 в 21:28
  • @Beaver Feller, не спасет(я не обратил внимание на использованный тип) и не спасет от неэффективности, но может быть полезным замечанием... 6 дек 2018 в 21:36

3 ответа 3

4

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

  • Реализовывать длинное число в виде массива десятичных цифр, что сделает вычисление финальной суммы тривиальной операцией, но существенно удлинит и замедлит процесс длинного умножения.

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

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

#include <cstdint>
#include <vector>
#include <algorithm>
#include <iostream>

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

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 <cstdint>
#include <vector>
#include <iostream>

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

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
  • Практика показала, что для длинной целочисленной арифметики оптимально использовать 100-ричную систему счисления. 7 дек 2018 в 5:24
  • @Герман Борисов: Идея разумная, но при чем здесь именно 100-ричная система - не ясно. Здравый смысл говорит, что надо использовать систему с максимальным основанием 10^N и ограничениями в точности как я привел выше, т.е. с сохранением возможности перемножить две цифры без переполнения на данной платформе. Т.е. фактически 1000000000. 7 дек 2018 в 5:33
  • Не могли бы вы объяснить мне данный кусок кода? Что здесь происходит? Вы определяете собственные пространства имен? using TDigit = std::uint32_t; using TDigit2 = std::uint64_t; const TDigit2 BASE = 1000000000u; using TNumber = std::vector<TDigit>; @AnT 9 дек 2018 в 9:30
1

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

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

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

void mul(vector<int>& 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<int> 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;
}
0
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;

Так проще___

4
  • но ведь 100! имеет 158 цифр... и отбрасывание нулей не поможет от переполнения
    – IR42
    6 дек 2018 в 22:07
  • пробовал long long, происходит переполнение 6 дек 2018 в 22:26
  • В числе 100! всего 24 нуля справа и 134 значащих разряда 7 дек 2018 в 5:27
  • @Олег Данилов, прошу прощения, для 100! не подходит, я внесу поправки 7 дек 2018 в 15:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.