题目内容
（请给出正确答案）
提问人：网友18***590
发布时间：2022-06-12
[主观题]
问题描述:设磁盘上有n个文件每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是且磁头从
问题描述:设磁盘上有n个文件
每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是
且
磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是
.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.
磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置,使期望检索时间达到最小.试设计一个解此问题的算法,并分析算法的正确性与计算复杂性.
算法设计:对于给定的文件检索概率,计算磁盘文件的最优存储方案.
数据输入:由文件input.txt给出输入数据.第1行是正整数n,表示文件个数.第2行有n个正整数a,表示文件的检索概率.实际上第k个文件的检索概率应为
结果输出:将计算的最小期望检索时间输出到文件output.txt.
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
查看官方参考答案
，被检索的概率是
检索每个文件需要从磁带的开始位置进行操作，例如文件i存储在磁带的第100到第250单元，那么检索该文件需要的时间是250。假设n个文件的排列顺序是
以扫描单元数作为时间复杂度的度量，这些文件的平均检索时间是：
，被检索的概率是
检索每个文件需要从磁带的开始位置进行操作，例如文件i存储在磁带的第100到第250单元，那么检索该文件需要的时间是250。假设n个文件的排列顺序是
以扫描单元数作为时间复杂度的度量，这些文件的平均检索时间是：
，被检索的概率是
，i=1,2,···,n，且
. 检索每个文件需要从磁带的开始位置进行操作，比如文件i需要空间
，被检索的概率是
且
检索每个文件需要从磁带的开始位置进行操作，例如文件i存储在磁带的第100到第250单元，那么检索该文件需要的时间是250。假设n个文件的排列顺序是
以扫描单元数作为时间复杂度的度量，这些文件的平均检索时间是：
个字节的存储空间，i = 1, 2,···, n.磁盘的总容量是C. 且
. （1）如果要求存入的文件个数达到最多，选用哪种算法设计技术？简述算法设计思想，证明算法的正确性，并估计算法最坏情况下的时间复杂度. （2）如果要求磁盘的剩余空间达到最小，选用哪种算法设计技术？简述算法设计思想，并估计算法最坏情况下的时间复杂度.
