other.cpp

给定一个集装箱

/*  HELLO.C -- Hello, world */

#include "stdio.h"
#include "conio.h"
#include <stdlib.h>
#include <string.h>
#include <windows.h>

#define ERROR 0
#define N  50
#define PI 3.141593

double a[N];
double area,Hei;
double W,H;
int L;

int Partition(double a[],int low,int high){
    double pivotkey=a[low];
    double t;
    while(low<high){
        while((low<high)&&(a[high]<=pivotkey)) high--;
        t=a[low];
        a[low]=a[high];
        a[high]=t;
        while((low<high)&&(a[low]>=pivotkey)) low++;
        t=a[high];
        a[high]=a[low];
        a[low]=t;
    }
    return low;
}

void QuickSort(double a[],int low,int high){
    if(low<high){
        int pivotloc=Partition(a,low,high);
        QuickSort(a,low,pivotloc-1);
        QuickSort(a,pivotloc+1,high);
    }
}



int greedy(double a[],int i,double leftw,int n){
   /*  printf("%d %d %d\t",i,H,leftw);*/
     int j,k;
     if(i==n){return 1;}
     if(Hei<H)
	 {
       if((2*a[i])<=leftw){
         Hei=Hei;
         leftw=leftw-2*a[i];
		 area+=PI*a[i]*a[i];
         i++;
         greedy(a,i,leftw,n);
       }
       else
	   { 
		   j=i+1;
		   while(j<n)
		   {
			   if((2*a[j])<leftw)
			   {
				   Hei=Hei;
				   leftw=leftw-2*a[j];
				   area+=PI*a[j]*a[j];
                   for(k=j+1;k<n;k++)
				   {
					   a[k-1]=a[k];
					   a[k]=0;
				   }
				   break;
			   }
			   else
			   {
				   j++;
			   }
		   }
           Hei=Hei+2*a[i];
		   leftw=W-2*a[i];
		   area+=PI*a[i]*a[i];
		   i++;
           greedy(a,i+1,leftw,n);
	   }           
     }
}


void main()
{
	FILE *fp;
	char filename[10];
	int i,n,first;
	DWORD time_1,time_2;
	double a[N];

	while(1)
	{
		printf("\nplease input filename:");
		scanf("%s",filename);
		if((fp=fopen(filename,"r"))==NULL)
		{
			printf("\ncan not open this file!");
			exit(0);
		}

		fscanf(fp,"%d",&n);
		fscanf(fp,"%lf",&W);
		fscanf(fp,"%lf",&H);
		fscanf(fp,"%d",&L);
		printf("\n圆柱形木材的个数:%d\n集装箱的宽度:%f\n集装箱的高度:%f\n集装箱的长度即圆柱形木材的长度:%d\n",n,W,H,L);

		for(i=1;i<=n;i++)
		{
			fscanf(fp,"%lf",&a[i]);
			printf("%lf\t",a[i]);
		}
		fclose(fp);

		QuickSort(a,1,n);
		printf("\n按半径从大到小的顺序如下：\n");
		for(i=1;i<=n;i++)
		{
			printf("%lf\t",a[i]);
		}
		
        time_1=GetTickCount();

		for(first=1;first<=n&&((2*a[first]>W)||(2*a[first]>H));first++);
	    if(first>n) printf("the container is too small!");
		Hei=2*a[first];
		area=0;
		greedy(a,first,W,n);
		printf("所用体积：%lf\n",area*L);
		printf("空间利用率：%lf\n",area/(W*H));

		time_2=GetTickCount();
		printf("\nthe running time is:%f\n",(time_2-time_1)/1000.0);
	}
}