Javaの課題丸投げコミュの[課題]アルゴリズム

課題２の内容のフローチャートです。

課題２の内容のフローチャートです。

ところでいきなり課題2,5のトピがなくなったのは何ゆえ?

課題1は二分探索木での要素を何にしろとは書かれていないけど、int型整数ということかな。

はい、特に指定無かったんでint型でいいと思います。

class Node {

int key;
Node right;
Node left;

public Node(int key) {
this.key = key;
}
}

class Tree {

public Node tIns(Node root, int key) {
Node p = root;
Node pp = null;
while (p != null) {
pp = p;
if (p.key == key) {
return root;
}
if (p.key > key) {
p = p.left;
} else {
p = p.right;
}
}
p = new Node(key);
if (pp == null) {
root = p;
} else {
if (pp.key > key) {
pp.left = p;
} else {
pp.right = p;
}
}
return root;
}

public Node tSrch(Node root, int key) {
Node p = root;
if (p != null && p.key != key) {
Node c;
if (p.key > key) {
c = p.left;
} else {
c = p.right;
}
p = tSrch(c, key);
}
return p;
}

public Node tSrch2(Node root, int key) {
Node p = root;
while (p != null) {
if (p.key == key) {
break;
}
if (p.key > key) {
p = p.left;
} else {
p = p.right;
}
}
return p;
}

public void display(Node node) {
if (node.left != null) {
display(node.left);
}
System.out.println(node.key);
if (node.right != null) {
display(node.right);
}
}

public static void main(String args[]) {
int[] key = new int[] {99, 2, -4, 35, 2, 6, -1, 1, 2, 4, 6, -34, 100,};
Tree tree = new Tree();
Node root = null;

System.out.println("## T_SRCHによる挿入");
for (int i = 0; i < key.length; i++) {
System.out.println("" + key[i] + "を二分検索木に挿入します");
root = tree.tIns(root, key[i]);
}
System.out.println("## 二分検索木の全ノードを表示");
tree.display(root);

System.out.println("## T_SRCHによる検索");
System.out.println("## 0,1, ... , 9を要素とするノードを検索します");
for (int i = 0; i < 10; i++) {
Node node = tree.tSrch(root, i);
if (node != null) {
System.out.println("" + node.key + "を要素とするノードが見つかりました");
}
}

System.out.println("## T_SRCH2による検索");
System.out.println("## 0,1, ... , 9を要素とするノードを検索します");
for (int i = 0; i < 10; i++) {
Node node = tree.tSrch2(root, i);
if (node != null) {
System.out.println("" + node.key + "を要素とするノードが見つかりました");
}
}
}
}

上のは課題1、今度は課題2

import java.util.LinkedList;
import java.util.Queue;

public class DfsBfs {
private int[][] adj;
private int n;
private int[] visited;
private Queue<Integer> queue;

/** @param adj 隣接行列 */
public DfsBfs(int[][] adj) {
this.adj = adj;
n = adj.length;
visited = new int[n];
queue = new LinkedList<Integer>();
}

public void dfs() {
System.out.println("## 深さ優先検索");
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
dfsVisit(i);
}
}
}

private void dfsVisit(int u) {
System.out.println(" 現在" + (u + 1) + "を訪問");
visited[u] = 1;
for (int i = 0; i < n; i++) {
if ((visited[i] == 0) && (adj[u][i] == 1)) {
dfsVisit(i);
}
}
}

public void bfs() {
System.out.println("## 幅優先検索");
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
bfsVisit(i);
}
}
}

private void bfsVisit(int u) {
enqueue(u);
while (!headEqualsTail()) {
int s = dequeue();
if (visited[s] == 0) {
System.out.println(" 現在" + (s + 1) + "をはじめて訪問");
}
visited[s] = 1;
for (int i = 0; i < n; i++) {
if ((adj[s][i] == 1) && (visited[i] == 0)) {
enqueue(i);
}
}
}
}

private void enqueue(int u) {
queue.add(u);
}

private int dequeue() {
return queue.poll();
}

private boolean headEqualsTail() {
return (queue.peek() == null);
}

