（离线缓存）现代计算机使用缓存你技术将少量数据保存于快速内存中。虽然程序可能访问大量数据，但通过将主存中少量数据保存在缓存（cache）——容量小当更快的内存中，还是可以大幅度降低访问时间。当一个计算机程序运行时，它对内存进行n次内存访问<r1,r2,...,rn>，每个请求访问一个特定数据元素。例如，一个程序访问4个不同元素{a,b,c,d}，访问请求序列为{d,b,d,b,d,a,c,d,b,a,c,b}。令k为缓存的规模。当缓存已经保存了k个元素，而程序访问(k+1)个元素时，系统必须决定，对于此访问的请求及之后的请求，要将哪k个元素保存在缓存中。更准确的，对于每个请求ri，缓存管理算法检查元素ri已经在缓存中。如果已在，就产生一次缓存命中（cache hit）；否则，产生一次缓存未命中（cache miss）。若产生缓存未命中，系统从主存中提取ri，同时缓存管理算法必须决定是否将ri保留在缓存中。如果算法决定保留ri且缓存中已经保存了k个元素，则它必须将某个元素逐出缓存来为ri腾出空间。缓存管理算法逐出数据的目标是处理整个访问请求序列的过程中缓存未命中的次数最少。
通常，缓存管理是一个在线问题，也就是说，我们在决定哪些数据保留在缓存中时，并不知道未来的访问请求是什么。但是，我们考虑此问题的离线版本，即预先知道完整的请求序列（包含n个访问请求）及缓存规模k，目标仍是最小化缓存未命中次数。
我们可以用一种称为将来最远（furthest-in-future）的贪心策略求解离线缓存问题，此策略选择逐出缓存的数据的方法是选择在请求序列中下一次访问距离最远的数据。
a.编写使用将来最远策略的缓存管理器的伪代码。输入是请求序列<r1,r2,...,rn>和缓存规模k，输出为决策结果序列——处理每个请求时逐出缓存的是哪个数据（如果需要逐出），分析算法的运行时间。
b.证明：离线缓存问题具有最优子结构性质。
c.证明：将来最远策略可以保证最下缓存未命中次数。
