Как бы я разделил данное значение только с двумя числами?

Question

Я должен разделить число, введенное пользователем, используя, например, только 5 и 3 - Если пользователь введет 25, я получу пять 5 монет, чтобы получить это значение, но если пользователь введет 111, мне нужно будет получить двадцать одна 5 монет и две 3 монеты.

Мы пытаемся получить значение, введенное пользователем, если пользователь введет 112, мы будем использовать 20 пятерок и 4 тройки

Мое решение до сих пор это было

puts "How much are you buying?"
x = gets.to_f

case
when x / 5 
x = x/ 5
when x / 3
  x = x / 3
end
 puts x

, но это не правильный способ сделать это, и я немного застрял, заранее спасибо за помощь

Answer 1

Чтобы вычислить значения, которые вы запрашиваете, вы должны сначала спросить себя, как решить проблему без языка программирования. В этом случае это можно сделать, выполнив следующие действия:

1. Уменьшите входной номер на 3, пока итоговое число не опустится ниже 0 или пока число не может быть делится на 5. Подсчитайте, сколько раз это можно сделать.
2. Подсчитайте, как часто результирующее значение можно разделить на 5.

Это может быть обработано в Ruby следующим образом :

def calc(number)
  threes = 0
  until number < 3 || (number % 5).zero?
    number -= 3
    threes += 1
  end

  fives, rest = number.divmod(5)

  [fives, threes, rest]
end

calc(111) #=> [21, 2, 0]
calc(112) #=> [20, 4, 0]

Этот ответ предполагает абсолютный ввод (ноль или выше).

Answer 2

Итак, из того, что вы говорите, я понимаю, что вам нужен метод, который выглядит примерно так:

def get_change(number)
  rest = number % 5
  puts " 5x#{number / 5} 3x0" if rest == 0
  puts " 5x#{(number / 5) - 1} 3x2" if rest == 1
  puts " 5x#{(number / 5) - 2} 3x4" if rest == 2
  puts " 5x#{number / 5} 3x1" if rest == 3
end

Я знаю, что код уродлив и может быть изменен, если я хочу показать вам идею, что вы хотите достичь. Я думаю, что поможет. Не уверен, что код работает на 100% так, как вы хотите, но вы хотя бы представляете, что и как нужно делать.

Answer 3

Проблема

Я предполагаю, что вопрос заключается в следующем: «дано положительное целое число tot и массив пар положительных чисел

arr = [[a1,m1], [a2,m2],...,[ai,mi],...,[aN,mN]]

мы sh найдем неотрицательные числа n1,n2,...,nN такие, что

n1*a1 + n2*a2 +...+ nN*aN = tot

и

mi <= ni, i = 0,...,N

, или сделаем вывод, что таких чисел ni не существует (не может внесите точные изменения). Предположим, что

tot = 104
arr = [[25,4],[10,5],[5,1],[3,4]]

arr будет интерпретироваться как создатель изменений, имеющий 4 четверти, 5 центов, 1 никель и 4 трея, а «три» - монета достоинством 3 цента. .

Одним из решений будет:

n0 = 3
n1 = 2
n2 = 0
n3 = 3

as

3*25 + 2*10 + 0*5 + 3*3
  #=> 104

На самом деле решить эту проблему не сложнее, чем та, где нет ограничений на номера каждой доступной монеты.

Подход, который необходимо принять

Простой подход состоит в том, чтобы рассмотреть все комбинации 0..m1, 0..m2,...,0..mN, ища комбинацию, которая имеет значение tot. Для arr выше это будет:

(4+1)*(5+1)*(1+1)*(4+1)
  #=> 300

комбинаций. Это легко управляемо, конечно e, но если было доступно 10 монет и 9 из каждой монеты, которые могли бы генерировать 10**10 комбинаций.

Они другой подход, который я представляю ниже, - это рассматривать его как проблему динамического программирования c, этапы - монеты, а состояния - оставшееся количество изменений, которые необходимо внести. Сложность вычислений для этого подхода составляет O (tot*(m1+m2+...mN)).

Код

def make_change(tot, arr)
  return nil if tot.zero?
  chg = arr.each_with_object([tot=>0]) do |(coin, nbr_avail),a|
    if a.last.key?(0)
      a << { 0=>0 }
    else  
      a << hash_for_coin(coin, nbr_avail, a.last)
    end
  end
  return nil unless chg.last.key?(0)
  chg.shift
  recover_solution(arr, chg)
end

def hash_for_coin(coin, nbr_avail, last_coin) 
  last_coin.each_with_object({}) do |(k,v),h|
    (0..nbr_avail).each do |n|
      break if n*coin > k
      h[k-n*coin]=n
    end
    return { 0=>h[0] } if h.key?(0)
  end
end

def recover_solution(arr, change)
  return nil if change.nil?
  remaining = 0
  (arr.size-1).downto(0).with_object({}) do |i,h|
    coin = arr[i].first
    nbr = change[i][remaining]
    h[coin] = nbr
    remaining += coin*nbr
  end
end

Примеры

arr = [[25,4],[10,5],[5,1],[3,4]]

