disk.cpp

对于给定的文件检索概率,编程计算磁盘文件的最优存储方案.

///////////////////////////////////////////////////////////////////////////
//    题目相当于给定(1/2)*n(n-1)个元素PiPj的集合A和(1/2)*n(n-1)个        //
//    元素d(i,j)的集合B，要求从A、B集合中各选一个元素配对求积，使        //
//    这些积的总和达到最小。如果a1>a2,a1∈A,a2∈A;b2<b1,b1∈B,b2∈B。    //
//    配对有两种：(a1b1,a2b2)和(a1b2,a2b1)，显然a1b2+a2b1<a1b1+a2b2。    //
//    说明PiPj大的，要使d(i,j)尽量地小。一般地，若设Pn≤……≤P2≤P1,    //
//    且将文件f1放在中心磁道上，然后将f2、f3分别置于紧靠f1的左、右侧     //
//    磁道上；接着又将f4放在f2的右边，……。如此按检索概率的大小置放，   //
//    磁盘文件的这种排列将是一种最佳方案。                               //
//    该算法的复杂性是O(nlog(2的n次方))。                                //
///////////////////////////////////////////////////////////////////////////

#include<stdio.h>
#include<fstream.h>

//快速排序算法，对所有文件的检索概率从小到大进行排序a[0]<a[1]<……a[n-1]。//////////

void QuickSort(int a[],int low,int up)    
{                                         
	int i,j;
	int t;
	if(low<up)
		{
		i=low;
		j=up;
		t=a[low];
		while(i!=j)
			{
			while(i<j&&a[j]>t)
				j--;
			if(i<j) a[i++]=a[j];
			while(i<j&&a[i]<=t)
				i++;
			if(i<j) a[j--]=a[i];
			}
		a[i]=t;
		QuickSort(a,low,i-1);
		QuickSort(a,i+1,up);
		}
}

//贪心算法求解最小期望检索时间。////////////////////////////////////////////////////

double greedy(int P[], int n)      
{
	int* X=new int[n];             
	QuickSort(P,0,n-1);            //调用快速排序函数对检索概率进行从小到大的排序。
	int k=(n-1)/2;
	X[k]=P[n-1];                   //按照检索概率大的位于磁道中心，第二大和第三大的
	for(int i=k+1;i<n;i++)         //位于最大两边，以此类推，重新存放于数组X中。
		X[i]=P[n-2*(i-k)];
	for(i=k-1;i>=0;i--)
		X[i]=P[n-2*(k-i)-1];
	double m=0,t=0;
	for(i=0;i<n;i++)
		{
		m+=P[i];                   //m用于存放所有文件的检索概率之和。
		for(int j=i+1;j<n;j++)
			t+=X[i]*X[j]*(j-i);    //t用于存放最终的最小期望检索时间。
		}
	t=t/m/m;                       //因为第k个文件的检索概率应为ak/m,
	return t;                      //所以fi和fj的文件检索概率应为X[i]/m和X[j]/m，
	                               //则最小期望检索时间应该为X[i]*X[j]*(j-i)/m/m的和。
}

/////////////////////////////////////////////////////////////////////////////////////

void main()                        
{
	int n;
	double result;
	ifstream input("input.txt");
	ofstream output("output.txt");
	input>>n;                      //从文件中读取文件个数n。
	int* a=new int[n];
	for(int i=0;i<n;i++)
		input>>a[i];               //从文件中读取所有文件的检索概率。
	result=greedy(a,n);            //调用贪心算法求解最小期望检索时间。
	output<<result;                //输出结果到文件中。
}