C++代码中的浮点错误

Question

我正在尝试解决一个问题，在这个问题中我需要找出组成两个成员的团队的可能方法的数量。（注意：一个团队最多可以有两个人）编写此代码后，它可以正常工作，但在某些测试用例中它显示浮点错误广告我无法找出它到底是什么。

输入：第一行：测试用例数第二行：总人数

谢谢

#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;
}

Answer 1

数组语法为：

type name[size]

注意：size 必须是常量而不是变量

示例 #1：

int name[10];

示例 #2：

const int asize = 10;
int name[asize];

Answer 2

您没有使用浮点数。你似乎在使用可变大小的数组，这是一个 C 特性，可能是一个 C++ 扩展，但不是标准的。

无论如何，即使对于相当小的 n 值，您也会出现溢出并因此出现未定义的行为。

在实践中，溢出将导致数组元素变为零，因为 n 的值不会太大。

您的代码将被零除并崩溃。

他们也可能有一个像 (1000000000, 999999999) 这样的测试用例，解决起来很简单，但我敢打赌它会崩溃。

Answer 3

您没有说明 "floating point error" 是什么意思 - 我认为您指的是这样一个事实，即您正在进行整数除法而不是浮点数除法，这样您将始终得到整数而不是浮动。

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？

Answer 4

您没有收到浮点异常。您得到除以零的异常。因为您的代码试图除以数字 0（这不能在计算机上完成）。

当您调用 C(100, 1) 时，初始化 C 内的 f 数组的主循环呈指数增长。最终，两个值相乘，使得 i * f[i-1] 由于溢出而为零。这导致所有后续的 f[i] 值都被初始化为零。然后循环后面的除法是除以零。

尽管这些论坛上的纯粹主义者会说这是未定义的，但这是大多数 2 的补码架构上真正发生的事情。或者至少在我的电脑上....

在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)!

哪个是"number of unique sorted combinations"

在这种情况下，我们可以将该表达式简化为：

，而不是计算 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++代码中的浮点错误

Floating point error in C++ code

c++

sigfpe