Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Задача. Теперь по программированию

Задача. Теперь по программированию
Я
   1Сергей
 
09.07.18 - 11:45
Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.
 
 
   patapum
 
1 - 09.07.18 - 11:48
(0) анекдот помнишь, "ты поехал отдохнуть, а там станки, станки, станки..."
   K1RSAN
 
2 - 09.07.18 - 12:15
самое банальное - 4 вложенных цикла)
   1Сергей
 
3 - 09.07.18 - 12:16
(2) да, вариант. Но, я по старинке - рекурсией решил
   1Сергей
 
4 - 09.07.18 - 12:19
При сумме 100 центов получается 292 комбинации, если кому интересно :)
   bolobol
 
5 - 09.07.18 - 12:25
Миста вопрос: "А зачем?"
   Cool_Profi
 
6 - 09.07.18 - 12:27
Сколько денег?
   1Сергей
 
7 - 09.07.18 - 12:29
(6) нужно сделать алгоритм который смог бы рассчитать на любую сумму
   bolobol
 
8 - 09.07.18 - 12:31
(7) Кому нужно? Это не противозаконно?, 1С использовать в личных, не рабочих, целях
   mistеr
 
9 - 09.07.18 - 12:39
(3) Рекурсия выдала кучу дублей?
   Fish
 
10 - 09.07.18 - 12:40
(0) А почему именно в американских деньгах?
 
 Рекламное место пустует
   Вафель
 
11 - 09.07.18 - 12:41
Первый вопрос должен быть: Сколько платишь )))
   1Сергей
 
12 - 09.07.18 - 12:48
(9) эээ... нет. всё вроде предусмотрел
   1Сергей
 
13 - 09.07.18 - 12:48
(11) За решение задачи для 9-го класса? Не стыдно?
   1Сергей
 
14 - 09.07.18 - 12:55
Кароче, кому лень думать. Вот моё решение



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

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


Номиналы = Новый Массив;
Номиналы.Добавить(50);
Номиналы.Добавить(25);
Номиналы.Добавить(10);
Номиналы.Добавить(5);
Номиналы.Добавить(1);
   Михаил Козлов
 
15 - 09.07.18 - 13:07
Число решений уравнения:
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)
   bolobol
 
16 - 09.07.18 - 13:35
(15) Я ничо непонел
   Ching Wu
 
17 - 09.07.18 - 13:53
(0) про 2 цента забыл
   mistеr
 
18 - 09.07.18 - 13:53
(11) Был же в (6)
   1Сергей
 
19 - 09.07.18 - 13:53
(15) всё гениальное простынь
А тоже самое на ЯП слабо?
   1Сергей
 
20 - 09.07.18 - 13:55
(17) нет сейчас у них двухцентовиков
   Asmody
 
21 - 09.07.18 - 13:59
(19) Гугли "линейные диофантовы уравнения".
   Ching Wu
 
22 - 09.07.18 - 14:06
(20) Молодец, прошел тест
   Михаил Козлов
 
23 - 09.07.18 - 14:12
(16) Характерный случай: биномиальные коэффициенты (C(n,k) - число сочетаний из n по k) - производящая функция (1+Z)^n.
   1Сергей
 
24 - 09.07.18 - 14:16
теоретики
   Михаил Козлов
 
25 - 09.07.18 - 14:31
(24) Сколько денег?
   1Сергей
 
26 - 09.07.18 - 14:36
(25) см (7)
   Михаил Козлов
 
27 - 09.07.18 - 14:38
(26) Сколько платите за решение?
   1Сергей
 
28 - 09.07.18 - 14:38
(26) см (13)
   NSSerg
 
29 - 09.07.18 - 14:42
(28) Если решать с наилучшей сложностью алгоритма - то это  не 9 класс.
   NSSerg
 
30 - 09.07.18 - 14:48
За О(N^2) решается динамическим программированием.
Для всех значений от 0 до N считаем сколько вариантов набора суммы полтинниками (значение будет один или ноль)
Потом вторым проходом сколько вариантов набора полтинниками и 25-центовиками.
и т.д.
   Михаил Козлов
 
31 - 09.07.18 - 14:49
(28) Вот Вы в (14) и оформили программно (15).
(30) В (14), как мне кажется, примерно так и сделано.
   bolobol
 
32 - 09.07.18 - 14:53
(31) Так это про сочетания (уникальные расстановки) в массиве к-элементов из н-возможных элементов.
У нас ни н нет - не ограничено, ни к нет - не ограничено. В н имеется ещё и размер - не в каждую ячейку из к влезет, т.е. - займёт несколько ячеек к, если допустить, что к - это сумма. Или как?
   bolobol
 
33 - 09.07.18 - 15:00
*Уникальные отсортированные расстановки (111223 = 131122)
*из н-возможных вариантов элементов (1,5,10,25,50)
 
 
   NSSerg
 
34 - 09.07.18 - 15:02
(31) Нет. ДП без массива не получится.
   NSSerg
 
35 - 09.07.18 - 15:04
+ (34) Хотя похоже да, там тоже N^N, и тоже самое, но без массива.
   NSSerg
 
36 - 09.07.18 - 15:23
N^2 конечно.
   NSSerg
 
37 - 09.07.18 - 15:34
Кстати, в (15) - О(N)
   bolobol
 
38 - 09.07.18 - 16:11
(37) Но задачу это решить не помогает
   NSSerg
 
39 - 09.07.18 - 16:33
(38) В смысле? Код в (15) Решает задачу за О(N)
Набери миллион копеек, и он решит.
   NSSerg
 
40 - 09.07.18 - 16:34
Блин, в (14) конечно-же.
   1Сергей
 
41 - 09.07.18 - 17:46
(39) ващета не решит. Вылетит из-за нехватки памяти :)
   Михаил Козлов
 
42 - 09.07.18 - 20:54
(41) Неправда Ваша: достаточно храниить только коэффициента разложения в ряд производящей функции, т.е. не более сумма чисел. Многовато, конечно, если сумма - большое число, но в этом случае в (14) будет большой стек (а это тоже память).
   Михаил Козлов
 
43 - 09.07.18 - 21:02
(42) Более того, если бы трудоемкость (15) была любая степень от LOG(сумма), это было бы ПОЧТИ решением проблемы P=NP, что вряд ли.
   Михаил Козлов
 
44 - 09.07.18 - 22:29
Позволю себе еще одно замечание: в (21) есть важная, по-моему, наводка: для числа решений линейного диофантова уравнения можно составить реккурентное соотношение, а это путь для его рекурсивного вычисления.
   PR
 
45 - 09.07.18 - 22:41
(4) А если никому не интересно?
   1Сергей
 
46 - 10.07.18 - 10:34
(45) те молча проходят мимо


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует