intfactorization.cpp

最优分解：将正整数n分解为若干互不相同的自然数的和

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

int Factorizate(int n,int *a)
{
	int intMaxProduct=1;
	int intOverplus=n;
	
	int i=2;//加数数组的下标

	if (n==1) return 1;//当n为1~4时，最大乘积就是他们自己
	if (n==2) return 2;
	if (n==3) return 3;
	if (n==4) return 4;
	
	while(intOverplus>=i)//找出最大加数下标
	{		
		intOverplus-=i;		
		i++;
	}

	int m=i-1;//保存最大加数下标
	
	for (int j=0;j<=m;j++) a[j]=j;//初始化加数数组

	for (i-=1;i>=2;i--)//微调加数数组，使其和为n
	{
		if(intOverplus<=0) break;
		a[i]++;
		intOverplus--;
		
	}
	if(intOverplus>0) a[m]++;

	for (j=2;j<=m;j++)//求出最大乘积,并输出加数数组
	{
		intMaxProduct*=a[j];
		cout<<a[j]<<"\t";
		//fprintf(outFile, "%d\t", a[j]); 
	}
	cout<<endl;
	//fprintf(outFile, "\n"); 
	return intMaxProduct; 
}

void main()
{
	int n;   
	//int n=10;
	FILE *inFile;  //从txt获得正整数n   
    inFile= fopen("input.txt","r"); 
    fscanf(inFile,"%d",&n);   
    fclose(inFile);    

	int intMaxProduct;
	int m=(int)(sqrt(2*n)+1);//数组长度
	int *a=new int[m+1];//加数数组

	intMaxProduct=Factorizate(n,a);
	cout<<"最大乘积为"<<intMaxProduct<<endl;
	
	FILE *outFile;   //输出最大乘积
    outFile = fopen("output.txt", "w");  
	fprintf(outFile, "%d\n", intMaxProduct); 
	fclose(outFile);
}