Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.

(0) анекдот помнишь, "ты поехал отдохнуть, а там станки, станки, станки..."

самое банальное - 4 вложенных цикла)

(2) да, вариант. Но, я по старинке - рекурсией решил

При сумме 100 центов получается 292 комбинации, если кому интересно :)

Миста вопрос: "А зачем?"

Сколько денег?

(6) нужно сделать алгоритм который смог бы рассчитать на любую сумму

(7) Кому нужно? Это не противозаконно?, 1С использовать в личных, не рабочих, целях

(3) Рекурсия выдала кучу дублей?

(0) А почему именно в американских деньгах?

Первый вопрос должен быть: Сколько платишь )))

(9) эээ... нет. всё вроде предусмотрел

(11) За решение задачи для 9-го класса? Не стыдно?

Кароче, кому лень думать. Вот моё решение



Перем Номиналы;

Функция КоличествоКомбинаций(Сумма, МонетыМеньшеНоминала = 100) Экспорт
    
    Если Сумма < 5 Тогда
        Возврат 1;
    КонецЕсли;
    
    Результат = 0;
    
    Для Каждого Номинал Из Номиналы Цикл
        
        Если Номинал >= МонетыМеньшеНоминала Тогда
            Продолжить;
        КонецЕсли;
        
        Если Номинал = 1 Тогда
            Результат = Результат + 1;
        Иначе
            
            МаксМонет = Цел(Сумма / Номинал);
            
            Для Идн = 1 по МаксМонет Цикл
                
                Результат = Результат + КоличествоКомбинаций(Сумма - Номинал*Идн, Номинал);
                
            КонецЦикла;
            
        КонецЕсли;
        
    КонецЦикла;
    
    Возврат Результат;
    
КонецФункции


Номиналы = Новый Массив;
Номиналы.Добавить(50);
Номиналы.Добавить(25);
Номиналы.Добавить(10);
Номиналы.Добавить(5);
Номиналы.Добавить(1);

Число решений уравнения:
1*Х1+5*Х2+10*Х3+25*Х4+50*Х5 = сумма (в целых неотрицательных).
Равно коэффициенту при Z^сумма в разложении функции (производящая):
1/(1-Z)*1/(1-Z^5)*1/(1-Z^10)*1/(1-Z^25)*1/(1-Z^50)

(15) Я ничо непонел

(0) про 2 цента забыл

(11) Был же в (6)

(15) всё гениальное простынь
А тоже самое на ЯП слабо?

(17) нет сейчас у них двухцентовиков

(19) Гугли "линейные диофантовы уравнения".

(20) Молодец, прошел тест

(16) Характерный случай: биномиальные коэффициенты (C(n,k) - число сочетаний из n по k) - производящая функция (1+Z)^n.

теоретики

(24) Сколько денег?

(25) см (7)

(26) Сколько платите за решение?

(26) см (13)

(28) Если решать с наилучшей сложностью алгоритма - то это  не 9 класс.

За О(N^2) решается динамическим программированием.
Для всех значений от 0 до N считаем сколько вариантов набора суммы полтинниками (значение будет один или ноль)
Потом вторым проходом сколько вариантов набора полтинниками и 25-центовиками.
и т.д.

(28) Вот Вы в (14) и оформили программно (15).
(30) В (14), как мне кажется, примерно так и сделано.

(31) Так это про сочетания (уникальные расстановки) в массиве к-элементов из н-возможных элементов.
У нас ни н нет - не ограничено, ни к нет - не ограничено. В н имеется ещё и размер - не в каждую ячейку из к влезет, т.е. - займёт несколько ячеек к, если допустить, что к - это сумма. Или как?

*Уникальные отсортированные расстановки (111223 = 131122)
*из н-возможных вариантов элементов (1,5,10,25,50)

(31) Нет. ДП без массива не получится.

+ (34) Хотя похоже да, там тоже N^N, и тоже самое, но без массива.

N^2 конечно.

Кстати, в (15) - О(N)

(37) Но задачу это решить не помогает

(38) В смысле? Код в (15) Решает задачу за О(N)
Набери миллион копеек, и он решит.

Блин, в (14) конечно-же.

(39) ващета не решит. Вылетит из-за нехватки памяти :)

(41) Неправда Ваша: достаточно храниить только коэффициента разложения в ряд производящей функции, т.е. не более сумма чисел. Многовато, конечно, если сумма - большое число, но в этом случае в (14) будет большой стек (а это тоже память).

(42) Более того, если бы трудоемкость (15) была любая степень от LOG(сумма), это было бы ПОЧТИ решением проблемы P=NP, что вряд ли.

Позволю себе еще одно замечание: в (21) есть важная, по-моему, наводка: для числа решений линейного диофантова уравнения можно составить реккурентное соотношение, а это путь для его рекурсивного вычисления.

(4) А если никому не интересно?

(45) те молча проходят мимо