最优分解问题.cpp

王晓东算法设计与分析课后一些题目的源码。vc下全都编译通过。且在学校网站上提交通过。是学习算法较好的参考资料

#include<iostream>
using namespace std;
void dicomp();
long a[3000];
long result[3000]={1,0};
long c;
long k;
long n;
long len;
long m;
int main()
{
	scanf("%ld",&n);
	dicomp();
	for(len = 1;k>=0;k--)
	{
		for(c=0,m=0;m<len;m++)
		{
			long p = result[m]*a[k]+c;
			result[m] = p%10000;
			c = p/10000;
		}
		result[m] = c;
		if(c>0) len++;
	}
	if(len==1) cout << result[len-1] << endl;
	else
	{
		cout << result[len-1];
		for(len--;len>0;len--)
			printf("%04d",result[len-1]);
		cout<<endl;
	}
	system("pause");
	//return 0;
	
}
void dicomp()
{
	k = 0;
	if(n<3)
	{
		a[0] = 0;
		return ;
	}
	if(n<5)
	{
		a[k]=1;
		a[++k] = n-1;
		return ;
	}
	a[0] = 2;
	n -=2;
	while(n>a[k]){
		k++;
		a[k] = a[k-1]+1;
		n -=a[k];
	}
	if(n==a[k])
	{
		a[k]++;
		n--;
	}
	for(long i=0;i<n;i++)
		a[k-i]++;
}