プロフィール

島田圭二

Author:島田圭二
Follow shimanp on Twitter

カレンダー
06 | 2017/07 | 08
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -
読断と変見内検索
訪問ありがとうございます
最近のコメント
最近のトラックバック
関連リンク
カテゴリー
月別アーカイブ


スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)
Java - 迷路の最短距離を求める
プログラマーとしての技量を測るという問題があったので挑戦してみた。
人材獲得作戦・4 試験問題ほか - 人生を書き換える者すらいた。
壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ
三時間以内にできれば優秀かもしれないらしい。
とりあえずソース
package src;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Shortest {
private static final char WAY = '$';
private static final char S = 'S';
private static final char G = 'G';

private Stack st = new Stack();
private int goalCnt = 0;
Stack shortest = null;

public static void main(String[] args) {
Shortest sht = new Shortest();
sht.way(args[0]);
}

private void way(String inputPath) {
try {
// char配列に読み込む
char[][] inpMap = inputFile2char2D(inputPath);
Point s = getPoint(inpMap, S);

gotoGoal(s.x, s.y, mapCopy(inpMap));
System.out.println("経路数:" + goalCnt);

if (shortest != null) {
//経路を記述
for(int[] yx : shortest){
inpMap[yx[0]][yx[1]] = WAY;
}
}
print2DChar(inpMap);
outputFile4char2D("output.txt", inpMap);
} catch (Exception ex) {
ex.printStackTrace();
}
}

private void gotoGoal(int x, int y, char[][] map) {
// ゴールだったら終了
if (map[y][x] == G) {
if(shortest == null)shortest = copyStack(st);
if(shortest.size() > st.size())shortest = copyStack(st);
goalCnt++;
return;
}
if (map[y][x] != S) map[y][x] = WAY;
int[] yx = {y,x};
//スタックにつむ
st.push(yx);
// System.out.println("x=" + x + ",y=" + y);
if (map[y-1][x] == ' ' || map[y-1][x] == G) gotoGoal(x, y-1, map);
if (map[y+1][x] == ' ' || map[y+1][x] == G) gotoGoal(x, y+1, map);
if (map[y][x-1] == ' ' || map[y][x-1] == G) gotoGoal(x-1, y, map);
if (map[y][x+1] == ' ' || map[y][x+1] == G) gotoGoal(x+1, y, map);
//全方向だめな場合は終了
map[y][x] = ' ';
//スタックから出す
st.pop();
return;
}

private Point getPoint(char[][] arg2D, char c) {
Point p = new Point(-1, -1);
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
int len2D = arg2D[i].length;
for (int j = 0; j < len2D; j++) {
if (arg2D[i][j] == c) {
p.y = i;
p.x = j;
return p;
}
}
}
return p;
}

private char[][] inputFile2char2D(final String path) throws Exception {
char[][] arg = null;
try {

FileInputStream fi = new FileInputStream(path);
InputStreamReader ir = new InputStreamReader(fi);
BufferedReader br = new BufferedReader(ir);

String line;
List lines = new ArrayList();
int row = 0;
while ((line = br.readLine()) != null) {
lines.add(line);
row++;
}
arg = new char[row][];
int r = 0;
for (String l : lines) {
arg[r++] = l.toCharArray();
}
fi.close();
ir.close();
br.close();
} catch (Exception ex) {
throw ex;
}
return arg;
}

private char[][] mapCopy(char[][] map) {
int map2Dlen = map.length;
char[][] copy = new char[map2Dlen][];

for (int i = 0; i < map2Dlen; i++) {
copy[i] = new char[map[i].length];
System.arraycopy(map[i], 0, copy[i], 0, map[i].length);
}
return copy;
}

private Stack copyStack(Stack s){
Stack copy = new Stack();
for(int[] xy : s){
int[] c = new int[2];
c[0] = xy[0];
c[1] = xy[1];
copy.push(c);
}
return copy;
}

private void outputFile4char2D(final String path, final char[][] arg2D)
throws Exception {
FileOutputStream fo = new FileOutputStream(path);
OutputStreamWriter ow = new OutputStreamWriter(fo);
BufferedWriter bw = new BufferedWriter(ow);
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
bw.write(arg2D[i]);
bw.newLine();
}
bw.close();
}

private void print2DChar(final char[][] arg2D) {
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
System.out.println(arg2D[i]);
}
}

}


一応書いてみたけど、どうやらこれだと、全経路を通ってからチェックするので、
不完全な最短チェックらしく、レベル3ということみたい。。。
まだまだだな・・・。
っていうか、全経路を通らずにどうやってチェックするんだろう?
後でググってみよう。