change = make_change(104, arr)
  #=> {3=>3, 5=>0, 10=>2, 25=>3} 
change = make_change(85, arr)
  #=> {3=>0, 5=>0, 10=>1, 25=>3} 
change = make_change(7, arr)
  #=> nil       

arr = [[1000,6],[100,7],[25,6],[10,4],[5,2],[3,4]]

change = make_change(5863, arr)
  #=> {3=>1, 5=>0, 10=>1, 25=>6, 100=>7, 1000=>5}
change = make_change(5972, arr)
  #=> nil

Объяснение

Обратите внимание, что метод возвращает решение, как только он находит один.

Для первого примера выше (make_change(104, arr)) было обнаружено, что значение chg непосредственно перед выполнением recover_solution(arr, chg) было следующим:

chg
  #=> [{104=>0, 79=>1, 54=>2, 29=>3, 4=>4},
  #    {104=>0, 94=>1, 84=>2, 74=>3, 64=>4, 54=>0, 79=>0, 69=>1,
  #      59=>2, 49=>3, 39=>4, 29=>0, 44=>1, 34=>2, 24=>3, 14=>4, 
  #       4=>0, 19=>1,  9=>2},
  #    {104=>0, 99=>1, 94=>0, 89=>1, 84=>0, 79=>0, 74=>1, 69=>0,
  #      64=>1, 59=>0, 54=>1, 49=>0, 44=>0, 39=>1, 34=>0, 29=>1, 
  #      24=>0, 19=>0, 14=>1, 9=>0, 4=>1},
  #    {0=>3}]

Давайте сначала рассмотрим chg[0], что соответствует четвертям:

chg[0]
  #=> {104=>0, 79=>1, 54=>2, 29=>3, 4=>4}

Это говорит нам о том, что из общего числа 104, 104 остается изменить, если используются 0 четверти, 79 остается, если используется одна четверть (104-25) и т. Д.

Следующая проверка chg[1], за 10 центов:

chg[1] = 
  #=> {104=>0, 94=>1, 84=>2, 74=>3, 64=>4, 54=>0, 79=>0, 69=>1,
  #     59=>2, 49=>3, 39=>4, 29=>0, 44=>1, 34=>2, 24=>3, 14=>4,
  #      4=>0, 19=>1, 9=>2}

Это говорит о том, что 104 можно оставить используя ноль центов, 94 можно оставить, используя 1 цент, и так далее. Рассмотрим 19=>1, который говорит нам, что 19 можно оставить, если использовать 1 цент. Добавление 10 к 19 говорит нам, что баланс был 29 до применения этого одного цента. Теперь мы видим, что chg[0][29] #=> 3, что говорит нам о том, что 3 четверти были использованы в дополнение к одному центу, чтобы уменьшить общее количество до 19.

На никелях!

chg[2]
  #=> {104=>0, 99=>1, 94=>0, 89=>1, 84=>0, 79=>0, 74=>1, 69=>0, 64=>1,
  #     59=>0, 54=>1, 49=>0, 44=>0, 39=>1, 34=>0, 29=>1, 24=>0, 19=>0,
  #     14=>1, 9=>0, 4=>1}

Давайте посмотрим на 49=>0, что означает, что 49 можно изменить, если ники не используются. Мы видим, сколько центов и четвертей было использовано следующим образом:

chg[1][49+0*5]  #=> chg[1][49] #=> 3 dimes
chg[0][49+10*3] #=> chg[0][79] #=> 1 quarter

Можно ли было использовать 1 никель? Конечно! Начиная с 104-49 = 55 мы могли бы вместо этого использовать 2 четверти, без десяти центов и один никель. Проверьте это:

chg[1][49+1*5]  #=> chg[1][54] #=> 0 dimes
chg[0][54+0*10] #=> chg[0][54] #=> 2 quarters

Фактически, во время вычислений одно время chg[2][49] равнялось бы 1 и позже перезаписывалось на 2, только потому, что было проще перезаписать значение, чем проверьте, есть ли у chg[2] ключ 49, и оставьте значение без изменений, если оно есть (в любом случае работает). В более крупных задачах значения ключей могут многократно перезаписываться, что препятствует экспоненциальному расширению вычислений.

Наконец, мы смотрим на chg[3], трейсы:

chg[3]
  #=> {0=>3}

говорит нам, что 3 трея могут быть использованы для снижения баланса до нуля. Решение, таким образом,

chg[2][0+3*3]  #=> chg[2][9]  #=> 0 nickels
chg[1][9+0*5]  #=> chg[1][9]  #=> 2 dimes
chg[0][9+2*10] #=> chg[0][29] #=> 3 quarters

Если факт, как только обнаруживается, что изменение может быть сделано, хэши сводятся к одной паре ключ-значение, ключ которой равен нулю (как показано выше для chg[3]). Если бы мы выполнили:

make_change(25, arr}
  #=> {3=>0, 5=>0, 10=>0, 25=>1}

, мы нашли бы:

chg
  #=> [{0=>1}, {0=>0}, {0=>0}, {0=>0}]