math.hのsqrt(f)を使わずに整数の平方根を求めてみた。(intが4byteであるマシンでのみ動作) sqrtmod0はアルゴリズム上0x40000000以上の値の平方根を計算でようなので、0x40000000以上の値はKaratsuba開平を利用して求めている。↓は乱数で平方根と余りを求め…

検証用に使っていた物です。 len = ARGV[0].to_i B = 10 ** len B2 = B << 1 pi = (len * 8 + 1).step(3, -2).inject(B) {|a, i| (i >> 1) * (a + B2) / i} - B puts "3.#{pi}" # time ruby pi.rb 100 3.14159265358979323846264338327950288419716939937510…

何も見ないでマージソートを書いてみた。 初め int *tmp = new int[num]; で、マージするための領域用意したのに if(j >= num || (i < left && array[i] < array[j]))array[k++] = array[i++]; else array[k++] = array[j++]; と書いていて、tmpのコピーも開…

何も見ないでクイックソートを書いてみた（汗 while(i < num && array[i] < s)i++; while(j >= 0 && array[j] >= s)j--; の、各whileの1つ目の条件抜けてて、結構ハマった。。。。 ソース void quickSort(int *array, int num){ if(num < 2)return; int i = …

大分前の話だが、赤黒木の削除もできたのでそのうちソース公開

挿入はできたが、削除がまだ。。。 参考 http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html http://ja.wikipedia.org/wiki/%E5%88%A9%E7%94%A8%E8%80%85:Yutaochi/translating/%E8%B5%A4%E9%BB%92%E6%9C%A8 http://www.ececs.uc.edu/~fra…

CだとC++と違ってが使えないので、別のデータを格納するハッシュを利用するには、それ専用のソースを用意する必要がある。 そこで、Ruby等で使われているst_tableを参考に、柔軟なHashを自分なりに一から作ってみた。突っ込み、機能拡張大歓迎。一応一通りメ…

『Maximum Winter Contest 2008』のH問題 http://maximum.vc/PastProblems/Winter-Contest-2008/h/h.htmlエラストテネスの篩で2-16までのテーブルを作って、ユークリッドの互除法(GCD)で求めたものがソスウ化判定するだけ #include <iostream> #include <vector> #include <math.h> usi</math.h></vector></iostream>…

『Maximum Winter Contest 2008』のE問題 http://maximum.vc/PastProblems/Winter-Contest-2008/e/e.htmlダイクストラだけど・・・ 『複数の異なる高さのマスが接する境界上の点の高さは、それらのうち最も高いマスの高さとする。』が罠！ #include <iostream> using n</iostream>…

『Maximum Winter Contest 2008』のA問題 http://maximum.vc/PastProblems/Winter-Contest-2008/a/a.htmlしっかり仕様を実装すればOK #include <string> #include <iostream> using namespace std; int main(){ int n, i, j; char word[1024][100], c; while(cin >> n, n){ for</iostream></string>…