简单算法的优化

Question

我有个问题：

考虑到两个慢跑者跑的圈的长度(相同的速度)，返回#的圈数。每个人必须在同一时间到达起点之前跑。

这个代码是：

def nbr_of_laps(x, y)
  result = []
  lcm = 1
  until lcm % x == 0 || lcm % y == 0
    lcm +=1
  end
  result << (lcm/x, lcm/y)
  return result 
end

这需要超过12秒才能执行。你能告诉我为什么这段代码效率这么低吗？

Answer 1

设d1和d2分别为正整数，分别等于跑步者1和2的一圈长度，我们是两者的速度。在不失去一般性的情况下，假设s= 1。

在时间t= d1*d2时，跑步者1已经完成( d1 * d2 *s)/d1 =d2圈，跑步者2已经完成(d1*d2*s)/d2 =d1圈。由于d1、d2和s都是正整数，所以此时t都跨越了终点线。

设n等于d1和d2的最小公倍数。然后d1 = n1*n和d2 = n2*n，其中n1、n2和n都是正整数。现在t=n跑步者1完成了d1/n = n1圈，2已经完成了d2/n = n2圈。因为n1和n2都是正整数，所以这是两个跑步者穿越终点线的上界。(请注意，n <= d1*d2.)

现在假设有一个时间t，t< n，在这个时刻，双方都越过终点线。跑步者1完成t/d1圈，2完成t/d2圈。但是，由于t不是d1和d2的倍数(因为它小于这些数字中最不常见的倍数)，因此建立了一个矛盾(也就是说，两个跑步者在t时完成一个整数圈数被证明是假的)。因此，我们得出的结论是，d1和d2最不常见的倍数是第一次两个跑步者同时穿越终点线。

这当然是微不足道的实现。

def nbr_laps(d1, d2)
  t = d1.lcm(d2)
  { player1: t/d1, player2: t/d2 }
end

nbr_laps(1, 2)              #=> {:player1=>2, :player2=>1}         lcm = 2
nbr_laps(2, 6)              #=> {:player1=>3, :player2=>1}         lcm = 3
nbr_laps(12, 60)            #=> {:player1=>5, :player2=>1}         lcm = 5
nbr_laps(132, 164)          #=> {:player1=>41, :player2=>33}       lcm = 5412
nbr_laps(123_456, 345_678)  #=> {:player1=>57613, :player2=>20576} lcm = 7112670528

见Integer#lcm。