2008年08月20日(水)
超有名な最大公約数を求めるアルゴリズム。
その理論はともかく、rubyで書くなら
さらに短く
大きい数で小さい数を割った値を求めても時間が余計にかかるだけで計算に影響はないだろうから、さらに短く。
こんなもんですかね？Cなら
それにしても紀元前にこのアルゴリズムを考えたユークリッドはすごいわ
def gcd(a, b)
while true
if a > b
a %= b
return b if a == 0
else
b %= a
return a if b == 0
end
end
end
さらに短く
def gcd(a, b)
while true
if a > b
return b if (a %= b) == 0
else
return a if (b %= a) == 0
end
end
end
大きい数で小さい数を割った値を求めても時間が余計にかかるだけで計算に影響はないだろうから、さらに短く。
def gcd(a, b)
while true
return b if (a %= b) == 0
return a if (b %= a) == 0
end
end
こんなもんですかね？Cなら
int gcd(int a, int b)
{
while(1){
if(!(a %= b))
return b;
if(!(b %= a))
return a;
}
}
それにしても紀元前にこのアルゴリズムを考えたユークリッドはすごいわ
