日常を2014年8月13日水曜日グラフ関係のコードいくつかようやく大学が夏季休業に入ったので、学校で使った離散数学の本読んでグラフ理論とオートマトンの勉強をしている。グラフ理論の部分で出てきたアルゴリズムとかでコード書いたのでいくつか。algorithmまずはBellman-Ford法。これは本には出てこなかったけど、Dijkstra法は書いたことあるのにBellman-Ford法は書いた事ないなぁと思った程度のアルゴリズム力なので、とりあえず書いてみた。一応無向グラフ想定して書いたけど、ちょっと変えれば有向グラフにも適用出来る......はず。一応辺は行列で表現してるので。algorithm次にKruskal法。同じ木に属しているかどうかはUnion-Find木で書けるので、本の通りにいけば、まずは辺をコストでソートして、小さい辺から、その辺が連結でない2つの木を連結するならば、最小全域木の辺として加えていくというアルゴリズム。Notationアルゴリズムではないけども、逆ポーランド記法をプログラミング3年目?にしてようやく実装したので。ある数式を表す木構造を考えるときに、木の各頂点に番号を付けることを考えると、プリオーダーとポストオーダーという2つの方法が考えられる。プリオーダーって言うのは、自分自身、左の子ノード、右の子ノードの順に再帰的に番号を付けていく方法で、このやり方だと式木はポーランド記法になる......はず。ポストオーダーは左の子ノード、右の子ノード、自分自身の順に番号をつけていく方法で、このやり方だと式木は逆ポーランド記法になる。実装の方法としては、入力をスペース区切りの数字、演算子の列だとして、数字が来たらスタックにそのままプッシュ、演算子が来たら右、左の順にスタックから取り出した値を子ノードとして割り当てて、演算子を根とした木構造にしてスタックにプッシュ。最後にスタックに残った木を取り出すと、これが式木になってる。後はまぁコードの通りに各頂点ごとの値を計算するだけ。グラフは(まだフローとかあるけど)ひと通り分かった......と思うので、次はオートマトンのあたりで何かしらコードを書きたい。(Atom)rigibunプログラミング歴3年くらい。世界一プログラミングが出来ない。D言語を使って大抵の計算をコンパイル時に終わらせたい。Javaについては基礎文法すら怪しい。数学をやりつつ低レイヤも少しさわろうと思ってる。