多边形.cpp

在学习计算算法分析与设计时编写的几个算法代码

#include"stdio.h"
void min_max(int n,int i,int s ,int j, int *minf,int *maxf,int m[][5][2],char op[])
{
	int e[4],a,b,r,c,d;
	a=m[i][s][0];
	b=m[i][s][1];
	r=(i+s-1)%n+1;
	c=m[r][j-s][0];
	d=m[r][j-s][1];
	if(op[r]=='t')
	{
		*minf=a+c;
		*maxf=b+d;
	}
	else
	{
		e[0]=a*c;
		e[1]=a*d;
		e[2]=b*c;
		e[3]=b*d;
		*minf=e[0];
		*maxf=e[0];
		for(r=1;r<4;r++)
		{
			if(*minf>e[r])*minf=e[r];
			if(*maxf<e[r])*maxf=e[r];
		}
	}
}
int poly_max(int n,int m[][5][2],char op[])
{
	int minf,maxf,j,i,s,temp,k;
	int b[4]={0};
	k=0;
	minf=maxf=0;
	for(j=2;j<=n;j++)
		for(i=1;i<=n;i++)
			for(s=1;s<j;s++)
			{
				min_max(n,i,s,j,&minf,&maxf,m,op);
			    if(m[i][j][0]>minf)m[i][j][0]=minf;
			    if(m[i][j][1]<maxf)m[i][j][1]=maxf;
			}
			temp=m[1][n][1];//printf("%d\n",temp);
		    
			
			for(i=2;i<=n;i++)
				
				if(temp<=m[i][n][1]){temp=m[i][n][1];
				                    b[k++]=i;}

				//printf("%d\n",b[0]);					
			    if(m[b[0]][2][1]>m[b[1]][2][1])printf("%d\n",b[0]);
				else printf("%d\n",b[1]);
				
				return temp;
}
main()
{
	int i,j,n,k;
	int m[5][5][2]={{0},{0,0,5,5,0,0,0,0,0,0},{0,0,-7,-7,0,0,0,0,0,0},{0,0,4,4,0,0,0,0,0,0},{0,0,2,2,0,0,0,0,0,0}};
	char op[]={0,'x','t','t','x'};
	n=poly_max(4,m,op);

	printf("%5d\n",n);
	for(i=1;i<=4;i++)
	{
		for(j=1;j<=4;j++)
			for(k=0;k<2;k++)
			printf("%5d",m[i][j][k]);
		printf("\n");
	}
}