csx.c

四人过河求时间最短问题

/*四人过河求时间最短问题*/
/*先将是个人过河所需时间按从小到大排序x0<=x1<=x2<=x3*/
/*该问题存在两种求最优路径方法*/
/*当2*x1-x2<=1时*/
/*可用方法一求得最短路径*/
/*否则用方法二求最优路径*/
#include<math.h>
void main()
{
	int	M[4],N[4]={0,0,0,0},i,j=0,k=0,mm=0;
	int hn=0,a,b,cc,aa,nn;

	printf("\nInput arry M[4]:\n\n");
	scanf("%d,%d,%d,%d",&M[0],&M[1],&M[2],&M[3]);
	printf("\n");
	for(i=0;i<4;i++)
		printf("%d   ",M[i]);
	printf("\n");
	for(i=0;i<4;i++)                    /*排序*/
		printf("%d   ",M[i]);
	for(i=0;i<3;i++)
	{
		j=i;
		while((j>-1)&&(M[j]>M[j+1]))
		{
			aa=M[j];
			M[j]=M[j+1];
			M[j+1]=aa;
			j--;
		}
	}
	printf("\n\n");
	for(i=0;i<4;i++)
		printf("%d   ",M[i]);                 /*排序*/


	printf("\n\nArry N[4]:\n\n");
	printf("\n");
	for(i=0;i<4;i++)                  
		printf("%d   ",N[i]);
	printf("\n");	
	cc=M[0]+M[1];
    printf("\n\n%d,%d,%d__%d\n",M[0],M[1],M[0],cc);
	N[3]=M[0];
	M[0]=0;	

	if(2*M[1]-M[2]<=1)                    /*当2*x1-x2<=1时*//*可用方法一求得最短路径*/
	{					
loop:
		for(i=0;i<3;i++)        /*M排序*/
	{
		j=i;
		while((j>-1)&&(M[j]>M[j+1]))
		{
			aa=M[j];
			M[j]=M[j+1];
			M[j+1]=aa;
			j--;
		}
	}
		a=M[3];
		M[3]=0;
		b=M[2];
		M[2]=0;
		for(i=0;i<3;i++)        /*N排序*/
	{
		j=i;
		while((j>-1)&&(N[j]>N[j+1]))
		{
			aa=N[j];
			N[j]=N[j+1];
			N[j+1]=aa;
			j--;
		}
	}		
		hn=M[0]+M[1]+M[2]+M[3];					
		if(N[0]!=0)mm=N[0];
		else if(N[1]!=0)mm=N[1];
		else if(N[2]!=0)mm=N[2];
		else if(N[3]!=0)mm=N[3];
		for(i=0;i<3;i++)
		{
			if(N[i]!=mm);
			else N[i]=0;
		}
		if(hn>0)
		{
			cc=cc+a+mm;
			M[0]=mm;
			printf("\n%d,%d,%d__%d\n",a,b,M[0],cc);
		}
		else
		{
		cc=cc+a;
		printf("\n%d,%d,%d__%d\n",a,b,M[0],cc);
		M[0]=mm;
		}
		if(hn==0)return;
		else goto loop;
	}
	else                     /*当2*x1-x2>1时*//*可用方法二求得最短路径*/
	{
		if(N[0]!=0)mm=N[0];
		else if(N[1]!=0)mm=N[1];
		else if(N[2]!=0)mm=N[2];
		else if(N[3]!=0)mm=N[3];
		for(i=2;i<3;i++)
		{
			cc=cc+mm+M[i];
			printf("\n\n%d,%d,%d__%d",mm,M[i],mm,cc);
		}
		while(i=3)
		{
			nn=0;
			cc=cc+M[i];
			printf("\n\n%d,%d,%d__%d",mm,M[i],nn,cc);
			break;		
		}
	}		/*CrossRiver2(M[4],N[4]);*/;
}