ρヒューリスティック - rubyco（るびこ）の日記
大きな数の因数を発見的に求めるρ法（Pollardのρヒューリスティック）をRubyで実装しました。 # 2個の素数の積を因数分解する def factor_two(given) start = Time.now one = rho(given) another = given / one elapsed = Time.now - start puts "#{given} = #{one} * #{another} (#{elapsed} sec)" end # 『アルゴリズムイントロダクション』第3巻p.196 # 「Pollardのρヒューリスティック」で因数を探す def rho(n) i = 1 x = rand(n) y = x k = 2 loop do i += 1 x = (x * x - 1) % n f = n.gcd(y - x) if f != 1 and f !=
ユークリッドの互除法 - rubyco（るびこ）の日記
Rubyで「ユークリッドの互除法」を実装しました。最古のアルゴリズム♪ def euclid(m, n) loop do puts "m = #{m}, n = #{n}" if $DEBUG r = m % n return n if r == 0 m, n = n, r end end p euclid(60, 42)実行結果です。-dオプションでグローバル変数$DEBUGがtrueになります。 > ruby euclid.rb 6 > ruby -d euclid.rb m = 60, n = 42 m = 42, n = 18 m = 18, n = 6 6 Based on: 「C#で学ぶアルゴリズムとデータ構造」アルゴリズムとは何か、データ構造とは何か
クイックソート - rubyco（るびこ）の日記
Rubyでクイックソートを作ってみました。シンプルな仕上がり♪ qsortとqsort!を作りました。 比較関数をブロックで与えることができます。 与えられなかったら<=>を使います。 課題: callではなくyieldを使う版 課題: 非再帰版 class Array def qsort(&cmp) self.dup.qsort!(&cmp) end def qsort!(&cmp) cmp ||= lambda { |a, b| a <=> b } sort_between(0, length - 1, &cmp) end def sort_between(low, high, &cmp) return self if high <= low pivot = self[(low + high) / 2] left = low right = high loop do left += 1
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
