算法设计与分析3页.doc

计算机算法设计与分析1、 实验名称：用贪心算法解决磁盘文件最优存储问题。2、 实验目的：1）理解贪心算法的概念和掌握其基本要素； 2）针对具体问题，能应用贪心算法设计有效算法，提高对实际 问题的分析、设计和实现能力； 3）为后续课程的学习及课程设计打下坚实的实践基础。3、 实验内容： 1）问题描述： 设磁盘上有n个文件，f1,f2,fn，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,pn,且p1+p2+pn =1。磁头从当前磁道移到被检信息磁道所需的时间可用这2 个磁道之间的径向距离来度量。如果文件pi存放在第i道上, ，则检索这n 个文件的期望时间是 ,其中d(I,j) 是第i道与第j 道之间的径向距离|i-j|。磁盘问题就是要确定这n 个文件在磁盘上的存储位置，使期望检索时间达到最小。设计一个解此问题的算法，并分析算法的正确性与计算复杂性。 2）问题分析： a、通过对所给数据33 55 2