アルゴリズム
[ Ruby ]
http://blog.livedoor.jp/dankogai/archives/50957658.htmlをよんで。
メルセンヌ・ツイスタ以外は理解してたはずなのにけっこう忘れてる。ということで思い出すために実装してみます。Rubyで。
ユークリッドの互除法
実装自体はとても簡単。aとbの最大公約数を求めるgcd(a,b)は次のようにかけます。
def gcd(a, b)
b, a = [a,b].sort
until b == 0
a, b = b, a%b
end
a
end
それより、「なぜこれで最大公約数が求まるのか」は、それほど直感的じゃありません。
整数A, B、ただしA > Bがある。 GCD(x, y)は、xとyの最大公約数とする。 A/Bの商がQ、剰余がRとする。Q,Rは整数。 このとき、 A = B * Q + R ... (1) したがって R = B*Q - A ... (2) C= GCD(A,B)とすると、(2)の右辺はB*Q - AはCで割り切れる。 したがって、(2)の左辺RもCで割り切れる。よって、ＣはRの約数。つまり、 C = GCD(A,B) <= GCD(B,R) ... (3) ここでGCD(B,R) = C'とする。 (1)の右辺はC'で割り切れる。したがって左辺AもC'で割り切れる。 つまり、C'は、A,Bの公約数。 したがって、 C' =GCD(B,R) <= GCD(A,B) ... (4) (3),(4)から、GCD(A,B) = GCD(B,R)。
ここでひといき。ここまでで、「AとBの剰余がRであるとき、GCD(A,B)=GCD(B,R)である」といえます。AがBで割り切れるまでこの操作を続ければ、そのうちGCD(A,B) = GCD(B,0)になります。GCD(B,0)は明らかにBです。
こりゃ証明の形になってないですね。この繰り返しを証明の形で記述するにはどうするんだっけ。思い出せないや。
エラトステネスの篩
なんか不格好な実装
def primes(n)
searchlist = (2..n).map
primelist = [ 1 ]
while searchlist.last > primelist.last **2
p = searchlist[0]
primelist << p
searchlist = searchlist.find_all { | x | x % p > 0 }
end
primelist + searchlist
end
バイナリサーチ
def binarySearch(arr, n)
if (arr.length < 1)
return nil
end
p = arr.length / 2
case n <=> arr[p]
when -1 then return binarySearch(arr[0,p], n)
when 0 then return n
when 1 then return binarySearch(arr[p+1, arr.length - p],n)
end
end
