C++中数学库的组合函数

Question

提出了组合库链接，并尝试实现了nCr函数。如果在某个地方容易失败，请提一下。

1. 任何其他需要添加的测试代码。
2. 任何更有效的方式来编码这个。

注:我知道必须考虑到溢流处理，这是一项正在进行的工作。

码

// MathLibrary.cpp: Defines the functions for the static library.
//

#include "pch.h"
#include "framework.h"
#include <vector>
#include <iostream>


// TODO: This is an example of a library function
namespace Combinatorics
{
    const std::vector<unsigned long long> representableFactors = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,
        479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};

    unsigned long long factorial(unsigned int n) 
    {
        if (n >= representableFactors.size())
        {
            throw std::invalid_argument("Combinatorics:factorial - The argument is too large");
        }
        return representableFactors[n];
    }
    //CODE to be reviewed.
    inline unsigned long long gcd(unsigned long long a, unsigned long long b)
    {
        if (a % b == 0)
            return b;
        return gcd(b, (a % b));
    }

    unsigned long long combinations(int n, int r)
    {
        if (n - r < r)
            r = n - r;
        unsigned long long int denominatorProduct = 1, numeratorProduct = 1;
        for (int denomCount = r, numCount = n ; denomCount >= 1; denomCount--, numCount--)
        {
            denominatorProduct = denominatorProduct * denomCount;
            numeratorProduct = numeratorProduct * numCount;
            unsigned gcdCommonFactor = gcd(denominatorProduct, numeratorProduct);
            denominatorProduct /= gcdCommonFactor;
            numeratorProduct /= gcdCommonFactor;
        }
        return (numeratorProduct / denominatorProduct);
    }

}

测试代码

#include "pch.h"
#include <iostream>
#include "../MathLibrary/MathLibrary.cpp"

TEST(Combinatorial_Factorial, small_ints)
{
    EXPECT_EQ(Combinatorics::factorial(0), 1);
    EXPECT_EQ(Combinatorics::factorial(1), 1);
    EXPECT_EQ(Combinatorics::factorial(5), 120);
    EXPECT_EQ(Combinatorics::factorial(20), 2432902008176640000);
}

TEST(Combinatorial_Factorial, too_big)
{
    EXPECT_THROW(Combinatorics::factorial(500), std::invalid_argument);
}

TEST(Combinatorial_Combinations, small_ints)
{
    EXPECT_EQ(Combinatorics::combinations(5,5), 1);
    EXPECT_EQ(Combinatorics::combinations(5, 0), 1);
    EXPECT_EQ(Combinatorics::combinations(5, 1), 5);
    EXPECT_EQ(Combinatorics::combinations(20,10),184756);
    EXPECT_EQ(Combinatorics::combinations(40, 35),658008);
}

Answer 1

我将忽略阶乘代码，因为在前面的问题中已经对此进行了回顾。

在combinations()中，如果r>n会发生什么？如果这两种输入都是负值呢？测试集中既没有出现大小写，也没有在函数中进行测试。带负号整数的无符号算术会导致溢出和…头痛。

在……里面

if (n - r < r)
    r = n - r;

你应该更喜欢用牙套。我认为它们增加了可读性。还有一个著名的故事介绍了一个错误，因为缺少大括号:很容易添加一行代码，并认为它在条件内，而不是。我不知道这有多真实，但GCC补充了一个警告，当缩进是误导性的，大概是为了在传说中解决这种情况。

在此：

unsigned long long int denominatorProduct = 1, numeratorProduct = 1;

我更喜欢两行，每行一条声明。再次提高可读性。

您可以考虑在库中声明要使用的一些整数类型，避免重复使用unsigned long long int等。不仅使类型名称更短，而且还增加了一些灵活性和一致性。

而不是

denominatorProduct = denominatorProduct * denomCount;

写：

denominatorProduct *= denomCount;

这个更容易读懂。在后面的除法中，您确实使用了这个符号。尽量与你的语法一致！