最大公約数
一昨日の続きです．今日は，２つの数を素因数分解し，共通する因数を得て演算し，最大公約数を得る，というメソッド(というと語弊があるけど)を考えてみました．
配列の共通する要素
まず，どのようにして共通する要素を求めるか？普通は，「そんなの，and演算すりゃ良いじゃないか」と考えます．しかし，それでは少し困った事があります．
とりあえずand演算から考えてみます．
> [2,2,3] & [2,3,3] # 12と18を素因数分解したもの => [2, 3]
これだと，問題無いですね．2,3だけでいいですから．しかし，次の場合，
> [2,2,3] & [2,2,2,3] # 12と24 => [2, 3]
これだと，最大公約数は12なのに，結果を演算した時に12ではなく6になってしまいます．そこで，and演算を自分流に作ります．
class Array
def my_and(other)
arr = []
nother = other.dup
self.each{|e|
if nother.include? e
nother.each_index{|i|
if nother[i] == e
arr.push e
nother.delete_at(i) # 要素を消す
break
end
}
end
}
arr
end
endselfの要素を一つ一つ見ていって，ohterをdupして得られたnotherに同じ要素が含まれているか調べ，含まれていたらその要素をarrにpush，notherから削除し，selfの次の要素を見ます．頑張って脳でイメージしてください．説明が上手く出来ません．
実行すると，こんな感じです．
> [2,2,3].my_and [2,2,2,3] => [2, 2, 3]
望み通りの結果が得られました．
共通する素因数
とりあえず，これでand演算の問題は解決しました．次は，２つの数から共通する素因数を得ます．
これはもう簡単で，
class Integer
def comfact(other)
a1 = self.factor
a2 = other.factor
a1.my_and a2
end
end
>12.comfact 24
=> [2, 2, 3]factorメソッドに関しては，一昨日のを参照してください．一応，下にソースを載っけてありますが．
最大公約数
さて，やっと最大公約数です．考え方としては，comfactによって得られた配列を，ひたすらに掛ければ良いかしら．
class Integer
def maxcomfact(other)
m = 1
self.comfact(other).each{|e|
m *= e
}
m
end
end
> 12.maxcomfact 24
=> 12お，なんか動いてるっぽい．
色々試してみた感じ，なんとか動きました．とりあえず完成．ただ，２項だけしか演算できない訳だから，今度は配列に対してやってみるか．
以下，とりあえず完成版のソースを載せます．
class Array
def my_and(other)
arr = []
nother = other.dup
self.each{|e|
if nother.include? e
nother.each_index{|i|
if nother[i] == e
arr.push e
nother.delete_at(i)
break
end
}
end
}
arr
end
end
class Integer
def prime?
return false if self < 2
(2 ... self).each{|x|
# 割り切れたら素数じゃない
return false if self % x == 0
}
true
end
def factor
primes = []
# 素数なら配列に突っ込んで返す
return primes.push(self) if self.prime?
# 1以下の数なら素因数分解出来ないので空の配列を返す
return primes if self < 2
n = self
# 2から順番に，素数で割っていく
(2 ... n).each{|p|
if p.prime?
while n % p == 0
primes.push(p)
n = n / p
end
end
break if n == 1
}
primes
end
def comfact(other)
a1 = self.factor
a2 = other.factor
a1.my_and a2
end
def maxcomfact(other)
m = 1
self.comfact(other).each{|e|
m *= e
}
m
end
end
楽しいわぁ．
