integer_split.cpp

整数划分算法实现源码 整数划分算法实现源码

// 思路：把n从2开始分解，依次增加1，
//如果最后分解的数count小于前一个数，那么就分解成count个1 累加到前面的数
#include <iostream.h>
#include <fstream.h>
#define MSplitX 100
int Integer_split ( int n)
{
	int Split[MSplitX];
	int count=1;
	int result=1;
	
	if ( n<3)
	{
		Split[1]=0;
		return n;
	}
	Split[1]=2;
	n-=2;

	while ( n> Split[count])
	{
		count++;
		Split[count] = Split[count-1]+1;
		n-= Split[count];
	}

     if ( n==Split[count])
     {
		 Split[count]++;
		 n--;
     }
	 for ( int i=0 ; i<n  ; i++ )
	 {
		 Split[count-i]++;
	 }
	 
	 for (int j=1; j<=count ; j++ )
	 {
		 result*=Split[j];
	 }
	 return result;
}
void main(int argc, char *argv[])
{
	int sum=0;
	int num=0;
	fstream fs;
	fs.open("input.txt",ios::in);
	fs>>num;
	sum=Integer_split ( num );
    cout<<sum<<endl;
	ofstream ss("output.txt");
	ss<<sum<<endl;

}