新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題8をJavaにしてみました
山崎講師2023 年 4 月からIPA （独立行政法人情報処理推進機構）の基本情報技術者試験の制度が変更されました。
ここでは、「基本情報技術者試験 科目 B のサンプル問題20問バージョン」の中から、アルゴリズムとプログラミングの問題を取り上げ、Javaのソースコードを示します。
新人エンジニア研修に参加されている皆様の参考になれば幸いです。
【Javaプログラム】
【結果】
| A C D D |
【プログラムの解説】
このプログラムは、優先度付きキュー（Priority Queue）を実装し、優先度が高い順に要素を取り出す手続き prioSched() を実行するものです。
まず、PriorityQueue というジェネリッククラスが定義されています。これは、要素の型 T と優先度の型 Integer を持つキューです。キューの実態は、内部で List<Data<T, Integer>> というデータ構造を使って表現されます。ここで Data は、要素と優先度をペアにしたデータ構造で、ジェネリック型 I と P を持ちます。また、PairComparator というクラスが定義されており、これは Data の優先度を比較するための Comparator です。
PriorityQueue には以下のメソッドが定義されています。
enqueue(T item, int priority)：要素itemを優先度priorityでキューに追加します。要素が追加されるたびに、内部のリストをPairComparatorでソートします。dequeue()：優先度が最も高い要素を取り出し、その要素自体を返します。キューが空の場合はnullを返します。size()：キューの要素数を返します。
prioSched() では、PriorityQueue を使って以下の手順で要素を追加・取り出しています。
- 要素 "A" を優先度 1 で追加します。
- 要素 "B" を優先度 2 で追加します。
- 要素 "C" を優先度 2 で追加します。
- 要素 "D" を優先度 3 で追加します。
- キューから要素を 2 つ取り出します。
- 要素 "D" を優先度 3 で再度追加します。
- 要素 "B" を優先度 2 で追加します。
- キューから要素を 2 つ取り出します。
- 要素 "C" を優先度 2 で追加します。
- 要素 "A" を優先度 1 で追加します。
- キューが空になるまで、要素を取り出して表示します。
このプログラムは、ジェネリックを使ったデータ構造の実装方法や、Comparator を使ったソート方法など、基本的なデータ構造の実装
について学べます。また、優先度付きキューを使ったアルゴリズムについても理解できます。
優先度付きキューは、一般的なキューと異なり、要素が追加されるときに優先度を指定することができます。このため、要素が取り出される順番が優先度によって決まります。このプログラムでは、ジェネリックを使ってデータ構造を汎用的に実装しているため、要素の型や優先度の型を変更することができます。
キューの実体は List で表現されています。要素が追加されるたびに、内部のリストを PairComparator でソートしているため、常に優先度が高い順に並んでいます。PairComparator は、Data の優先度を比較するための Comparator として実装されており、内部で Integer.compare() を使って比較しています。
prioSched() では、優先度付きキューを使ってジョブスケジューリングのシミュレーションを行っています。ジョブの優先度が高い順に処理するため、キューに要素を追加する際に優先度を指定しています。また、キューから要素を取り出す際には、dequeue() メソッドを呼び出しています。
このような優先度付きキューは、ジョブスケジューリング以外にも、最短経路探索やヒープソートなど、様々なアルゴリズムで使われます。プログラムを読み解くことで、このようなアルゴリズムを理解する手助けになるでしょう。
