集合划分.cpp

王晓东算法设计与分析源码。vc下编译通过能够运行。且运行效率较高

#include<iostream>
using namespace std;
__int64 S[100][100] = {0};
void StirlingNumber(int m,int n);
__int64 computeB(int m);
int main()
{
	int m;
	__int64 result;
	scanf("%d",&m);
	result  = computeB(m);
	printf("%I64d\n",result);
	//return 0;
	system("pause");
}
void StirlingNumber(int m,int n)
{
	int min;
	S[0][0] = 1;
	for(int i=1;i<=m;i++) S[i][0] = 0;
	for(int i=0;i<m;i++) S[i][i+1] = 0;
	for(int i=1;i<=m;i++){
		if(i<n) 
			min = i;
		else
			min = n;
		for(int j=1;j<=min;j++)
			S[i][j] = j*S[i-1][j]+S[i-1][j-1];
	}
}
__int64 computeB(int m)
{
	StirlingNumber(m,m);
	__int64 *B = new __int64[m];
	for(int i = 0;i<m;i++)
		B[i] = 0;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=i;j++)
			B[i-1]+=S[i][j];
	}
	return B[m-1];
}