アルゴリズムa 第5回

待ち行列 (queue)

「データの挿入が一方の端でのみ行われ、削除がもう一方の端でのみ行われる」 リストを、『待ち行列 (queue)』といいます。

• enqueue --- データを待ち行列に入れること
• dequeue --- データを待ち行列から取り出すこと

「最初に入れたデータが最初に取り出される」ようなデータ構造を "First In First Out" (FIFO)といいます。 これは「最後に入れたデータが最後に取り出される」とも考えられるので "Last In Last Out" (LILO) と言うこともあります。

配列による待ち行列の実現

配列の大きさをnとすると、配列へアクセスする際に 「インデックスがnになったら、インデックスを0に戻す」ことで あたかも配列の先頭と末尾がつながっているかのごとく扱うことが できます。 このようなバッファをリングバッファ(ring buffer)といいます。 プログラム的には、「次のインデックスの計算」を

    (インデックス＋1) を 「配列の大きさ」で割った余り

配列が空の状態では front==rearとなります。 もし、配列が一杯になった状態を rear==front で表すと、 空の場合と区別がつかなくなってしまうので、 プログラムでは「必ず１つ空の要素を残しておく」ことにしています。

MyQueue.java

RunMyQueue.java

$ javac RunMyQueue.java 
$ java RunMyQueue 
aを入れた
bを入れた
cを入れた
MyQueue=[a b c ] front=0 rear=3
aを取り出した
bを取り出した
MyQueue=[c ] front=2 rear=3
dを入れた
eを入れた
cを取り出した
MyQueue=[d e ] front=3 rear=0
fを入れた
dを取り出した
eを取り出した
MyQueue=[f ] front=0 rear=1
クリアした
MyQueue=[] front=0 rear=0
gを入れた
hを入れた
MyQueue=[g h ] front=0 rear=2
$ 

グラフ

「グラフ」 (graph) は、「節点」(node, または「頂点」 vertex) を 「辺」(edge, または「枝」 branch)で結んだものです。

このようなグラフをデータとして表現するために、、次のような 隣接行列 (adjacency matrix) を用います。

行方向をi, 列方向をjとすると、 「節点 $i$ $\longrightarrow$ 節点 $j$ への辺がある場合に true、無い場合に false 」 となっています。自分自身( $i ~ \rightarrow ~ i$ )へのリンクはないものとしています。

辺に向きを持ったグラフを「有向グラフ」(directed graph)といいますが、 ここでは辺に向きを持たない「無向グラフ」(undirected graph)を扱います。

深さ優先探索

1. 始点を出発し、隣接している節を行けるところ(すなわち、辺で連結していて まだ訪れていない節点がある限り)まで進む
2. 行き場所がなくなったら、行き場所がある節まで元来た辺を戻り、 再び行ける所まで行く。
3. 行き場所がなくなったら終了

幅優先探索

1. 始点を出発し、隣接している節(始点からの距離1)にそれぞれ進む。
2. それぞれ進んだ節(始点からの距離n)から、隣接している節 (始点からの距離n+1)まで進む。ただし、既に訪れた節には進まない。
3. 行き場所がなくなったら終了

BFSearch.java

$ javac BFSearch.java 
$ java BFSearch 
0
1
2
3
4
6
5
7

アルゴリズムA 演習

課題提出〆切は次回の講義の開始時刻です。

課題5a

BFSearch.java を変更してBFSearch2.javaを作成して下さい。 グラフの様子がプログラムに書いてあるのではなく、実行時に 標準入力から次の形式で読み込むものとします。

T                 ←節の総数
N                 ←辺の総数
A1  B1    ←辺の両端の節
..
AN  BN
S                   ←Sは始点

8
9
0 1
1 2
1 3
1 4
2 6
4 5
5 6
5 7
6 7
0

BFSearch2.java(骨子のみ)

$ javac BFSearch2.java 
$ java BFSearch2 < graph01data.txt 
0
1
2
3
4
6
5
7

課題5b: 深さ優先探索

深さ優先探索をするように変更して下さい。

[ヒント] BFSearch2.java の中で、MyQueueを使っている部分を MyStackを使うように変更すればよいだけです。 (push → enqueue, pop → dequeue)

課題4c: 分数クラス

ユークリッドの互除法を用いて、２個のintegerの最大公約数を計算する メソッドをFraction.javaの中に、getGCD()というメソッド名で記述しなさい。

コメント欄には実行結果を貼り付けておいて下さい。

[例] 自然数 99541 と 81809の最大公約数は403

   99541 % 81809 → 17732     「大きい数A」を「小さい数B」で割った余りCを計算
   81809 % 17732 → 10881      Bを新しいAに、Cを新しいBにして、計算を繰り返す
   17732 % 10881 → 6851
   10881 % 6851  → 4030
   6851 % 4030   → 2821
   4030 % 2821   → 1209
   2821 % 1209   → 403
   1209 % 403    → 0          余りが0になったときのBが最大公約数

Fraction.java

% javac Fraction.java
% java Fraction
6
403

課題4d: 分数電卓

4  3  /  12  8  /  *  1  3  /  1  5  /  -  /

8 3 7 4 a b c

分数計算を行う「逆ポーランド計算機」を作成してみましょう。

まず先程作成した Fraction.java を次の CalcElementを継承する ようにして下さい。

public class Fraction extends CalcElement {

その後で、次のJavaファイルを作成します。

RunMain.java

CalcElement.java

Operator.java

AddOperator.java

AddOperator.java を参考にして、次の3種類のファイルを作成しなさい。

• SubOperator.java ... 引き算演算子
• MulOperator.java ... 掛け算演算子
• DivOperator.java ... 割り算演算子

$ javac RunMain.java 
$ java RunMain 
1 2 / 1 3 / + 
5/6        → 結果が出力される
1 2 / 1 3 / - 
1/6        → 結果が出力される
1 2 / 1 4 / / 2 12 / * 
1/3        → 結果が出力される
Ctl-D      ← 行の先頭でコントロールキーとDを同時に押す (MacOSやLinuxの場合)
Ctl-Z      ← 行の先頭でコントロールキーとZを同時に押す (Windowsの場合)
$