整数最优分解.cpp

贪心算法解一系列算法经典问题

#include <iostream.h>

int a[100];
int dicomp(int n)
{
   int k=1;
   if(n<3) {
	   a[1]=0; 
	   return k;
   }
   if(n<5){
	   a[k]=1;
	   a[++k]=n-1;
	   return k;
   }
   a[1]=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(int i=0;i<n;i++)a[k-i]++;
	return k;
}

void main()
{
	int n,k,m=1;
	cout<<"Please input a number:";
	cin>>n;
	k=dicomp(n);
	cout<<"The numbers are:"<<endl;
	for(int i=1;i<=k;i++){
		cout<<a[i]<<"    ";
		m=m*a[i];
	}
	cout<<"\nThe result is: "<<m<<endl;
}