|
Помогите решить задачу с монетами | ☑ | ||
---|---|---|---|---|
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) Фиолетово абсолютно, "табличный алгоритм" то универсальный ))
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |