1543.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 101
//int a[NMAX][NMAX][NMAX];
int c[NMAX];
//int f[3*NMAX*NMAX*NMAX]={0};
typedef struct
{
	int a,b,c,d;
}data;
data q[NMAX*NMAX];
int n;
int cmp(const void *a,const void *b)
{
	int ta=((data*)a)->a-((data*)b)->a;
	int tb=((data*)a)->b-((data*)b)->b;
	int tc=((data*)a)->c-((data*)b)->c;
	int td=((data*)a)->d-((data*)b)->d;
	if(ta)
		return ta;
	if(tb)
		return tb;
	if(tc)
		return tc;
	return td;
	
		
}
void init()
{
	int i,j,k;
	for(i=2;i<=n;i++)
	{
		c[i]=i*i*i;
//		f[c[i]]=i;
	}
	int p=0;
	int m;
	for(i=2;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				int t=c[i]+c[j]+c[k];
				for(m=k+1;m<=n;m++)
				{
					if(m*m*m==t)
					{
						q[p].a=m;
						q[p].b=i;
						q[p].c=j;
						q[p].d=k;
						p++;
					}
					else if(m*m*m>t)
						break;
				}
			}
	qsort(q,p,sizeof(data),cmp);
	for(i=0;i<p;i++)
	{
		printf("Cube = %d, Triple = (%d,%d,%d)\n",q[i].a,q[i].b,q[i].c,q[i].d);
	}

		

}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d",&n);
	init();
	
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}