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 рублей, тем самым получив из представления ещё 3 новых, из которых также можно получить новые представления.
Для того, чтобы привести этот подход к единому алгоритму создадим два списка – buffer и result: первый будем использовать как буфер ещё не обработанных (из которых будем получать новые ), а второй – как хранилище обработанных . Элементы списка – кортежи типа (количество_монеток_по_рублю, количество_монеток_по_два_рубля, количество_монеток_по_пять рублей, количество_купюр_по_десять_рублей). Полученное в переменную n сумму N, необходимую для представления, сразу представляем как N монеток по 1 рублю и записываем в буфер. В цикле (пока есть ещё необработанные ) забираем из buffer первый необработанный элемент. Если такой уже есть в результатах (могут быть дублирования, нам надо их избежать), пропускаем итерацию цикла и продолжаем со следующего необработанного элемента. Если же такого элемента в результатах нет, то добавляем его как обработанный и находим от 0 до 3 возможных новых необработанных путём "перевода" монеток по 1 рублю в другой номинал.
Цикл выполняется до тех пор, пока в buffer присутствуют необработанные . По окончание работы цикла в списке result содержатся все представления суммы N различными монетами и купюрами.
Код:
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 рублей, тем самым получив из представления ещё 3 новых, из которых также можно получить новые представления.
Для того, чтобы привести этот подход к единому алгоритму создадим два списка – buffer и result: первый будем использовать как буфер ещё не обработанных (из которых будем получать новые ), а второй – как хранилище обработанных . Элементы списка – кортежи типа (количество_монеток_по_рублю, количество_монеток_по_два_рубля, количество_монеток_по_пять рублей, количество_купюр_по_десять_рублей). Полученное в переменную n сумму N, необходимую для представления, сразу представляем как N монеток по 1 рублю и записываем в буфер. В цикле (пока есть ещё необработанные ) забираем из buffer первый необработанный элемент. Если такой уже есть в результатах (могут быть дублирования, нам надо их избежать), пропускаем итерацию цикла и продолжаем со следующего необработанного элемента. Если же такого элемента в результатах нет, то добавляем его как обработанный и находим от 0 до 3 возможных новых необработанных путём "перевода" монеток по 1 рублю в другой номинал.
Цикл выполняется до тех пор, пока в buffer присутствуют необработанные . По окончание работы цикла в списке result содержатся все представления суммы N различными монетами и купюрами.
#include <iostream>
#include <windows.h>
using namespace std;
int main()
{
int hours;
bool isHungry;
SetConsoleOutputCP(1251);
cout << "Напишіть, скільки годин спав лев. Очікуємо ціле число:" << endl;;
cin >> hours;
if (hours < 18)
{
cout << "Лев сонний.";
return 0;
}
else
{
cout << endl << "Введіть 1, якщо лева годували, і 0 — у протилежному випадку:" << endl;
cin >> isHungry;
if (isHungry)
cout << endl << "Лев голодний.";
else cout << endl << "Лев щасливий.";
return 0;
}
}