IT工程師數位筆記本

題目：

Description

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(1<=n<=20),計算出n個元素的集合{1,2,...,n} 可以化為多少個不同的非空子集。

Input

多組輸入數據，每組數據1行，表示元素個數n.

Output

對于每組數據，輸出一行一個數，表示不同的非空子集的個數。

Sample Input

24

Sample Output

215

用遞歸法求出第二類Stirling數，然后求和得到sum即為答案。

代碼：

#includeusing namespace std;const int l = 21;long long Stirling[l][l];long long sum[l];void getStirling(){for (int i = 0; i < l; i++){sum[i] = 0;for (int j = 0; j < l; j++)Stirling[i][j] = 0;}Stirling[0][0] = 1;for (int i = 1; i < l; i++)for (int j = 1; j <= i; j++){Stirling[i][j] = Stirling[i - 1][j - 1] + Stirling[i - 1][j] * j;sum[i] += Stirling[i][j];}}int main(){getStirling();int n;while (cin >> n)cout << sum[n] << endl;return 0;}

就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161116/54177.html

文章列表

不含病毒。www.avast.com