アルゴリズム

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