アルゴリズムA 第5回


待ち行列 (queue)

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

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

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


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

    (インデックス+1) を 「配列の大きさ」で割った余り
とすることで簡単に実現できます。

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

MyQueue.java
授業で配布するプリントを参照して下さい。
RunMyQueue.java
授業で配布するプリントを参照して下さい。
RunMyQueue.javaの実行例
sp204: ~/pro 4> javac RunMyQueue.java 
sp204: ~/pro 5> 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
sp204: ~/pro 6> 

グラフ

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


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

ノード01234567
0 false true false false false false false false
1 true false true true true false false false
2 false true false false false false true false
3 false true false false false false false false
4 false true false false false true false false
5 false false false false true false true true
6 false false true false false true false true
7 false false false false false true true false

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

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

深さ優先探索

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

幅優先探索

  1. 始点を出発し、隣接している節(始点からの距離1)にそれぞれ進む。
  2. それぞれ進んだ節(始点からの距離n)から、隣接している節 (始点からの距離n+1)まで進む。ただし、既に訪れた節には進まない。
  3. 行き場所がなくなったら終了
BFSearch.java
授業で配布するプリントを参照して下さい。
BFSearch.javaの実行例
% javac BFSearch.java
% java BFSearch
0
1
2
3
4
6
5
7


アルゴリズムA 演習


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


課題5a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai5a
提出ファイルBFSearch2.java
コメント欄 graph01data.txtの内容 を入力した時の出力結果

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

入力形式
T                 ←節の総数
N                 ←辺の総数
A1  B1    ←辺の両端の節
..
AN  BN
S                   ←Sは始点
入力例(graph01data.txt)
8
9
0 1
1 2
1 3
1 4
2 6
4 5
5 6
5 7
6 7
0
BFSearch2.java(骨子のみ)
授業で配布するプリントを参照して下さい。
BFSearch2.javaの実行例
% javac BFSearch2.java 
% java BFSearch2 < graph01data.txt 
0
1
2
3
4
6
5
7

課題5b: 深さ優先探索

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai5b
提出ファイルDFSearch.java
コメント欄 graph01data.txtの内容 を入力した時の出力結果

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

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


課題4c: 分数クラス

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai4c
提出ファイルFraction.java
コメント欄実行したときの出力結果

ユークリッドの互除法を用いて、2個の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
授業で配布するプリントを参照して下さい。
Fraction.javaの実行例
% javac Fraction.java
% java Fraction
6
403

課題4d: 分数電卓

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai4d
提出ファイルMulOperator.java
コメント欄

RunMain の実行時に

4  3  /  12  8  /  *  1  3  /  1  5  /  -  /
を入力した時の出力結果

および

RunMain の実行時に、以下の形式でデータを与える。 ただしa , b ,c は +,-,*,/のどれかである。

8 3 7 4 a b c
答が10になるときのa,b,c

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

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

public class Fraction extends CalcElement {

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

RunMain.java
授業で配布するプリントを参照して下さい。
CalcElement.java
授業で配布するプリントを参照して下さい。
Operator.java
授業で配布するプリントを参照して下さい。
AddOperator.java
授業で配布するプリントを参照して下さい。

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

RunMain.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の場合)
%