Question

Написать программу в питоне
можно пожалуйста с объяснениями

Answer 1

Код:

• n = int(input("n = "))
• buffer = [(n, 0, 0, 0)]
• result = []
• while len(buffer) > 0:
•    variant = buffer.pop()
•    if variant in result:
•        continue
•    result.append(variant)
•    ones, twos, fives, tens = variant
•    if ones - 2 >= 0:
•        buffer.append((ones - 2, twos + 1, fives, tens))
•    if ones - 5 >= 0:
•        buffer.append((ones - 5, twos, fives + 1, tens))
•    if ones - 10 >= 0:
•        buffer.append((ones - 10, twos, fives, tens + 1))
• print("Задание А.\nКоличество способов: %d\n" % len(result))
• print("Задание Б.\nДекларация вариантов:")
• for variant in result:
•    print("Монеток по 1 рублю: %d; Монеток по 2 рубля: %d; Монеток по 5 рублей: %d; Купюр по 10 рублей: %d." % variant)

Пояснение:

Самый простой способ представить сумму в N рублей – выразить её как N монеток по 1 рублю. Из этого представления "вытекают" все остальные способы. С теми ограничениями, что количество денег каждого номинала не может быть отрицательным, мы можем "перевести" 2 монетки по 1 рублю в 1 монетку по 2 рубля, 5 монеток по 1 рублю в 1 монетку по 5 рублей и 10 монеток по 1 рублю в 1 купюру по 10 рублей, тем самым получив из 1 способа представления ещё 3 новых, из которых также можно получить новые способы представления.

Для того, чтобы привести этот подход к единому алгоритму создадим два списка – buffer и result: первый будем использовать как буфер ещё не обработанных способов (из которых будем получать новые способы), а второй – как хранилище обработанных способов. Элементы списка – кортежи типа (количество_монеток_по_рублю, количество_монеток_по_два_рубля, количество_монеток_по_пять рублей, количество_купюр_по_десять_рублей). Полученное в переменную n сумму N, необходимую для представления, сразу представляем как N монеток по 1 рублю и записываем в буфер. В цикле (пока есть ещё необработанные способы) забираем из buffer первый необработанный элемент. Если такой способ уже есть в результатах (могут быть дублирования, нам надо их избежать), пропускаем итерацию цикла и продолжаем со следующего необработанного элемента. Если же такого элемента в результатах нет, то добавляем его как обработанный и находим от 0 до 3 возможных новых необработанных способов путём "перевода" монеток по 1 рублю в другой номинал.

Цикл выполняется до тех пор, пока в buffer присутствуют необработанные способы. По окончание работы цикла в списке result содержатся все способы представления суммы N различными монетами и купюрами.