在数学中,两个或多个整数的最大公约数(gcd),当其中至少一个不为零时,是能够整除这些数字而没有余数的最大正整数。例如,8和12的GCD是4。维基百科
以下方法能够确定GCD:
def gcd(a, b)
if a % b == 0
b
else
gcd(b, a % b)
end
end
p gcd(4, 12)
#=> 4
这个方法是如何工作的?
如果a%b == 0
,那么b
就是可以同时被a
和b
整除的最大数,这是有道理的。
但为什么要再次调用相同的方法,交换参数并再次取模呢?
我不明白else
部分的原因。
编辑:
添加一些puts
语句以使其更清晰:
def gcd(a, b)
puts "Inside gcd, a: #{a}, b: #{b}, a \% b: #{a % b}"
if a % b == 0
puts "Inside if, a: #{a}, b: #{b}, a \% b: #{a % b}"
b
else
puts "Inside else, a: #{a}, b: #{b}, a \% b: #{a % b}"
gcd(b, a % b)
end
end
p gcd(55, 105)
标准输出:
Inside gcd, a: 55, b: 105, a % b: 55
Inside else, a: 55, b: 105, a % b: 55
Inside gcd, a: 105, b: 55, a % b: 50
Inside else, a: 105, b: 55, a % b: 50
Inside gcd, a: 55, b: 50, a % b: 5
Inside else, a: 55, b: 50, a % b: 5
Inside gcd, a: 50, b: 5, a % b: 0
Inside if, a: 50, b: 5, a % b: 0
5
puts
语句以查看它的运行情况?有趣的是,Ruby 内置了12.gcd(4)
函数。 - akuhn