スポンサーサイト
アルゴリズム | 【2010-04-09(Fri) 14:08:49】 | Trackback:(0) | Comments:(1)
アルゴリズム - クイックソート - 再帰編
数字などを並び替えするアルゴリズムにクイックソートがある。
とても効率的でソートアルゴリズムの中でもトップクラスに早いらしいけど、
完全に理解していなかったので、wikiを見ながら勉強してみた。

とりあえず、wiki通りにJAVAで書いてみた

public class QuickSort {

public static void main(String[] args) {
int[] a = {8,4,3,7,6,5,2,1};
QuickSort q = new QuickSort();
q.sort(a, 0, a.length - 1);
for (int k = 0, len = a.length; k < len; k++) {
System.out.print(k == 0 ? a[k] : "," + a[k]);
}
}

public void sort(int a[], int left, int right) {
if (left < right) {
int p = a[(left+right)/2]; //中央を軸とする
int l = left - 1;
int r = right + 1;
int t;
while (true) {
while (a[++l] < p); //軸より大きい値を左から探す
while (a[--r] > p); //軸より小さい値を右から探す
if (l >= r)break;
t = a[l]; //左と右の値を入れ替える。
a[l] = a[r];
a[r] = t;
}
sort(a, left, l - 1);
sort(a, r + 1, right);
}
}
}

wikiにも説明があるけど、自分なりに説明してみる。


①軸を決める
配列の中から、一つ適当に軸となる値を選ぶ。
プログラムで言うと
int p = a[(left+right)/2];

*軸は配列内の中央に位置しているものがベスト

②左から順に軸より大きい値を探す
プログラムで言うと
while (a[++l] < p);

の箇所whileで左から順に軸より大きい数を探し、あったら、ループ終了。

③右から順に軸より小さい値を探す
プログラムで言うと
while (a[--r] > p);

の箇所whileで右から順に軸より小さい数を探し、あったら、ループ終了。

④値入れ替え
②で見つけた値と③で見つけた値の位置を入れ替える。
プログラムで言うと
t = a[l];      
a[l] = a[r];
a[r] = t;

この入れ替えを繰り返すことで、左側は軸より小さい値となり
右側は軸より大きい値となる。

ただし、lの値がrの値以上となるとループを抜ける
プログラムで言うと
if (l >= r)break;


⑤左側の部分を再帰的にソート
軸より小さな左側の部分を再帰的にソートする
プログラムで言うと
sort(a, left, l - 1);


⑥右側の部分を再帰的にソート
軸より大きな右側の部分を再帰的にソートする
プログラムで言うと
sort(a, r + 1, right);


具体的な流れ


初期データ:{8,4,3,7,6,5,2,1}
1.軸を決める
一番始めの軸は、(0+7)/2=3.5→intなので3
で配列は0から始まるので、3の要素は「7」となる。
よって軸は「7」となる
8,4,3,7,6,5,2,1


2.左から順に軸より大きい値を探す
   8,4,3,7,6,5,2,1
→ l

8が軸の7より大きい

3.右から順に軸より小さい値を探す
  8,4,3,7,6,5,2,1
r ←

1が7より小さい

4.値入れ替え
lの値(0)はrの値(7)より小さいので、
2で見つけた8と3で見つけた1を入れ替える
1,4,3,7,6,5,2,8


5.再度左右から値を探し、入れ替え・・・を繰り返す。
lの値がrの値より小さいので、再度左から軸より大きい値、
右から軸より小さい値を探す。
  1,4,3,7,6,5,2,8
→ l
r ←

左から探した大きい値は7(軸と同じ)、
右から探した小さい値は2となる。

7と2を入れ替える
1,4,3,2,6,5,7,8


まだlの値がrの値より小さいので、再度左から軸より大きい値、
右から軸より小さい値を探す。
  1,4,3,2,6,5,7,8
→ l
r ←

左から探した大きい値は7(軸と同じ)、
右から探した小さい値は5となる。
しかし、lの値がrの値以上となってしまったため、ループは終了。

6.左側の部分を再帰的にクイックソート
左側の部分は[1,4,3,2,6,5]となる
プログラムで言うとleftからl-1ということになる。
leftは0でl-1は5となるので、0~5の配列要素が対象となる。

  左側部分  | 右側部分
1,4,3,2,6,5 | 7,8


で、左側の部分をまた1.に戻って、ソートを行う。

7.右側の部分を再帰的にクイックソート
右側の部分は[7,8]となる
プログラムで言うとr+1からrightということになる。
r+1は6でrightは7となるので、7~8の配列要素が対象となる。

  左側部分  | 右側部分
1,4,3,2,6,5 | 7,8


で、右側の部分をまた1.に戻って、ソートを行う。

以上説明終了。
てかクイックソートは説明が難しいな・・・


アルゴリズム | 【2009-03-08(Sun) 15:59:32】 | Trackback:(0) | Comments:(0)
べき乗アルゴリズム - 下位桁編
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 - 404 Blog Not Found
function (str, n){
var result = '';
for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str;
return result;
}

