アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのよう…

longの乱数が欲しかったのは、素数判定がやりたかったからなのですが、確認のためにエラトステネスの篩との比較をしたので、結局intの範囲までしか使いませんでした。 素数判定には、フェルマーテストを使います。で、今回は、わざと判定回数を少なくしてみ…

結局、乱数が一様であれば、それを分割した部分も一様になるはずなので、基本的にはgetLong() % nで大丈夫そうです。ただ、そうするとlongの範囲が割り切れなかった部分で、乱数にムラができるので、考慮する必要があります。 で、結局そうすると、nがintの…

さて、これで求めたい文字列が得られたわけですが、ここでアルゴリズムとして全ての順列について検査しているので、計算時間がO(n!)になってしまいます。 そこで、これを線形時間、つまり、入力文字列数nと出力文字列数mに比例した計算時間O(mn)になるように…

こないだの問題。 http://d.hatena.ne.jp/nowokay/20080717 Javaで書くとこんな感じか。 public class SBH { public static void main(String[] args){ sbh(new String[]{"BAB", "ABA", "AAB", "AAA", "BAA"}); sbh(new String[]{"BAB", "AAB", "AAA", "BAA"…

文字列の集合{ BAB, AAB, BAA, AAA, ABA }があるとき、これらのすべてを1回ずつ含み、かつ、3文字の部分文字列としてはこれらの文字列しか含まない文字列は、BABAAABとBAAABABの２通りある。 文字列の集合が{ BAB, AAB, BAA, AAA }のときは、そのような条件…

凸包を求めるアルゴリズム、最後にjarvisのマーチという方法をやってみます。 考え方としては、まず最初にy座標が一番小さいものを選んで、その点からの角度が一番小さい点を選んでいきます。 角度は内積で求めます。 このアルゴリズムの場合、凸包上の頂点…

前回のアルゴリズムでは、点の数分のループが４重になっていたので、計算時間がO(n^4)になってしまいます。 ということで、別のアルゴリズム。 ここでは、上側の凸包と下側の凸包をわけて取得します。上側の凸包をとるには、点をX座標でソートしておいて、連…

前回のようなランダムな点があったとき、その点を全部含んでへこみのない多角形を作成するという問題。 アルゴリズムとしては、「他の点でできる三角形に含まれてたら凸包上の点じゃない」という考え方で、全部の組み合わせの三角形について全部の点を走査し…

とりあえず。 public class RandomPoint extends JComponent{ @Override protected void paintComponent(Graphics g) { g.setColor(Color.WHITE); g.fillRect(0, 0, 400, 350); g.setColor(Color.BLACK); for(int i = 0; i < xs.size(); ++i){ g.drawOval(10…

例えば次のようなランダムな数列(同じ数字はない)から昇順になっている数列を抽出する。 2 0 5 7 1 3 9 6 4 8 そうすると 2 5 7 9 とか 0 1 3 4 8 とかが得られる。そういう数列の中で、もっとも長いものを得る。 public static void main(String[] d){ //ラ…