时间限制 1000 ms 内存限制 64 MB
题目描述
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，3，4}，{2}}， {{2，3，4}，{1}}， {{1，2，3，4}} 给定正整数n，计算出n 个元素的集合{1,2,…, n }可以划分为多少个不同的非空子集。
输入数据
多组输入(<=10组数据，读入以EOF结尾) 每组一行输入一个数字，n(0<n<=18)
输出数据
每组输出一行结果。
样例输入
4
样例输出
15
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cmath> long long fun(int m, int n) { if (m == 1) return 1; if (m == n) return 1; else return fun(m - 1, n - 1) + fun(m, n - 1) * m; } int main() { int n; while (scanf("%d", &n) != EOF) { long long ans = 0; //ans = fun(1, n); for (int i = 1; i <= n; i++) { //printf("%lld--before\n", ans); ans += fun(i, n); //printf("%lld\n", ans); } //long long ans = pow(2, n) - 1; printf("%lld\n", ans); } return 0; }