M個のFIFO Queueを用意し、次のように２つの操作を定義する。
- put : M個のQueueから、ランダムに１つ選んで、末尾に要素を追加する
- get : M個のQueueから、ランダムに１つ選んで、Queueが空でなければ先頭要素を取り出し、空ならば空を返す
for (i=0; i<N; ++i)
{ put(i);
print(get());
}
という処理を行ったときに、最後に出力される要素が空である確率を数学的に分析せよ。また、その時に、Queue全体に残っている要素数の期待値を分析せよ。
