Отдел очень больших чисел

Я написал следующий код на C ++:

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
double sum, containers, n ,c, max_cap, temp;

unsigned int j = 1;
cin >> n >> c;
sum = containers = n;for (unsigned int i = 2 ; i <= c; ++i)
{
max_cap = i * n;

if (max_cap - sum > 0)
{
temp = ceil((max_cap - sum)/i);
containers += temp;
sum += i * temp;
}
}

cout << containers << '\n';
}

Если для этого кода введено «728 1287644555», то для расчета ответа потребуется около 5 секунд, но когда ввод примерно три раза, т. Е. «763 3560664427», это не дает длительного времени (я ждал около получаса). Как видно, алгоритм имеет линейный порядок. Следовательно, это займет примерно 15 секунд. Почему это происходит? Это потому, что во втором случае вход слишком велик? Если да, то как это так сильно влияет на время?

1

Решение

Мое предположение было бы переполнением целого числа без знака.

       for (unsigned int i = 2 ; i <= c; ++i)

i увеличивается, пока не станет> c, но c двойной, тогда как i является неподписанным Int. Достигает максимума (UINT_MAX) и обнуляется до того, как достигнет значения c,

То есть 1287644555 меньше чем UINT_MAXтак что это завершает. Но 3560664427 больше, чем UINT_MAX, так что это петли навсегда. Что только поднимает вопрос о том, на какой странной архитектуре вы это используете 🙂

На моей собственной машине (UINT_MAX = 4294967295) первый ввод обрабатывается за 16 секунд, а второй — за 43,5 секунды, что вполне ожидаемо.

1

Другие решения