Возвращает количество монет, необходимое для монеты в этой позиции в формате массива

Question

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

Таким образом, если m равно 143 и coin = [200, 100, 50, 20, 10, 5, 2, 1], он вернет [0, 1, 0, 2, 0, 0, 1, 1], что означает нет 200 монет, одна 100 монет, нет 50 монет, две 20 монет, нет 10 монет, нет 5 монет, одна 2 монеты и одна 1 монета.

Сейчас мое решение возвращает 5, то есть количество монет.

        def coinSplit(m):
            if m == 0:
                return 0
            for i in range(len(coin)):
                if coin[i] <= m:
                    return 1 + coinSplit(m-coin[i])

      coin = [200, 100, 50, 20, 10, 5, 2, 1]
      print(coinSplit(143))

Answer 1

Работает следующая итеративная реализация:

def coinSplit(m):
    res = []
    for c in coin:
        num = m // c
        m = m % c
        res.append(num)
    return res

>>> coinSplit(143)
[0, 1, 0, 2, 0, 0, 1, 1]

Это предполагает пул монет, для которого этот жадный подход всегда дает результат. Если вы хотите, чтобы это было рекурсивным, вы можете попробовать:

def coinSplit(m, coins):
    if m == 0:
        return [0 for coin in coins]
    return [m // coins[0]] + coinSplit(m % coins[0], coins[1:])

>>> coinSplit(143, [200, 100, 50, 20, 10, 5, 2, 1])
[0, 1, 0, 2, 0, 0, 1, 1]

Answer 2

Вы возвращаете количество необходимых монет, независимо от их стоимости. Вам нужно отслеживать количество каждой монеты, которое, как я предполагаю, вы хотите создать список с тем же размером, что и ваш ввод (coin = [200, 100, 50, 20, 10, 5, 2, 1]), и инициализировать его нулями, и, как другой ответ, добавить к нужному индексу, используя модуль а затем вернуть этот список. Вы все еще можете написать это как рекурсию, но у вас есть другая операция для добавления правильного индекса.

Я думаю, что это домашнее задание, поэтому я не даю код для вас. Надеюсь, это поможет.

Answer 3

Ключ заключается в использовании арифметических операторов в python. В частности, деление / и модуль '%'

Получите частное и остаток, перебирая список, пока остаток не станет равным нулю.

монета = [200, 100, 50, 20, 10, 5, 2, 1]

например:

• 143/200 = 0; 143% 200 = 143
• Переходите к следующему, 143/100 = 1; 143% 100 = 43

повторять этот процесс до тех пор, пока остаток не станет равным нулю