2つの数字の倍数の和であるnの最も近い次の数字の検索

Question

与えられた数字nに対して、2つの与えられた数字（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について解くと、この問題を考え、私はこのような何かを始めるでしょう

Answer 1

Xa + Yb >= nとX, Y > 0：

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

、私はそれが非常に非効率的なソリューションですかなり確信していますが、ここでは1番目です私は仕事を信じています。それは2の分岐要因と再帰を使用しています。

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) 

：便宜上

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

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

出力は、ここにあなたのポストの例では、と比較します

私の解決策は、 2番目の例では倍数の組み合わせですが、diffは依然として0です。