问题描述:
要定义磁带上第n个文件,须要依次经过前面n-1个文件。假设磁带上有n个文件,长度分别为L[0],L[1], ..., L[n-1]且被访问的概率分别为P[0],P[1],...,P[n-1],请问怎样安排它们在磁带上的存储顺序最好?
分析:
最好的安排方式应该对应期望最小的方式。思考一下,不难写出期望的表达式:
(注意,访问第i个文件,因为要完整地读入这个文件,经过的长度是L[0]+L[1]+...+L[i],不是L[0]+L[1]+...+L[i-1]。我第一次写的时候就写错了。)
这时就犯难了:L[0],L[1], ..., L[n-1]与P[0],P[1],...,P[n-1]一一对应......
阅读全文