c++ 第二类Stirling数

Question

第二类Stirling数

描述

n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案用S（n,m）表示，称为第二类Stirling数。

用例输入 1

7 4
用例输出 1

350

Answer 1

引自免费微信小程序：皆我百晓生

要计算第二类Stirling数 S(n, m)，可以使用递归公式：

[ S(n, m) = m \cdot S(n-1, m) + S(n-1, m-1) ]

其中的基础情况是:

[ S(n, 1) = 1 ] [ S(0, m) = 0 ] [ S(n, 0) = 0 ] (当m为0时，没有盒子，所以没有合法的分配方式)

下面是一个C++函数实现，用于计算并返回S(n, m)值：

#include <iostream>
using namespace std;

unsigned long long stirling_number_of_the_second_kind(int n, int m) {
    // 基础情况
    if (n == 0 || m == 0) return 0;
    if (n == m) return 1;

    // 递归公式
    unsigned long long result = m * stirling_number_of_the_second_kind(n - 1, m);
    result += stirling_number_of_the_second_kind(n - 1, m - 1);

    return result;
}

int main() {
    int n = 7, m = 4;
    cout << "S(" << n << ", " << m << ") = " << stirling_number_of_the_second_kind(n, m) << endl;
    return 0;
}

在这个代码示例中，我们定义了一个名为stirling_number_of_the_second_kind的函数，它接受两个整数参数n和m，并返回它们之间的第二类Stirling数。在主函数main中，我们设置了例子中的n和m值，然后调用了这个函数并打印结果。

运行这段代码，将得到输出 S(7, 4) = 350，这与您提供的用例相符。注意，由于这些数字可能非常大，所以这里使用了unsigned long long类型来存储结果。