通常、べき乗の計算はべき乗の数だけ掛け合わせて計算を行う。
例えば24の場合、2×2×2×2となり、2を4つ掛け合わせる。
この計算の仕方だとべき乗の数が増えれば増えただけ掛け合わせることになる。
しかし、冒頭のアルゴリズムを使用するとlog n回で済み、処理が早くなるようだ。
でもwikiのべき乗アルゴリズムを見てもいまいち、何をやっているのかよくわからない。。。
とりあえず、wiki通りにjavaで書いてみた。
public long beki(long p, int n) {
long v = 1;
for(; n > 0; n >>>= 1){
if((n & 1)==1){
v*=p;
}
p*=p;
}
return v;
}

一応正常に動作するようだが、まだよくわかっていない、、、がなんとか説明してみることにする。

プログラムはとりあえず置いておいて、べき乗の性質から


wikiにもあるがべき乗には、
(ax)2 = a2x
という性質がある。この性質が重要。
具体的な数字を当てはめると、
(22)2 = 22*2
となる。つまりこれは(22)2 = 24ということである。
この考えで行くと
28 は ((22)2)2となる。
実はこの時点で計算が大分減っていることに気づくと思う。
普通に計算すると28は2×2×2×2×2×2×2×2と2を7回掛ける必要がある。
しかし、((22)2)2とすると、まず、22の計算をして4になり次に、4×4の計算をして16になり、
最後に16×16の計算をして256となり、3回の計算で済む。
なんと7回の計算が3回に減るのである。このアルゴリズムではこの特性を大いに利用する。

でこの性質をどうやって利用するの?


とりあえず、単純なべき乗の計算の効率化はできた。
しかし、この計算を行うには、べき乗の値に4乗が含まれているか?
8乗が含まれているか?と分析しなければならない。
どういうことかというと、wikiと同じ、a43について考えてみる。
a43 = a32+8+2+1 = a32×a8×a2×a1
と、43乗には32乗、8乗、2乗、1乗が含まれていることになる。
これをどうやって知るの?ということである。

ここで2進数登場


べき乗を分析するのには2進数を使う。
wikiにもあるけど、とりあえず、1,2,4,8,16,32を2進数にしてみる。
10進→2進
1    →1
2    →10
4    →100
8    →1000
16   →10000
32   →100000
で、43を2進数にしてみる
43 → 101011
43の2進数の値をよく見ると、1,2,8,32が含まれていることが分かる。
まず、101011の一桁目が1、を表す、で二桁目が2を表す、で三桁目が4を表すが0であるので、
43には4は含まれていないことになる。で同様に、四桁目が8で、5桁目が16で0なので含まれず、
最後の五桁目が32にとなる。
そうつまり、2進数にすると、何が含まれているのかが分かるのである。
何が含まれているのかが分かれば効率的な計算方法を利用することができる。

でようやくここからプログラムの説明に戻る


public long beki(long p, int n) {
long v = 1;
for(; n > 0; n >>>= 1){
if((n & 1)==1){
v*=p;
}
p*=p;
}
return v;
}
まず、for文の説明から。
for(; n > 0; n >>>= 1){
これはべき乗nを右にシフトしていってnが0以下になるまで回り続けろということである。
例えば、べき乗が43の場合、2進数は101011となる。
この101011を右に1シフトすると、10101となる。さらにシフトすると、1010となり、次に101、10、1、そして最後に0となりfor文は終了する。
なぜ、このようなfor文にするかというと、先ほどのべき乗の分析が関係してくる。
べき乗の分析は2進数にして、ある桁が1かどうかで含まれているかどうかを判断している。
なのでfor文で一つずつ右にシフトし、一桁目が1かどうか、次のifで判断しているのである。
で1の場合は、べき乗の元の値を結果値に掛ける。
v*=p;
ただし、元の値pは元の値のままでなく、for文が回る度にべき乗となる。
p*=p
例えば、元の値が2で1回まわったら2×2で4になり、2回まわったら4×4で16になる。
何でこんなことをしているかというと、べき乗の性質と効率的計算を思い出して欲しい。
(ax)2 = a2x
である。
つまり、べき乗を2進数にして一桁目から分析していって、1だったら、その桁にふさわしい値を
結果に掛けていってるのである。
例えば元の値が2で3桁目が1の場合、3桁目にはfor文は2回まわっているので、
2×2で4、4×4で16となり、結果値に16を掛けるのである。

以上、最後らへんはちょっと無理やりだったけど、眠いのでこれで終了。
てか、たったこれだけのプログラムを理解してまとめるのに半日もかかっちまったぜ。。。ふっ。

アルゴリズム | 【2009-02-02(Mon) 02:53:12】 | Trackback:(0) | Comments:(0)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。