ファイルを4冊だけ置くことができる机で、A～Fの6冊のファイルを使って仕事をする。 机上に5冊目のフ

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


意味が分からないのですが、分かりやすい解説をお願いします。

No.1 ベストアンサー 回答者： 曾美山 回答日時： 2018/11/19 19:00

４冊まで置けるので、ABCDがこの順（使った順）で机に並びます。

次にBAが再度使われるので、また使った順で並びなおすとCDBAと並びます。
次にEがきますが、４冊までしか置けないので、この中で一番古いCが消え、DBAEになります。
またABを使うので、DEABになり、Fがきて、一番古いDが消え、EABFとなります。

Fが最後にくるんだからFを最後にしまうんじゃないの？という気もしますが、
最終的に机にあるEABFはしまう必要はないので、ここまでの流れで消した（しまった）ものは
CとDだけで、このうち最後にしまったのはDとなります。

No.2 回答者： yhr2 回答日時： 2018/11/19 20:04

これ、在庫管理や、コンピュータのデータ管理に使われる「最も使われない（Least Frequently Used : LFU）」というアルゴリズム、考え方です。

主メモリ上のデータを一時的にハードディスクなどに退避させるときに、どのデータを退避させるかを判断するときなどに使います。「最も長く使われていない」ものは「アクセス頻度が最も低い」と判断するわけです。

↓　LFU
https://www.weblio.jp/content/LFU
https://www.sophia-it.com/content/LFU
https://dictionary.goo.ne.jp/jn/249304/meaning/m …

上記の場合には、
　A、B、C、D
までは「一時保存」しなくても済みます。（左にあるほど、古くに使ったもの）

次に「B」が来ても、机の上にあるので「一時退避」は不要で、順番が
　A、C、D、B
に変わります。（B が最新になる）
次に「A」が来ても、机の上にあるので「一時退避」は不要で、順番が
　C、D、B、A
に変わります。（A が最新になる）

次に「E」が来ると、机の上はいっぱいなので、最も長く使っていない左端の「C」を「一時退避」させ、Ｅを机の上に置きます。これで、順番が
　D、B、A、E
に変わります。（Ｅ が最新に、Ｄが最古になる）
次に「A」が来ても、机の上にあるので「一時退避」は不要で、順番が
　D、B、E、A
に変わります。（A が最新になる）
次に「B」が来ても、机の上にあるので「一時退避」は不要で、順番が
　D、E、A、B
に変わります。（B が最新になる）

次に「F」が来ると、机の上はいっぱいなので、最も長く使っていない左端の「D」を「一時退避」させ、Ｆを机の上に置きます。これで、順番が
　E、A、B、Ｆ
に変わります。

ということで、最後に「一次退避」させるのは「D」です。