磁盘文件最优存储问题

磁盘文件最优存储问题1.问题描述：设磁盘上有𝑛个文件𝑓1，𝑓2，…，𝑓𝑛，每个文件占用一个磁道。这n个文件的检索概率分别是𝑝1，𝑝2，…，𝑝𝑛，且∑𝑝𝑖=1𝑛𝑖。磁头从当前磁道移动到被检索信息的磁道所需时间是两个磁道之间镜像距离来度量。如果文件𝑓𝑖放在第i磁道上，1≤i≤n，则检索这n个文件的期望时间是∑𝑝𝑖𝑝𝑗𝑑(𝑖,𝑗)1≤𝑖j≤n。其中，𝑑(𝑖,𝑗)是第i道与第j道的镜像距离abs(i-j)。磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。2.算法设计首先对文件进行排序。接着采用贪心算法将文件𝑓1放在中心磁道上，𝑓2，𝑓3分别放在靠着𝑓1的左右磁道。例如，33,55,22,11,9。先进行排序，9,11,22,33,55。然后放置为：11,33,55,22,9。此时检索时间最小。3.实现效果4.代码：磁盘文件最优存储问题.txt