分治算法实践1-集合划分 c++

分治算法实践1-集合划分 c++ 题目描述

n个元素的集合{1,2,…, n }可以划分为若干个非空子集。
给定正整数n，计算出n 个元素的集合{1,2,…, n }可以划分为多少个不同的非空子集。
例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：

{{1}，{2}，{3}，{4}}{{1，2}，{3}，{4}}{{1，3}，{2}，{4}}{{1，4}，{2}，{3}}{{2，3}，{1}，{4}}{{2，4}，{1}，{3}}{{3，4}，{1}，{2}}{{1，2}，{3，4}}{{1，3}，{2，4}}{{1，4}，{2，3}}{{1，2，3}，{4}}{{1，2，4}，{3}}{{1，2，4}，{3}}{{1，2，4}，{3}}{{1，2，4}，{3}}

（注：表格无任何特殊含义，只为展示得更清晰）

输入数据

多组输入(<=10组数据，读入以EOF结尾) 每组一行输入一个数字，n(0 输出数据

每组输出一行结果

样例输入

4

样例输出

15

分析

这是一个对于有n个元素的集合，要将其划分成k个子集，求划分方案的个数的算法。

• 这里是参考的： CSDN博文-集合的划分

代码

#include  //集合划分
using namespace std;
#define LL long long

LL fun(int n, int k) //n个元素 分成k个子集 返回划分方案的个数
{
    if (k == 1 || n == k)
        return 1; //只有一种划分方法
    else
        return fun(n - 1, k - 1) + k * fun(n - 1, k); //递归公式
}

int main()
{
    int n;
    LL re;
    while (cin >> n)
    {
        re = 0;
        for (int i = 1; i <= n; i++) //从 1-n 划分
            re += fun(n, i);
        cout << re << endl;
    }
    system("pause");
    return 0;
}

小结

• 对于以"EOF”结尾的输入： c++中的cin，c中的scanf可自动判断，直接放到while里即可。
• 若文章存在问题，还请各位大佬批评指正，共同进步。