最大公約数（除算禁止）
Posted feedbacks - Ruby
２数の差が大きい時もわりと早く収束するかな。 結果[1, 3994]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | require "mathn"
class Fib
def initialize
@fib_a=[1,1]
end
def [](n)
(@fib_a.size..n).each{|i| @fib_a<<=@fib_a[i-2]+@fib_a[i-1]}
@fib_a[n-1]
end
end
def gcd(n,m)
c=0
until(n==m)
n,m=m,n if n<m
return [1,c] if m==1
m1=m
while(m1<n)
m1<<=1
c+=1
end
m1>>=1
n-=m1
c+=1
end
[n,c]
end
fib=Fib.new
p gcd(fib[2000],fib[1999])
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]