subsetcalculator.cpp

本算法实现2-10集合划分问题,采用动态规划法和大整数方法

/************************************************************
 **
 ** 标题：subsetcalculator.cpp
 **
 ** 功能：计算集合的不同划分方法数
 **
 ** 备注：采用动态规划法，没有考虑数据溢出的问题
 **
 ************************************************************/

#include <stdio.h>
#include "bigint.h"

#define	INPUT_FILE_NAME		"input.txt"		// 输入文件名
#define OUTPUT_FILE_NAME	"output.txt"	// 输出文件名

/**
 * 入口函数
 */
int main( int argc, char** argv )
{
	// 变量定义
	int i;
	BigInteger* ptr;
	FILE*		input		= NULL;	// 输入流
	FILE*		output		= NULL;	// 输出流
	bool		bError		= false;// 错误标号
	int			nSetLen		= 0;	// 待分析的集合长度
	BigInteger		dSubsetNum;		// 非空子集数
	BigInteger**	dArray	= 0;	// 缓存数组(第[i-1][j-1]个元素表示长度为i的集合划分为j块的划分方法数)

	// 打开输入文件
	if( (input=fopen(INPUT_FILE_NAME, "r")) == NULL )
	{
		printf( "打开文件 %s 失败！\n", INPUT_FILE_NAME );
		bError = true;
		goto QUIT;
	}
	
	// 读取集合的长度
	if( fscanf(input, "%d", &nSetLen) != 1 )
	{
		printf( "输入文件格式错误！\n" );
		bError = true;
		goto QUIT;
	}

	// 打印输入数据
	printf( "待分析的集合长度为： %d\n", nSetLen );

	// 构建缓存数组
	dArray = new BigInteger*[nSetLen];
	for(i = 0; i < nSetLen; i++ )
	{
		dArray[i] = new BigInteger[nSetLen];
		// 第一列置1,划分为一块的方法只有一种
		dArray[i][0].GetNum( "+1" );
	}

	// 利用缓存数组,计算所有的划分情况
	for(  i = 1; i < nSetLen; i++ )
	{
		for( int j = 1; j <= i; j++ )
		{
			dArray[i][j] = dArray[i-1][j] * (j+1) + dArray[i-1][j-1];
		}
	}

	// 计算最末行的划分数之和,即所求的划分数
	ptr = dArray[nSetLen-1];
	for( i = 0; i < nSetLen; i++ )
		dSubsetNum = dSubsetNum + ptr[i];

	// 打印分析结果
	printf( "长度为%d的集合的非空子集共有", nSetLen );
	dSubsetNum.Print();
	printf( "个\n" );

	// 打开输出文件
	if( (output=fopen(OUTPUT_FILE_NAME, "w")) == NULL )
	{
		printf( "打开文件 %s 失败！\n", OUTPUT_FILE_NAME );
		bError = true;
		goto QUIT;
	}

	// 将结果写入输出文件
	dSubsetNum.Print( output );

	// 退出
QUIT:
	if( input )
		fclose( input );
	if( output )
		fclose( output );
	if( dArray )
	{
		for( int i = 0; i < nSetLen; i++ )
			delete [] dArray[i];
		delete [] dArray;
	}
	return bError ? (-1):0;
}