Имя: Пароль:
1C
 
Помогите решить задачу с монетами
, , , ,
0 Sv4org
 
29.11.16
13:05
Имеются монеты достоинством 1, 2, 5, 10, 25, 50 копеек. Написать функцию, которая определяет, как любую заданную сумму денег представить наименьшим количеством монет указанного достоинства.
1 Ёпрст
 
29.11.16
13:07
Тебе нужно брать остаток от деления и всё.
2 Ёпрст
 
29.11.16
13:08
начиная от монет с большим достоинством.
3 torgm
 
29.11.16
13:09
в цикле идя к меньшему
4 HeKrendel
 
29.11.16
13:09
Изи
5 IlyaSR
 
29.11.16
13:09
вот тут все разжевано https://clck.ru/AKvyE
6 azt-yur
 
29.11.16
13:12
(1) тоже так сразу подумал, для данных номиналов вроде прокатывает, а как универсальное решение думаю не подойдет.
Например имеем монеты номиналом 1, 6 и 10. Надо получить 12. По твоему алгоритму получится 10, 1, 1 (всего 3 монеты), а лучше будет 6 и 6 (2 монеты)
7 HeKrendel
 
29.11.16
13:14
(6) монета номиналом 6? Из Ада чтоли?
8 HeKrendel
 
29.11.16
13:14
Да и почему не 10 и 2?
9 IlyaSR
 
29.11.16
13:15
(7) "ты бери, я себе еще нарисую" (с)
10 IlyaSR
 
29.11.16
13:16
(5) https://clck.ru/AKw3H для минимального кол-ва монет
11 azt-yur
 
29.11.16
13:18
(7) ну я же про универсальный случай. наверное действующие номиналы не просто так придуманы. Пока для них не придумаю случая, чтобы решение из (1) не прокатывало
12 Di-dog
 
29.11.16
13:18
Монеты достоинством 1, 2, 5, 10, 25, 50 копеек - каноническая система, решается жадным алгоритмом из (1).
Для прочих систем, например в (6), задача становится линейной задачей на оптимизацию и решается, соответственно, методами оптимизации(тем же симплекс-методом)

Динамическое программирование тут не нужно, тут линейная оптимизируемая функция.
13 Sv4org
 
29.11.16
13:29
Можете кто-то помочь хотяб начать писать этот цикл на 1с?
14 Garykom
 
гуру
29.11.16
13:30
(0) Алгоритмически данную задачу сейчас решать не принято, ибо на экономию места и памяти давно забили, важна только скорость выдачи ответа причем в параллельном режиме.

Поэтому многомерный массив (регистр сведений) хранящийся в БД, где уже заранее посчитаны всевозможные "наборы монеток".

А результат получается SQL запросом мгновенно с оптимизацией по индексу...
15 Salimbek
 
29.11.16
13:32
(13) Помогаю, вот тебе первое слово:
Функция
16 Fish
 
29.11.16
13:35
(13) Так в (10) готовая функция есть с подробным описанием. Всего-то надо на 1С её переписать.
17 azt-yur
 
29.11.16
13:36
Кол = 0;
Кол = Кол + Цел(Н/50);
Н = Н%50;
Кол = Кол + Цел(Н/25);
Н = Н%25;
.....
18 Dmitry77
 
29.11.16
13:41
(13) пока суммамонет   <> 0 цикл


конеццикла
19 aka AMIGO
 
29.11.16
13:51
Перем ТекМ, КолМ, ОстМ;
//***
Функция Очередная(Ост)
    КолМ = Цел(Ост/ТекМ);
    ОстМ = Ост%ТекМ;
КонецФункции

Процедура Сформировать()
    СЗМ = СоздатьОбъект("СписокЗначений");
    //1, 2, 5, 10, 25, 50
    СЗМ.ДобавитьЗначение(50);
    СЗМ.ДобавитьЗначение(25);
    СЗМ.ДобавитьЗначение(10);
    СЗМ.ДобавитьЗначение(5);
    СЗМ.ДобавитьЗначение(2);
    СЗМ.ДобавитьЗначение(1);
    
    ОстМ=ПростоЧисло;
    
    Для ы=1 По СЗМ.РазмерСписка() Цикл
        ТекМ = СЗМ.ПолучитьЗначение(ы);
        Очередная(ОстМ);
        Если КолМ=0 Тогда
            Если ОстМ=0 Тогда
                Прервать;
            КонецЕсли;
        КонецЕсли;
        Если КолМ=0 Тогда
            Продолжить;
        КонецЕсли;
        Сообщить(""+ТекМ+ " ;  "+КолМ+"шт; (Ост: "+ОстМ+")");
    КонецЦикла;
    
КонецПроцедуры
    ТекМ="";
    КолМ=0;
    ОстМ=0;
20 aka AMIGO
 
29.11.16
13:52
Результат в окне сообщений:
50 ;  2шт; (Ост: 33)
25 ;  1шт; (Ост: 8)
5 ;  1шт; (Ост: 3)
2 ;  1шт; (Ост: 1)
1 ;  1шт; (Ост: 0)
21 aka AMIGO
 
29.11.16
13:53
+А, да..
ПростоЧисло = 133
22 aka AMIGO
 
29.11.16
13:54
"ПростоЧисло" - элемент формы диалога
23 1dvd
 
29.11.16
13:56
(14) что курим?
24 Вафель
 
29.11.16
14:01
Так это же задача о рюкзаке
25 Вафель
 
29.11.16
14:03
Собеседование?
26 Garykom
 
гуру
29.11.16
14:06
(23) Написать тупой банальный алгоритм или продумать варианты разных решений которые "лучше" в чем то?

Просчитывать "таблицу вариантов" требуется только для чисел от 1 до (СамаяБольшаяМонетка*2-1). Все что больше получается добором этими самого большого номинала.
27 Это_mike
 
29.11.16
14:10
(26) а если монеты не из какнонического ряда, да еще дробным номиналом? И не обязательно положительным?
:-)
28 Это_mike
 
29.11.16
14:11
монеты с комплексным номиналом - тоже прикольно...
29 Garykom
 
гуру
29.11.16
14:14
(27) Дробный номинал это фигня, просто приводим их к натуральным и все, с одним наименьшим общим знаменателем.

(28) С комплексными задачка решается аналогично, только чуть сложнее. Для любого заданного "конечного" кол-ва номиналов она решаема.
30 Вафель
 
29.11.16
14:15
Тк следующая монета больше в 2 раза чем предыдущая, то работает жадный алгоритм
31 Это_mike
 
29.11.16
14:16
(29) а иррациональные? пи копеек, корень из трех рублей...
32 Garykom
 
гуру
29.11.16
14:19
(31) Фиолетово абсолютно, "табличный алгоритм" то универсальный ))
Независимо от того, куда вы едете — это в гору и против ветра!