磁盘文件最优存储

    磁盘文件最优存储，复杂度为O(n^2)。

    这是Ian的第一篇博客，希望大家喜欢，我会努力把自己的理解融入到我要讲的东西中，有什么不足欢迎指教。

    题目是从书上来的，不是原创。

问题描述：

    设磁盘上有 n 个文件 f1, f2, …, fn,每个文件占用磁盘上的 1 个磁
道。这 n 个文件的检索概率分别是 p1, p2, …, pn,且 p1+p2+…+ pn=1。
磁头从当前磁道移到被检信息磁道所需的时间可用这 2 个磁道之间
的径向距离来度量。如果文件 fi 存放在第 i 道上，1≤i≤n，则检索这
n 个文件的期望时间是对于所有的 i < j, time += pi*pj*d(i,j)。其中d(i,j)
是第 i 道与第 j 道之间的径向距离|i-j|。

    磁盘文件的最优存储问题要求确定这 n 个文件在磁盘上的存储
位置， 使期望检索时间达到最小。

算法设计：

    很多同学都认为设计算法要从原理进行分析，我认为这是好的，但不一定最有效，我认为最有效的方式是先从全局把握，看一下经验能带给我们什么，然后再从算法设计的流程一步一步的下去。正如这个问题，易知本题的贪心选择性质为，使概率值大的两个文件尽可能的挨在一起。即先让文件按概率大小排序，概率最大的应该放中间，第二大和第三大的分别放在最大的左右两边，第四大的放在第二大左边，第五大的放在第三大的右边，依次下去就行。

直接上代码：（C++,vs2015）

//磁盘文件最优存储

#include<string>
#include<iostream>
#include<bitset>
#include<fstream>
#include<math.h>
#include <algorithm>   
#define random(x) (rand()%x)

using namespace std;

//随机快排

template<class T>
void Swap(T &p, T &r)
{
	T tmp = p;
	p = r;
	r = tmp;
}

template<class T>
int Partition(T *a, int p, int r)
{
	int i = p, j = r + 1;
	T x = a[p];
	while (true) {
		while (a[++i] < x&&i < r);
		while (a[--j] > x);
		if (i >= j)break;
		Swap(a[i], a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}

template<class T>
int RandomizedPartition(T *a,int p,int r)
{
	int choose = r + 1;
	int i = random(choose);
	Swap(a[i], a[p]);
	return Partition(a, p, r);
}


template<class T>
void RandomizedQuickSort(T *a,int p,int r)
{
	if (p < r) {
		int q = RandomizedPartition(a, p, r);
		RandomizedQuickSort(a, p, q - 1);
		RandomizedQuickSort(a, q + 1, r);
	}
}
//磁盘文件最优存储
double diskstore(int nCount,double *a,double *s)
{
	RandomizedQuickSort(a, 0, nCount - 1);
	//sort(a, a+ nCount);
	double sum = 0.0;

	for (int i = 0; i < nCount; i++) {
		sum += a[i];
		
		printf("%f", sum);

	}
	for (int i = 0; i < nCount; i++) {
		
		printf("%f", a[i]);
	}
	for (int i = 0; i < nCount; i++) {

		printf("%f", s[i]);
	}
	int L_number = 1;
	int R_number = 1;
	for (int j=0;j<nCount;j++){ 
		
		if (j == 0) {
			s[nCount / 2] = a[(nCount - 1) - j]/sum;
			printf("/n%d", (nCount - 1)-j);
			printf("/n%f", s[nCount / 2]);
		}
		else{
			int t = j % 2;
			if (t != 0) {
				s[nCount / 2 - L_number] = a[(nCount - 1) - j] / sum;
				printf("/n%d", (nCount - 1) - j);
				printf("/n%f", s[nCount / 2 - L_number]);
				L_number++;

			}

			else{
				s[nCount / 2 + R_number] = a[(nCount - 1) - j] / sum;
				printf("/n%f", a[(nCount - 1) - j]);
				printf("/n%d", (nCount - 1) - j);
				printf("/n%f", s[nCount / 2 + R_number]);
				R_number++;
			}
		}	
				
	}
	double expect_time = 0;

	for (int k = 0; k<nCount; k++)
		for (int p = k+1; p < nCount; p++) {
			expect_time += s[k] * s[p] * abs(p - k);
		}


	return expect_time;
}
void main() {
	int nCount = 0;        //数据的个数
	double ET = 0;    //期望时间
	double *a;//存放数据的数组
	double *s;
	errno_t err;
	FILE *fp;
	
	err = fopen_s(&fp, "D:\\input.txt", "r");
	fscanf_s(fp, "%d", &nCount);
	a = new double[nCount];
	s = new double[nCount];
	for (int i = 0; i<nCount; i++){
		fscanf_s(fp, "%lf", &a[i]);
		s[i] = a[i];
		//printf("%f", a[i]);
		//printf("%f", s[i]);
	}
		
	fclose(fp);
	ET = diskstore(nCount, a,s);
	
	FILE *ofp;
	err = fopen_s(&ofp, "D:\\output.txt", "w");

	fprintf_s(ofp, "%f", ET);
	fclose(ofp);
	delete[] a;
	delete[] s;

}

在这段代码中，首先是给概率值排序。我用了自带的和写的随机快排都进行了测试，结果在通用的例子上是正确的。有问题请大家留言，谢谢，我是Ian.