public static void main(String[] args) {
DfsBfs dfsBfs = new DfsBfs(new int[][] {
{0, 1, 0, 0, 1, 0,},
{1, 0, 1, 0, 1, 0,},
{0, 1, 0, 1, 0, 0,},
{0, 0, 1, 0, 1, 1,},
{1, 1, 0, 1, 0, 0,},
{0, 0, 0, 1, 0, 0,},
});
dfsBfs.dfs();
dfsBfs.bfs();
}
}
/*
隣接行列は
http://ja.wikipedia.org/wiki/%E9%9A%A3%E6%8E%A5%E8%A1%8C%E5%88%97
のものを採用。

与えられた図からそのままコーディングすればループは
for (int i = 1; i <= n; i++) {処理}
となるはずだが、
iが1ではじまるか0ではじまるかは本質的ではないので、ソースの単純化のため
for (int i = 0; i < n; i++) {処理}
を採用。
System.out.println(" 現在" + (u + 1) + "を訪問");
System.out.println(" 現在" + (s + 1) + "をはじめて訪問");
と、変数に1を加えたものを表示しているのは、これを補正するため。

J2SE5.0より以前のバージョンのJavaではコンパイルを通らない。
*/

これって、java の課題なんですかね .. ? だって、フローチャートを見る限り、ポインターアクセスに ^ ( 上向き矢印 ) を使っているし、T-INS なんかは、「root を変更」といった形で、「Pascal での var 引数 ( いわゆる、参照渡し .. )」を想定しているし .. 。Pascal の課題のような気がする..。

多分、var 引数を利用することを想定しているので、( 値渡ししか使えない .. ) java 的には無意味な代入文 ( 例えば、 T-INS の冒頭の 「p ← root」 ) が入っている気がする ..

結果的、ござござ さんの解答も、tIns では、( 参照渡しが使えないので、しぶしぶ .. ) 返値を、変数に代入しているし、tSrch でも、意味なく、p, c の Local 変数が使われている。

まあ、僕だったら、tSrch は、Local 変数をばっさり削るでしょうね..。

-- 8< ---- 8< ---- 8< ---- 8< ---- 8< ---- 8< ---- 8< --
public Node tSrch ( Node p, int key ) {

if ( p != null ) {
if ( p.key > key ) {
p = tSrch ( p.left, key );
} else if ( p.key < key ) {
p = tSrch ( p.right, key );
}
}

return p;
}
-- 8< ---- 8< ---- 8< ---- 8< ---- 8< ---- 8< ---- 8< --

# 検索結果を、直に return せずに、わざわざ、一旦 p に戻しているのは、単に、「サブルーチンの出口 ( return のある場所 ) を一箇所にまとめる」という個人的な方針に基いているからです。

## まあ、本当ならば、直に return した方が、「末尾再帰」であることが明確になり、賢いコンパイラーなら、自動的に Loop に展開してくれるだろうが .. ( 最近のもっと賢いコンパイラは、僕のコードでも Loop に展開したりして .. )。

# tSrch は、最初の引数を var 引数宣言しなくてもよいのにも拘らず、わざわざ p に代入しているのは、単に、var 引数の方が ( レコード型のデータのコピー : 値渡し より .. ) 効率が良いってことかなぁ .. ( しかし、今の計算機環境だと、意味がないような気もするんだけどなぁ .. )。

元々Pascalは教育用言語として扱われる面がありますので，
アルゴリズムの講義で，Pascalを使うのはめずらしいことではないですよ．
ですから，おそらく課題をだした先生も，「Pascalで作れ」という意図は持ってないと思います．

ちなみに，最近のアルゴリズムの教科書はCとかJavaで書かれているのが多いですね．が，けっこうお堅い教科書は今でもPascalを用いてるのがありますね．

(おちくん@8 さん)
> アルゴリズムの講義で，Pascalを使う

アルゴリズムは、言語に対して非依存な概念です。したがって、教育上、特定の言語に依存した記述は、さけるべきでしょう。

もちろん、アルゴリズムは、何らかの形で、「記述」する必要がありますので、その意味で、特定のプログラミング言語 ( か、または、それに近い疑似言語... ) を選択して、それで表現しなければならないわけですが、今回の場合は、その表現言語として、Pascal ( と思われる ? ) 言語を採択し、それにべたな表現を選択 ( var 変数 ) していながら、それを直接表現できない java で書けっていうのが、変だと思っているわけです。

==

まあ、恐らくは、以前から、アルゴリズムの話題を取り上げており、前は Pascal だったが、今は java 導入。ただ、教材だけは、昔のままということなのでしょうが、問題は、別に「教材の持ち回り」ということではなく、「そのような情况である処に、この『丸投げ』が生じている」ということでしょう。

# ということで、「java > [議論]宿題解決コミュニティ？ (http://mixi.jp/view_bbs.pl?id=7759222&comm_id=1465) 」へ続く..