找到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) 

我该如何解决这个问题？

我所写的是：（在红宝石）

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的方程 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 

Answer 2

，我坚信这是一个非常低效的解决方案，但这里的第一个在我相信的作品。它采用递归为2的分支因子：

def recurse(a_base, b_base, a_mult, b_mult, n): 
    a = a_base * a_mult 
    b = b_base * b_mult 

    if a + b >= n: 
     return (a + b) - n, a_mult, b_mult 
    else: 
     diff_1, a_mult_1, b_mult_1 = recurse(a_base, b_base, a_mult + 1, b_mult, n) 
     diff_2, a_mult_2, b_mult_2 = recurse(a_base, b_base, a_mult, b_mult + 1, n) 

     if diff_1 <= diff_2: 
      return diff_1, a_mult_1, b_mult_1 
     else: 
      return diff_2, a_mult_2, b_mult_2 


def find_next_num_diff(a, b, n): 
    return recurse(a, b, 0, 0, n) 


if __name__ == '__main__': 
    print(find_next_num_diff(13, 17, 49)) 
    print(find_next_num_diff(2, 5, 16)) 
    print(find_next_num_diff(13, 17, 25)) 

输出

# Smallest diff, multiple of a, multiple of b 
(2, 0, 3) 
(0, 8, 0) 
(1, 2, 0) 

为了方便起见，这里是在您的文章中的例子来比较：

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) 

请注意，我的解决方案产生了不同的结果第二个示例的倍数组合，但diff仍然为0.