algorithm - 为 n 找到最近的下一个数字，以及 2 个数字的倍数之和

Question

对于给定的数字 n，找出下一个最接近的可以由两个给定数字 (a,b) 和 n 的倍数组成的数字之间的差值。

Example:
    n = 49, (a, b) = (13, 17) => Difference = 2
    Nearest number would be = 51 (3*17, 0*13)

    n = 16, (a, b) = (2 , 5) => Difference = 0
    Nearest number would be = 16 (2*5, 3*2)

    n = 25, (a, b) = (13, 17) => Difference = 1
    Nearest number would be = 26 (0*17, 2*13)

我该如何解决这个问题？

我写的是:( ruby )

def find_next_num_diff(x,y,z)
  x, y = x > y ? [x, y] : [y, x]
  while(z%y > 0 && z >= x) do
    z -= x
  end
  if z%y == 0
    return 0
  else
    return [y-(z%y), x-z].min
  end
end

以上代码不适用于最后一种示例。

编辑: 没有负数。而且只有总和。 起初我认为这个问题是求解 X & Y for Equation Xa + Yb >= n 和 X, Y > 0

Answer 1

我会从这样的事情开始:

def find_next_num_diff(n, a, b)
  multiples_of_a = (0..n+a-1).step(a).to_a
  multiples_of_b = (0..n+b-1).step(b).to_a

  multiples_of_a.product(multiples_of_b).map { |x, y| (n - (x + y)).abs }.min
end

find_next_num_diff(49, 13, 17)
#=> 2
find_next_num_diff(16, 2, 5)
#=> 0
find_next_num_diff(25, 13, 17)
#=> 1

或者您可能希望使用以下需要较少内存的实现，因为它不会将笛卡尔积存储在内存中:

def find_next_num_diff(n, a, b)
  a_multiples = (0..n+a-1).step(a)
  b_multiples = (0..n+b-1).step(b)

  smallest = Float::INFINITY

  a_multiples.each do |x|
    b_multiples.each do |y|
      smallest = [smallest, (n - (x + y)).abs].min
    end
  end

  smallest
end