1

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

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

谢谢

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

4 回答 4

3

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

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

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

在i==21：

f[20]已经等于2432902008176640000

21 * 2432902008176640000对于 64 位签名溢出，通常会变成-4249290049419214848 所以此时，您的程序出现错误并且现在处于未定义行为。

在i==66

f[65]等于0x8000000000000000。66 * f[65]由于对我有意义的原因，因此被计算为零，但应理解为未定义的行为。

f[66]赋值为 0 后，所有后续赋值也变为f[i]0。里面的主循环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;
}
于 2016-03-12T08:44:17.713 回答
2

您没有使用浮点数。而且您似乎正在使用可变大小的数组，这是 C 功能，可能是 C++ 扩展，但不是标准的。

无论如何，即使对于相当小的 n 值，您也会得到溢出和未定义的行为。

在实践中，溢出将导致数组元素在 n 值不大的情况下变为零。

然后，您的代码将除以零并崩溃。

他们也可能有一个像 (1000000000, 999999999) 这样的测试用例，这很容易解决，但我打赌你的代码会崩溃。

于 2016-03-12T08:21:04.997 回答
0

数组语法为：

type name[size]

注意：大小必须是常量而不是变量

示例 #1：

int name[10];

示例 #2：

const int asize = 10;
int name[asize];
于 2016-03-12T08:15:55.143 回答
0

您没有指定“浮点错误”的含义-我认为您指的是您正在执行整数除法而不是浮点除法，因此您将始终获得整数而不是浮点数。

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？

于 2016-03-12T08:24:56.170 回答