明解 Javaによるアルゴリズムとデータ構造 8-1_力まかせ法
8-1 力まかせ法
- brute force な文字列探索やるよ~
順探索
ソースコード
- ちょっと焦げ臭い。もっとスマートに書けそうだが・・・
- 進捗表示が意外とめんどかった。
- 探索対象文字列の何文字目から探索しているかを表示する部分で、フラグ処理が必要なんだが、ここをうまくかければ、綺麗になりそう。
import java.util.Scanner; class BFmatch { static int bfMatch(String txt, String pat) { // 探索対象文字列のインデックス int pt = 0; // マッチャーのインデックス int pp = 0; // 進捗表示インデックスたち・・・ // 「部分一致状時マッチャー用スペーサー」生成のためのインデックス int pFixed = -1; // 「マッチャー用スペーサー」生成のためのインデックス int patIndex = 0; // 「比較対象識別子用スペーサー」生成のためのインデックス int charIndex = 0; // スペーサーたち・・・ final String txtSpacer = "%4s"; String patSpacer; String charSpacer; // 文字比較回数 int compareCnt = 0; // ブルートフォースサーチ while (pt != txt.length() && pp != pat.length()) { if (pFixed > 0) { patIndex = pFixed; } else { patIndex = pt; } patSpacer = (patIndex != 0) ? "%" + patIndex + "s" : ""; charIndex = patIndex + pp; charSpacer = (charIndex != 0) ? "%" + charIndex + "s" : ""; // 単一文字一致 if (txt.charAt(pt) == pat.charAt(pp)) { if (pFixed < 0) { System.out.printf("%3s " + txt + "\n", pt); pFixed = pt; } else { System.out.printf(txtSpacer + txt + "\n", ""); } System.out.printf(txtSpacer + charSpacer + "+\n", "", ""); System.out.printf(txtSpacer + patSpacer + pat + "\n\n", "", ""); pt++; pp++; // 単一文字不一致 } else { if (pFixed < 0) { System.out.printf("%3s " + txt + "\n", pt); pFixed = pt; } else { System.out.printf(txtSpacer + txt + "\n", ""); } System.out.printf(txtSpacer + charSpacer + "|\n", "", ""); System.out.printf(txtSpacer + patSpacer + pat + "\n\n", "", ""); pt = pt - pp + 1; pp = 0; pFixed = -1; } } // 探索成功 if (pp == pat.length()) { System.out.println("比較回数: " + compareCnt); return pt - pp; } // 探索失敗 System.out.println("比較回数: " + compareCnt); return -1; } public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("テキスト: "); String s1 = stdIn.next(); System.out.print("パターン: "); String s2 = stdIn.next(); int idx = bfMatch(s1, s2); if (idx == -1) { System.out.println("テキスト中にパターンは存在しない"); } else { int len = 0; for (int i = 0; i < idx; i++) { len += s1.substring(i, i + 1).getBytes().length; } len += s2.length(); System.out.println((idx + 1) + "文字目にマッチします"); System.out.println("テキスト: " + s1); System.out.printf(String.format("パターン: %%%ds\n", len), s2); } } }
逆探索
- とりあえず後回し
String.indexOf による文字列探索
- int indexOf(String str)
- int indexOf(String str, int fromIndex)
- fromIndex 以降を検索
- int lastIndexOf(String str)
- int lastIndexOf(String str, int fromIndex)
- fromIndex 以降を検索
Eclipse で開発するときに気をつけること
- 謎の ClassNotFound
- リソースファイルに記載した内容が読み込まれない
- 何らかの事情でビルドがされていないなどの事由で、ビルドしたクラスファイルやリソースファイルが古いとか存在しないとかの可能性あり。モノが存在していたとしても、タイムスタンプで最新かを確認するべし。
- 今回は、クリーンしてもモノが出てこなかったので、Eclipse べったり信用はよくないね。便利だけども、それなりのツールという認識で。
Cygwin 初期セットアップまとめ
Cygwinの初期セットアップについて、いつもの作業なのでメモ化しておく。
- Cygwin インストール(Windows XP 32bit スッキリ行かなかった版)
- Cygwin インストール(Windows 8 64bit スッキリ行った版)
Cygwin インストール(Winsows XP 32bit うまく行かなかった版)
- インストーラから標準パッケージで
wget インストール
git インストール
$ git config --global http.proxy *******:****
apt-cyg インストール
$ wget http://apt-cyg.googlecode.com/svn/trunk/apt-cyg $ mv apt-cyg /usr/bin $ chmod +x /usr/bin/apt-cyg
apt-cyg の接続先変更
$ apt-cyg update -m http://ftp.jaist.ac.jp/pub/cygwin
apt-cyg 書き換え
- apt-cyg が jaist のディレクトリ構造に対応してない(http://ftp.jaist.ac.jp/pub/cygwin/x86 が正しいが、"x86"が重複した誤ったhttp://ftp.jaist.ac.jp/pub/cygwin/x86/x86 配下にアクセスしよる)ので。差分は以下。
$ diff /bin/apt-cyg_original /bin/apt-cyg 98c98,99 < wget -N $mirror/setup.bz2 --- > # wget -N $mirror/setup.bz2 > wget -N $mirror/x86/setup.bz2 105c106,107 < wget -N $mirror/setup.ini --- > # wget -N $mirror/setup.ini > wget -N $mirror/x86/setup.ini
zsh インストール
$ apt-cyg install zsh
vim インストール
- 以下のエラーが出た
$ apt-cyg install gvim ...snip... Installing xxd Found package xxd --2014-02-10 14:46:09-- http://ftp.jaist.ac.jp/pub/cygwin/x86/release/vim/xxd/x xd-7.4.135-1.tar.xz sciproxy (sciproxy) をDNSに問いあわせています... 192.168.16.11, 192.168.16.12 sciproxy (sciproxy)|192.168.16.11|:9080 に接続しています... 接続しました。 Proxy による接続要求を送信しました、応答を待っています... 200 OK 長さ: 55800 (54K) [application/x-tar] `xxd-7.4.135-1.tar.xz' に保存中 100%[======================================>] 55,800 --.-K/s 時間 0.05s 2014-02-10 14:46:09 (1.05 MB/s) - `xxd-7.4.135-1.tar.xz' へ保存完了 [55800/55800 ] Unpacking... bunzip2: (stdin) is not a bzip2 file. tar: これは tar アーカイブではないようです tar: 前のエラーにより失敗ステータスで終了します
apt-cyg インストール その2-1
$ git clone https://github.com/kou1okada/apt-cyg.git
- 今度は /usr/lib/git-core/git-remote-https.exe で怒られる。激おこ。
- 原因調査
$ cygcheck /usr/lib/git-core/git-remote-https.exe C:\cygwin\lib\git-core\git-remote-https.exe C:\cygwin\bin\cygcrypto-0.9.8.dll C:\cygwin\bin\cygwin1.dll C:\WINDOWS\system32\KERNEL32.dll C:\WINDOWS\system32\ntdll.dll C:\cygwin\bin\cygz.dll C:\cygwin\bin\cyggcc_s-1.dll C:\cygwin\bin\cygcurl-4.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll C:\cygwin\bin\cyggssapi-3.dll C:\cygwin\bin\cygheimntlm-0.dll C:\cygwin\bin\cygkrb5-26.dll C:\cygwin\bin\cygasn1-8.dll C:\cygwin\bin\cygroken-18.dll C:\cygwin\bin\cygcrypt-0.dll C:\cygwin\bin\cygcom_err-2.dll C:\cygwin\bin\cygwind-0.dll C:\cygwin\bin\cyghx509-5.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll C:\cygwin\bin\cygintl-8.dll C:\cygwin\bin\cygiconv-2.dll C:\cygwin\bin\cygsqlite3-0.dll C:\cygwin\bin\cygheimbase-1.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll C:\cygwin\bin\cygidn-11.dll C:\cygwin\bin\cyglber-2-4-2.dll C:\cygwin\bin\cygldap-2-4-2.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll C:\cygwin\bin\cygsasl2-3.dll cygcheck: track_down: could not find cygssl-1.0.0.dll C:\cygwin\bin\cygssh2-1.dll cygcheck: track_down: could not find cygcrypto-1.0.0.dll cygcheck: track_down: could not find cygssl-1.0.0.dll
libopenssl100 インストール
- xz が絡んでくるので、setup.exeから。
apt-cyg インストール その2-2
- ca-bundle.crt 入ってないぽい。
$ git clone https://github.com/kou1okada/apt-cyg.git Cloning into 'apt-cyg'... error: error setting certificate verify locations: CAfile: /usr/ssl/certs/ca-bundle.crt CApath: none while accessing https://github.com/kou1okada/apt-cyg.git/info/refs fatal: HTTP request failed
- …(無言でブラウザから apt-cygを落としてきて、Explorer から上書き)
$ git config --global http.sslVerify false
- (無言)
vim インストール
$ apt-cyg install vim
- 別PC(Windows8 64bit)でもセットアップしたんだが、こっちはすんなり入った・・・。年代物のXPだからかなぁ。多分もろもろが汚くなってる。
Cygwin インストール(Windows 8 64bit スッキリ行った版)
wget インストール
git インストール
ca-certificates おまじないインストール
GnuPG インストール
apt-cyg インストール
$ wget https://raw.github.com/kou1okada/apt-cyg/master/apt-cyg $ chmod +x apt-cyg $ mv apt-cyg /usr/bin
apt-cyg の接続先変更
$ apt-cyg update -m http://ftp.jaist.ac.jp/pub/cygwin
zsh インストール
$ apt-cyg install zsh
vim インストール
$ apt-cyg install vim
参考・参照先:
Zsh - Windowsのターミナル環境を整える vol.1 - Qiita [キータ]
apt-cygでLinuxライクにパッケージをインストールしてみる - === SANDmark 19106 === beginning stress test
計算物理屋の研究備忘録 apt-cyg を64 bit 版でも使えるようにする
git - SSL certificate rejected trying to access GitHub over HTTPS behind firewall - Stack Overflow
世界で戦うプログラミング力を鍛える150問
会社の同期に借りた本の問題、ぼちぼち今の俺でも解けそうなのが出てきているので、解いてこうと思う。世界で戦いたいんじゃなくて、世界で戦います(ドヤ
世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~
- 作者: Gayle Laakmann McDowell,秋葉拓哉,岩田陽一,北川宜稔,Ozy
- 出版社/メーカー: マイナビ
- 発売日: 2012/11/13
- メディア: 単行本(ソフトカバー)
- 購入: 143人 クリック: 7,806回
- この商品を含むブログ (46件) を見る
Chapter 3 スタックとキュー
問
- 1つの配列で3つのスタックをどうデザインする?
- push と pop に加えて min を持つスタックをどうデザインする? push, pop, min、全部O(1)の実行時間ね。
- Stack を複数備え、あるスタックを使いつくしたら次の Stack を利用し始めるような、SetOfStacksを実装せよ。 SetOfStacks.pop(), SetOfStacks.push()は、通常の1 Stack のデータ構造と同様に振る舞うようにせよ。 ex) 任意のStackからpopするpopAt(int index) を実装せよ
- ハノイの塔(バー3本)のソルバーを実装せよ
- MyQueue という名で、2 つのスタックを用いてキューを実装せよ
- スタック上のデータを小さい順に並び替えるプログラムを書け。最小がトップに来る。スタック以外のデータ構造(配列など)にスタック滋養のデータをコピーしてはいけない。スタックは、push, pop, peek, isEmpty のみを備える。
回答
- dualんときみたいにやれば多分できそう。
- 現時点での最小値を末尾に持つ、配列minを用意する。関数minは、配列minの末尾を返すだけ。O(1)。配列minの要素数をカウントするフィールド numMin も用意する。
- 擬似コードみたいなの
int[] min = new int[1000] // 最小値は配列に収める; int numMin = 0; // 配列minの要素数 void push(int e) { // (通常のpush処理) if (num == 0 || min[numMin] >= e) { // 等号つけとかないと何度か間を空けて // 同じ最小値が出てくるときの処理が厄介 min[numMin++] = e; } } int pop() { // (通常のpop処理) // popした値をfとしてローカル変数で持つ if (min[numMin - 1] == f) { numMin--; } } int min() { return min[numMin - 1]; }
- プロダクションコード
package ch03; class StackMin { private int[] stack; // スタック private int capacity; // 最大要素数 private int num; // スタックの要素数 private int[] min; // 最小値を収める配列スタック private int minNum; // 配列minの要素数 // 実行時例外クラス class OverflowMinStackException extends RuntimeException { public OverflowMinStackException() { } } class EmptyMinStackException extends RuntimeException { public EmptyMinStackException() { } } // コンスタラクタ StackMin() { capacity = 100; // 仮置き num = 0; minNum = 0; try { stack = new int[capacity]; min = new int[capacity]; } catch (OutOfMemoryError e) { capacity = 0; } } void push(int e) throws OverflowMinStackException { if (num >= capacity) { throw new OverflowMinStackException(); } stack[num++] = e; if (num == 0 || min[minNum] >= e) { min[minNum++] = e; } } int pop() throws EmptyMinStackException { if (num <= 0) { throw new EmptyMinStackException(); } int pop = stack[--num]; if (min[minNum - 1] == pop) { minNum--; } return pop; } int min() { if (minNum <= 0) { throw new EmptyMinStackException(); } return min[minNum - 1]; } int size() { return num; } int capacity() { return capacity; } int peek() throws EmptyMinStackException { if (num <= 0) { throw new EmptyMinStackException(); } return stack[num - 1]; } }
- テストコード出だし
package ch03; import static org.hamcrest.CoreMatchers.is; import static org.junit.Assert.assertThat; import org.junit.Before; import org.junit.Test; import org.junit.experimental.runners.Enclosed; import org.junit.runner.RunWith; import ch03.StackMin.EmptyMinStackException; @RunWith(Enclosed.class) public class StackMinTest { public static class 初期状態から始める場合 { StackMin sut; @Before public void setUp() { sut = new StackMin(); } @Test public void pushで1がスタックされること() throws Exception { sut.push(1); int expected = 1; int actual = sut.peek(); assertThat(actual, is(expected)); } @Test(expected = EmptyMinStackException.class) public void popで例外エラーが返ること() throws Exception { sut.pop(); } @Test(expected = EmptyMinStackException.class) public void minで例外エラーが返ること() throws Exception { sut.min(); } @Test public void sizeで0が返ること() throws Exception { int expected = 0; int actual = sut.size(); assertThat(actual, is(expected)); } @Test public void capacityで100が返ること() throws Exception { int expected = 100; int actual = sut.capacity(); assertThat(actual, is(expected)); } @Test(expected = EmptyMinStackException.class) public void peekで例外エラーが返ること() throws Exception { sut.peek(); } } }
- 擬似コードみたいなの
- (2013/02/10追記)とりあえず書いた。途中。
package ch03; class MultiStack { int stackCapacity = 0; int stackPtr; SingleStack[] singleStackArray; class EmptyStackException extends RuntimeException { EmptyStackException() { } } class OverflowStackException extends RuntimeException { OverflowStackException() { } } MultiStack(int stackCapacity) { this.stackCapacity = stackCapacity; try { singleStackArray = new SingleStack[stackCapacity]; } catch (OutOfMemoryError e) { stackCapacity = 0; stackPtr = 0; } } void push(SingleStack s) throws OverflowStackException { if (stackPtr >= stackCapacity) { throw new OverflowStackException(); } singleStackArray[stackPtr++] = s; } class SingleStack { int capacity; int[] stack; int ptr = 0; SingleStack(int elementCapacity) { this.capacity = elementCapacity; try { stack = new int[elementCapacity]; } catch (OutOfMemoryError e) { elementCapacity = 0; ptr = 0; } } void push(int e) throws OverflowStackException { if (ptr >= capacity) { throw new OverflowStackException(); } stack[ptr++] = e; } int pop() throws EmptyStackException { if (ptr <= 0) { throw new EmptyStackException(); } return stack[--ptr]; } int peek() throws EmptyStackException { if (ptr <= 0) { throw new EmptyStackException(); } return stack[ptr - 1]; } } }
- まだ。再帰使うととりあえずは書ける。
(1,2,3) = (1~N, 0, 0) → (N, 1~N-1, 0) → (0, 1~N-1, N) → (0, 0, 1~N)
の流れ。
(2013/02/06追記)
とりあえず書き下した。package ch03; import java.util.Scanner; class Hanoi { static void move(int no, int from, int to) { if (no > 1) { move(no - 1, from, 6 - from - to); } System.out.println(no + "枚目を、" + from + "軸から" + to + "軸に移動"); if (no > 1) { move(no - 1, 6 - from - to, to); } } public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("枚数?: "); int no = stdIn.nextInt(); int from = 1; int to = 3; move(no, from, to); } }
- まだ
- まだ
評価
- まだ
- まだ
- minを保持するデータ構造として、配列よりスタックのほうが良かったね。元から具備してる機能あるし。あと、初手からmin()叩くケースのエラー考慮漏れ。Integer.MAX_VALUE とか返してあげよう。
- 解1: pushする値と、その時点での最小値をフィールドに持つクラスを作成。そいつスタックする。スタックがかさんでくると、メモリ食いつぶしが二倍なのがいただけない。
- 解2: 最小値を押し込んでいくスタックを用意する。peekして最小値確認する感じ。自分の解法とほぼ同じ。スタックという構造を使うか、配列にマーカー付与するかの違い。
- 帰納的に一手一手書き出しながら一般の挙動をイメージして、実装した。一発ではないのでまだ染みこみ足りない。が、イメージを書き起こせるようにはなっているので、あと一歩。
- まだ
- まだ
総評
- 望洋さんの『Javaによるアルゴリズムとデータ構造』で触れたような話が多い。データ構造の基礎。一度理解したら、あとは空でサクサク書けるようになる事が必要だろう。各データ構造のアウトプット数回して、もうちょっと染みこませることが今必要。
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
付随して出た疑問・メモ
- JUnit のテストランナーで構造化 @Enclosed 指定した場合、テストクラスの内部クラスは static にしないと、テストケースとして拾われない。なんで?
- preタグ内でコード表示したいとき、インデントは一段深くしてやらんと正常に表示されないので以降注意。置換^\t -> \t\t 的な。
javari 超便利ィィィッ!
javariで靴買った。はじめて。あまりに便利で感動した。仕組みが自分の中に浸透してなくて利用してなかったんだけど、試してみて良かった!
なんで買ったの?
- 必要に迫られて。あと、javari なのは、試してみたかったから。
なに買ったの?
- 今回は 2 つのビジネスシューズを、それぞれ 0.5cm 刻みで2つずつ、計 4 足頼んだ。
- 履いた結果、片方がいまいちだったので、そちらは 2 足とも返品。いい感じだった方は、サイズ違いの 1 足を返品。
- 結果、1 足購入、3 足返品。
どれぐらいで届く?
- 東京 23 区住みだが、注文した翌日に届く。
返品のながれ
- 同梱されてた納品書の、返品したい商品に丸つける
- 送られてきたダンボールに返品する商品と 1. の納品書詰めて、ガムテ貼る
- コンビニから着払い発送
たったこれだけ!!やってみると、ほんとうにラク!!
結論
- 便利すぎるっしょコレ!
- 特に返品がすんごいラク。梱包に必要な物はガムテ以外、javari から商品送られてきた段階で揃ってるっていうのがでかい。
- 家の目の前がコンビニなので、全く苦じゃない。
- 買いたいもんが定まってる時は、店頭で買う気なくなった。おしゃべりしたい時とか、なに買うか決まってない時だけやな。品揃えは多分 javari のほうが上やしね。
[ジャランスリウァヤ] JALAN SRIWIJAYA キャップトゥ 98317 BLACK(BLACK/7)
- 出版社/メーカー: JALAN SRIWIJAYA(ジャランスリウァヤ)
- メディア: ウェア&シューズ
- この商品を含むブログを見る
(2014/01/29追記)
1/28 20時に届いて靴見定めて、1/29 1:00にコンビニから返品発送。お買物完了。
明解 Javaによるアルゴリズムとデータ構造 7-1_集合とは
7-1_集合とは
部分集合と真部分集合
真部分集合 proper subset
- 集合 A のすべての要素が集合Bの要素であって、集合AとBが等しくない
その他気付き
実行時には,左辺オペランド式を最初に評価する。その値がtrueならば,条件ORの値をtrueとし,右辺オペランド式は評価しない。左辺オペランドの値がfalseならば,右辺オペランド式を評価し,その値を条件OR式の値とする。この方法で,||はbooleanオペランド上で|と同じ結果を計算する。右辺オペランド式を常にではなくむしろ条件的に評価するという点だけが異なるものとする。
- 作ったメソッドがまさにこれに該当し、|| 演算子以降のaddメソッドが実行されていなかった
テスト対象メソッド
package algorithm.ch07; public class IntSet { private int max; private int num; private int[] set; public IntSet(int capacity) { num = 0; max = capacity; try { set = new int[max]; } catch (OutOfMemoryError e) { max = 0; } } public boolean add(int n) { if (num >= max || contains(n) == true) { return false; } else { set[num++] = n; return true; } } public boolean add(IntSet s) { boolean changeFlg = false; for (int e: s.set) { changeFlg = changeFlg || add(e); } return changeFlg; } }
テストクラス
package algorithm.ch07; import static org.hamcrest.CoreMatchers.*; import static org.junit.Assert.*; import org.junit.Before; import org.junit.Test; import org.junit.experimental.runners.Enclosed; import org.junit.runner.RunWith; @RunWith(Enclosed.class) public class IntSetTest { public static class 操作対象の集合が空の場合 { IntSet sut; IntSet s; @Before public void setUp(){ sut = new IntSet(10); s = new IntSet(10); s.add(10); s.add(15); s.add(20); } @Test public void 別の集合をaddすると和集合が得られること() { sut.add(s); String actual = sut.toString(); String expected = s.toString(); assertThat(actual, is(expected)); } @Test public void addした際に元の集合から変化があるとtrueを返すこと() { boolean actual = sut.add(s); boolean expected = true; assertThat(actual, is(expected)); } } }
修正メソッド
public boolean add(IntSet s) { boolean changeFlg = false; for (int i = 0; i < s.num; i++) { changeFlg = add(s.set[i]) || changeFlg; } return changeFlg; }
- 2点修正。
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る
JUnit実践入門 ~体系的に学ぶユニットテストの技法 (WEB+DB PRESS plus)
- 作者: 渡辺修司
- 出版社/メーカー: 技術評論社
- 発売日: 2012/11/21
- メディア: 単行本(ソフトカバー)
- 購入: 14人 クリック: 273回
- この商品を含むブログ (65件) を見る
15分ぐらいかなーって思ったら30分かかった/(^o^)\
10分でコーディング|プログラミングに自信があるやつこい!!の問題やってみた。
ツメの部分の見積もりが甘い。 わしゃまだまだじゃな・・・ がんばろー
15分ぐらいかなーって思ったら30分かかった/(^o^)\ http://ameblo.jp/pro ...
こんなかんじに出力されますん。
numPlayers: 2
deck: 1543
deal :
"14", "53",
numPlayers: 8
deck: 12345678
deal :
"1", "2", "3", "4", "5", "6", "7", "8",
numPlayers: 3
deck: 1234
deal :
"1", "2", "3",
numPlayers: 4
deck: 123
deal :
"", "", "", "",