整数最优分解1.cpp

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

#include <iostream.h>
#include <math.h>
void main()   
{   
		int  a[500],*p=a,i=0;   
		double t;
		int n;
		cout<<"Please input a number:";
		cin>>n;
		//如果小于5，直接输出结果
		if   (n>=0 && n<=4)   
	   	cout<<n;                        		
		else
		{   
			t=sqrt((long)n*8+17);   
			if (t==(int)t)
			{   
				i=1;n--;   
			}			  
			while(n>=4)
			{       //从后往前推出结果*  
				t=sqrt((long)n*8+9);   
				if (t==(int)t)   
					*p=(t-1)/2;   
				else   
					*p=(int)((t-1)/2)+1;   
					n-=*p;p++;   
			}   
			*p=n;   
			if (i==1)
				a[0]++;   
			for(i=p-a;i>=0;i--)
			cout<<a[i]<<" "<<endl;
			//在控制台上打印最大乘积结果
			long y=1;
			for(i=p-a;i>=0;i--)  
			y*=a[i];
	}   
  }