線形合同法による疑似乱数生成器をRubyで書きました。 class LinearCongruentialRandom A = 1812433253 def initialize(seed=314159) @state = seed end def next(max) @state = A * @state + 1 @state % max.to_i.abs end end r = LinearCongruentialRandom…

M. D. MacLarenとG. Marsagliaによって提案された、擬似乱数アルゴリズムを「改良」する（と言われている）「かき混ぜ法」です。 課題：maxの扱い 課題：インタフェースを定め、Decoratorパターンに。 class LinearCongruentialRandom A = 1812433253 def in…

昔懐かし(?)チェックサムを表示するプログラムです。 class ChecksumPrinter def initialize(io, columns = 16, rows = 16) @columns, @rows = columns, rows @buffer_size = @columns * @rows @sums = Array.new(@buffer_size) @io = io @io.binmode end de…

指定したビット数のグレイコード表を作ります。 def gray_table(n) fmt = sprintf("%%0%db\n", n) (0...(1 << n)).each do |i| printf(fmt, i ^ (i >> 1)) end end gray_table(5)実行結果です。 00000 00001 00011 00010 00110 00111 00101 00100 01100 0110…

Rubyでバイナリサーチを実装しました。本来はSortedListクラスのメソッドのような気もしますが、とりあえず関数風味で♪ def bsearch(sorted, target, if_none = nil, &cmp) cmp ||= proc { |a, b| a <=> b } left, right = 0, sorted.length while left < ri…

Rubyでクイックソートを作ってみました。シンプルな仕上がり♪ qsortとqsort!を作りました。 比較関数をブロックで与えることができます。 与えられなかったらを使います。 課題: callではなくyieldを使う版 課題: 非再帰版 class Array def qsort(&cmp) self…

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オプションでグローバル変数$DEBU…

Rubyで「エラトステネスの篩」を実装しました。単純な版♪ def sieve(m) prime = (0..m).to_a (2..m).each do |p| next if not prime[p] yield(p) if block_given? (p+p..m).step(p) do |k| prime[k] = false end end prime[2..m].find_all {|p| p} end sieve…