sigfpe — ошибка с плавающей точкой в коде C ++
Я пытаюсь решить вопрос, в котором мне нужно выяснить количество возможных способов создать команду из двух человек (примечание: в команде может быть не более двух человек).
После создания этого кода он работает правильно, но в некоторых тестовых случаях он показывает ошибку с плавающей запятой, и я не могу выяснить, что именно.
Ввод: 1-я строка: количество тестов
2-я строка: номер всего человека
Спасибо
#include<iostream>
using namespace std;
long C(long n, long r)
{
long f[n + 1];
f[0] = 1;
for (long i = 1; i <= n; i++)
{
f[i] = i * f[i - 1];
}
return f[n] / f[r] / f[n - r];
}
int main()
{
long n, r, m,t;
cin>>t;
while(t--)
{
cin>>n;
r=1;
cout<<C(n, min(r, n - r))+1<<endl;
}
return 0;
}
Решение
Вы не получаете исключение с плавающей запятой. Вы получаете деление на ноль исключений. Потому что ваш код пытается разделить на число 0 (что нельзя сделать на компьютере).
Когда вы вызываете C(100, 1) основной цикл, который инициализирует f массив внутри C увеличивается в геометрической прогрессии. В конце концов, два значения умножаются так, что i * f[i-1] ноль из-за переполнения. Это приводит к тому, что все последующие значения f [i] инициализируются нулями. И тогда деление, которое следует за циклом, является делением на ноль.
Хотя пуристы на этих форумах скажут, что это не определено, вот что на самом деле происходит на большинстве двух дополнительных архитектур. Или, по крайней мере, на моем компьютере ….
В i==21:
f[20] уже равен 2432902008176640000
21 * 2432902008176640000 переполнения для 64-битной подписи и обычно становятся -4249290049419214848 Итак, на данный момент ваша программа прослушивается и теперь находится в неопределенное поведение.
В i==66
f[65] равно 0x8000000000000000, Так 66 * f[65] вычисляется как ноль по причинам, которые имеют смысл для меня, но должны пониматься как неопределенное поведение.
С f[66] присваивается 0, все последующие присвоения f[i] стать нулевым, а также. После основной петли внутри C закончилась, f[n-r] это ноль. Следовательно, делим на ноль ошибок.
Обновить
Я вернулся и реверс-инжиниринг вашей проблемы. Похоже твой C Функция просто пытается вычислить это выражение:
N!
-------------
R! * (N-R)!
Что является «количеством уникальных отсортированных комбинаций»
В этом случае вместо вычисления большого факториала N !, мы можем уменьшить это выражение до следующего:
n
[ ∏ i ]
n-r
--------------------
R!
Это не устранит переполнение, но позволит вашему C функция, чтобы иметь возможность принимать большие значения N и R для вычисления количества комбинаций без ошибок.
Но мы также можем воспользоваться преимуществами простого сокращения, прежде чем пытаться сделать большое длинное факториальное выражение.
Например, скажем, мы пытались вычислить C (15,5). Математически это:
15!
--------
10! 5!
Или, как мы выразились выше:
1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
-----------------------------------
1*2*3*4*5*6*7*8*9*10 * 1*2*3*4*5
Первые 10 факторов числителя и знаменателя взаимно уничтожаются:
11*12*13*14*15
-----------------------------------
1*2*3*4*5
Но интуитивно вы можете видеть, что «12» в числителе уже делится равномерно на знаменатели 2 и 3. И что 15 в числителе делится на 5 в знаменателе. Так что простое сокращение может быть применено:
11*2*13*14*3
-----------------------------------
1 * 4
Еще больше возможностей для уменьшения общего делителя, но это отличное начало.
Давайте начнем с вспомогательной функции, которая вычисляет произведение всех значений в списке.
long long multiply_vector(std::vector<int>& values)
{
long long result = 1;
for (long i : values)
{
result = result * i;
if (result < 0)
{
std::cout << "ERROR - multiply_range hit overflow" << std::endl;
return 0;
}
}
return result;
}
Не будем реализовывать C как с использованием вышеуказанной функции после выполнения операции сокращения
long long C(int n, int r)
{
if ((r >= n) || (n < 0) || (r < 0))
{
std::cout << "invalid parameters passed to C" << std::endl;
return 0;
}
// compute
// n!
// -------------
// r! * (n-r)!
//
// assume (r < n)
// Which maps to
// n
// [∏ i]
// n - r
// --------------------
// R!int end = n;
int start = n - r + 1;
std::vector<int> numerators;
std::vector<int> denominators;
long long numerator = 1;
long long denominator = 1;
for (int i = start; i <= end; i++)
{
numerators.push_back(i);
}
for (int i = 2; i <= r; i++)
{
denominators.push_back(i);
}
size_t n_length = numerators.size();
size_t d_length = denominators.size();
for (size_t n = 0; n < n_length; n++)
{
int nval = numerators[n];
for (size_t d = 0; d < d_length; d++)
{
int dval = denominators[d];
if ((nval % dval) == 0)
{
denominators[d] = 1;
numerators[n] = nval / dval;
}
}
}
numerator = multiply_vector(numerators);
denominator = multiply_vector(denominators);
if ((numerator == 0) || (denominator == 0))
{
std::cout << "Giving up. Can't resolve overflow" << std::endl;
return 0;
}
long long result = numerator / denominator;
return result;
}
Другие решения
Вы не используете с плавающей точкой. И вы, похоже, используете массивы переменного размера, которые являются функцией C и, возможно, расширением C ++, но не стандартным.
В любом случае, вы получите переполнение и, следовательно, неопределенное поведение даже для довольно небольших значений n.
На практике переполнение приведет к тому, что элементы массива станут равными нулю при не намного больших значениях n.
Ваш код будет делиться на ноль и сбой.
У них также может быть контрольный пример, подобный (1000000000, 999999999), который тривиально решить, но не для вашего кода, который, я уверен, вылетит.
Вы не указываете, что вы подразумеваете под «ошибкой с плавающей точкой» — я считаю, что вы имеете в виду тот факт, что вы делаете целочисленное деление, а не деление с плавающей точкой, так что вы всегда будете получать целые числа, а не числа с плавающей запятой.
int a, b;
a = 7;
b = 2;
std::cout << a / b << std::endl;
это приведет к 3, а не 3,5! Если вы хотите получить результат с плавающей запятой, вы должны использовать плавающие вместо этого:
float a, b;
a = 7;
b = 2;
std::cout << a / b << std::end;
Таким образом, решение вашей проблемы будет просто использовать float вместо long long int,
Также обратите внимание, что вы используете массивы переменного размера, которые не будут работать в C ++ — почему бы не использовать std::vector вместо??
Синтаксис массива как:
type name[size]
Примечание: размер должен быть константой, а не переменной
Пример № 1:
int name[10];
Пример № 2:
const int asize = 10;
int name[asize];