お試しの最近のブログ記事

ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。スタートノードからゴールノードまでの最短距離とその経路を求めることができます。

並行処理のお題です。ある床屋の亭主は、客がいないときまって居眠りを始めます。床屋店内には三台の散髪兼順番待ち用の椅子があり、客は来店時に椅子に空きがあれば、いずれかに勝手に座って自分の番が来るのを待ち、散髪を終えてから店を出ます。空席が無ければそのまま何もせずに立ち去ります。居眠り中の亭主は、客の入店時に起こされると待ち客すべてをひとりずつ順に散髪しますが、誰もいなくなればまた居眠りを始めます。

この床屋店に16人の客が訪れた日のシミュレーションを行なうコードと、その結果（下に例として示したログ形式。「[スレッドのIDなど] イベント描写」の一覧と終了後の総括）を出力して示してください。なお、散髪には一人当たり100～400ミリ秒の時間（この範囲でランダムに変化）を要し、客は通常 0～200ミリ秒（同）の間隔で訪れます。ただし例外として9番目の客だけは前の客から1200ミリ秒程度の間隔（すなわち、最大三名の待ち客全員を散髪し終えるのに十分な時間）をあけて訪れるものとします。

実装に際し、実行時のデッドロックの回避はもちろんですが、そのほかにも、競合状態（席の空きを確認して座ろうとしたら、もう別の客が座っていた...というような事態）などの不整合も生じないよう配慮し、必要であればそのための対策を講じてください。たとえば来客の間隔が仮に０ミリ秒で固定の場合（つまり、客が一斉に来店した場合）でも、コードが正常に動作するかどうか試してみるのもよいかもしれません。

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

プロジェクトの成果物を細分化し、担当者割り振りやスケジュール・進捗状況の管理を行うWBS（Work Breakdown Structure：作業分解図）。
プロジェクトを管理する上で欠かせないこの手法を中心に、チームとしても個々としても作業を効率的に進められるようになるツールです。