set.cpp

半数集问题--动态规划算法,也是算法分析与设计的其中算法分析,用于数集问题.

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>

int ReadFile(char *filename)
{
	int data;
	ifstream input(filename, ios::nocreate);
	if(input.fail())
	{
		cerr << "error opening file input\n";
		return NULL;
	}
	input >> data;
	return data;
	input.close();
}

void WriteFile(char *filename, unsigned long x)
{
	ofstream output(filename, ios::trunc);
	if(output.fail())
	{
		cerr << "error opening file output\n";
		return;
	}
	output << x;
	output.close();
}

unsigned long set(int n)
{
	unsigned long res=0;
	unsigned long *buf;
	buf = new unsigned long [(int)n/2];

	for(int i=0; i<=n/2; i++)
	{
		buf[i] = 1;
		for(int j=1; j<=i/2; j++)
			buf[i] += buf[j];
		res += buf[i];
	}
	return res;
}

void main()
{
	int input;
	if(ReadFile("set().in.txt") == NULL)
	{
		cout << "set().in.txt不存在!" << endl;
		getchar();
		return;
	}
	input = ReadFile("set().in.txt");
	cout << "     n的值为 " << input << endl;
	if(input > 1000)
	{
		cout << "数字应在1--1000之间!(按Enter键退出)" << endl;
		getchar();
		return;
	}
	unsigned long sum;
	sum = set(input);
	cout << "其元素个数为 " << sum << endl;
	WriteFile("set().out.txt", sum);
	cout << "结果已写入set().out.txt文件!" << endl;
	cout << "(按Enter键退出!)" << endl;
	getchar();
}