Задача от Apple про кассира-программиста

Задача от Apple про кассира-программиста
Представим что вы устроились на подработку в качестве кассира. Через несколько дней ваш БОСС узнает что вы программист и просит написать небольшую программу.

Программа будет принимать два параметра:
  1. Сумма денег
  2. Массив, в котором указаны все возможные номиналы монет
После выполнения программа должна выдавать количество всех возможных способов выдачи указанной суммы денег всеми возможными номиналами монет. К примеру, если вам надо 5 центов из монет номиналом 1, 2 и 3, то у вас получится число 5.
Так как это такие возможные варианты:
  1. 1 + 1 + 1 + 1 + 1
  2. 1 + 2 + 2
  3. 1 + 1 + 3
  4. 3 + 2
  5. 1 + 1 + 1 + 2

Решение задачи

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

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

Поскольку мы уже проделали все операции со всеми возможными номиналами, теперь нам необходимо добавить сумму. Делается это просто. Помним, что у нас уже есть сумма, которая равна 0, а также все номиналы монет. Это новое число записывается как существующее значение: higher_amount_remainder = higher_amount - coin.

Итак, вот код решения на языке Python:

def change_possibilities_bottom_up(amount, denominations):
    doing_n_cents = [0] * (amount + 1)
    doing_n_cents[0] = 1
 
    for coin in denominations:
        for higher_amount in range(coin, amount + 1):
            higher_amount_remainder = higher_amount - coin
            doing_n_cents[higher_amount] += doing_n_cents[higher_amount_remainder]
 
    return doing_n_cents[amount]
    
denominations = [1, 2, 3]
print (change_possibilities_bottom_up(5, denominations))
Чтобы было понятно, то вот пример того что содержит массив doing_n_cents если мы ищем число всех возможных вариантов из числа 5 и номиналов [1, 3 и 5]:

===========
key:
a = higher_amount
r = higher_amount_remainder
===========
 
============
for coin = 1:
============
[1, 1, 0, 0, 0, 0]
 r  a
 
[1, 1, 1, 0, 0, 0]
    r  a
 
[1, 1, 1, 1, 0, 0]
       r  a
 
[1, 1, 1, 1, 1, 0]
          r  a
 
[1, 1, 1, 1, 1, 1]
             r  a
 
============
for coin = 3:
=============
[1, 1, 1, 2, 1, 1]
 r        a
 
[1, 1, 1, 2, 2, 1]
    r        a
 
[1, 1, 1, 2, 2, 2]
       r        a
 
============
for coin = 5:
=============
[1, 1, 1, 2, 2, 3]
 r              a
 
 
final answer: 3
()
Количество показов: 207
15 января 2017

Возврат к списку

Корзина0 позиций на сумму 0 руб.