Question

написать программу в питоне
напишите пояснение к написанной программе

Answer 1

Можно решить "по-умному". Можно "по-простому". По-умному интереснее решать на всяких C++. На python приятнее решать по-простому.

• variants = []
• n = int(input("n = "))

• def silly(k):
•    variants = []
•    for ones in range(k + 1):
•        for twos in range(k // 2 + 1):
•            for fifth in range(k // 5 + 1):
•                for tenth in range(k // 10 + 1):
•                    s = tenth * 10 + fifth * 5 + twos * 2 + ones
•                    if s > k:
•                        break
•                    if s == k:
•                        variants.append((ones, twos, fifth, tenth))
•    return variants

• print("Количество вариантов: %d" % len(variants))
• for v in variants:
•    print("Рублями: %d; Двойками: %d; Пятёрками: %d; Десятками: %d." % v)

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

Есть другой подход. "Умный".

Выглядит он так.

• def smart(variants, ones, twos=0, fifth=0, tenth=0):
•    v = (ones, twos, fifth, tenth)
•    if v not in variants:
•        variants.append(v)
•        if ones - 2 >= 0:
•            smart(variants, ones - 2, twos + 1, fifth, tenth)
•        if ones - 5 >= 0:
•            smart(variants, ones - 5, twos, fifth + 1, tenth)
•        if ones - 10 >= 0:
•            smart(variants, ones - 10, twos, fifth, tenth + 1)
•        return variants

Поясняю: Ясное дело, что сумму n можно описать как n монеток по 1 рублю. А все остальные варианты вытекают из этого путем отнятия 2, 5 или 10 рублей от исходной суммы и дописыванием единиц в соответствующие параметры. Такой подход позволяет избежать неправильных комбинаций, однако может генерировать дублирующие варианты. Чтобы этого избежать, проверяем наличие варианта в сохраненных.