問題

問85　ファイルを4冊だけ置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいとき，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルがA，B，C，D，B，A，E，A，B，Fの順で必要になった場合，最後に引き出しにしまうファイルはどれか。

ア　A
イ　B
ウ　D
エ　E

テクノロジ系>基礎理論>アルゴリズムとプログラミング>アルゴリズム

解説と解答

　このような問題では，問題文の指示に従って，机上のファイルがどんな風に変わっていくか，図を描いてみるとよいでしょう。ここでは，次のことに留意します。

●机にはファイルを4冊だけ置くことができる
●ファイルの種類はA～Fの6冊である
●5冊目のファイルを置くときは，最後に参照してからの経過時間が最も長いファイルを引き出しにしまう

　ファイルを参照する順番は，(1)A，(2)B，(3)C，(4)D，(5)B，(6)A，(7)E，(8)A，(9)B，(10)Fの順です。机上に置かれていくファイルの流れは，次のようになります。

　以上より，最後に引き出しにしまうファイルはDであることが分かります。

　なお，「最後に参照してから最も時間が経過しているものを作業対象から追い出す」という考え方をLRU（Least Recently Used）方式と言い，主記憶（メインメモリー）の容量よりも大きなプログラムを効率的に読み込むための代表的なアルゴリズムの一つです。

　以上より正解は，選択肢ウです。