問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1215文字列といくつかの文字が与えられる。 文字をすべて含む、文字列の部分列の中で最小の長さのものの個数と、そのような部分列のなかで最初に現れるものを出力せよ。 尺取り法のような…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1257連続する素数の和でnを作る場合の数を求めよ。 素数の数が1000くらいしかなかったので尺取り法した。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ bool prim[10</algorithm></vector></iostream>…

文字列aとbの編集距離を求めるプログラムを書いた。 wikipediaの擬似コード↓を参考にした。 http://en.wikipedia.org/wiki/Levenshtein_distance文字の挿入や削除、置換によって一つの文字列を別の文字列に変形するのに必要な手順の最小回数を編集距離という…

問題文 http://uva.onlinejudge.org/external/101/10168.htmlnを4つの素数の和で表す。その表し方のうちの一つを出力せよ。不可能な場合は"Impossible."と出力せよ。 http://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%90%E3%83%83%…

真ん中の要素をピボットにするクイックソートに非常に計算量が多くなりそうなケースを与えてみた。 クイックソートは http://www.prefield.com/algorithm/sort/quicksort.html ↑spaghetti source様から拝借しました。↓は要素数nとソートしたい要素を与えると…

モンテカルロ法で図形の面積を求めることができる。x*x/4+y*y=1 の式で示される楕円の面積をモンテカルロ法で求める。乱数 0≦x≦2 , 0≦y≦1 を2×1の長方形の中に均一に落とす。 1/4の楕円の中に入った乱数の数をr 落とした乱数の総数をn 1/4の楕円の面積をSと…

モンテカルロ法で円周率を求めるプログラムを簡単に書いてみた。 円周率の計算にはもっとよい方法があるのでこの方法は使われていない。1辺の長さが1の正方形とそれに内接する4分の1円(扇形)がある。正方形の面積 : 扇形の面積 = 1 : π / 4この正方形のなか…