392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
|
|
1 | |
Комбинации с монеток06.12.2010, 18:02. Показов 1262. Ответов 9
Метки нет (Все метки)
В копилке есть монетки следующих номиналов:
1 2 5 10 25 50 100 из копилки достаются К монеток Сколько различных значений может иметь сумма полученных денег? Пример: Ввод: 2 10 25 3 2 - количество номиналов (далее 10 и 25), которые есть в копилке 3 - количество вытянутых монеток Вывод: 4 10 + 10 + 10 = 30 ; 10 + 10 + 25 = 45; 10 + 25 + 25 = 60; 25 + 25 + 25 = 75; Итого, 4 разных значения Ввод: 4 1 2 5 10 3 Вывод: 19
0
|
06.12.2010, 18:02 | |
Ответы с готовыми решениями:
9
Притяжение монеток! Найти в строке все комбинации из сдвоенных букв и удалить вторую букву в каждой комбинации Заменить в заданном слове комбинации 1011 на комбинации 1101 Определить минимальное число монеток, которые нужно перевернуть |
Быдлокодер
512 / 298 / 85
Регистрация: 22.11.2009
Сообщений: 892
|
|
06.12.2010, 18:03 | 2 |
спасибо, ознакомился.
0
|
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
|
|
06.12.2010, 18:38 [ТС] | 3 |
Вообще-то количество разных вариантов можно посчитать за формулой
но как узнать количество разных сум, как перебрать все возможные варианты сум?
0
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
06.12.2010, 19:28 | 5 |
Mayonez, Какие ограничения К, кол-во номиналов и максимальный номинал?
1
|
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
|
|
06.12.2010, 19:37 [ТС] | 6 |
количество номиналов 7:
1____2____5____10____25____50_____100 максимальный номинал 100 К меньше 1000 и вводится в конце
0
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
06.12.2010, 19:45 | 7 |
Количество номиналов не более 7? В приведенных ранее двух примерах кол-во номиналов было 2 и 4. А по времени есть ограничения?
1
|
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
|
|
06.12.2010, 19:49 [ТС] | 8 |
0
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
06.12.2010, 20:10 | 9 |
Реализовывать здесь алгоритм (который сейчас опишу) можно и массивами и векторами (во втором случае получится быстрее и экономичнее по используемой памяти).
Итак есть 4 номинала: 1 2 5 10 И есть К равное 3 (максимально взятое число монет из копилки). Расмотрим сначало взятие 1 монеты из копилки. В данном случае суммы которые могут получится такие: 1 2 5 10 - назовем это первой строкой. Теперь найдем 2 строку (какие суммы могут получится при взятии 2-х монет из копилки). Здесь нужно учитывать результаты из предыдущей строки (из первой). Итак перебираем возможные номиналы, которые можем взять. Берем первый номинал - это 1. Вторая строка пока получается такой: 2 3 6 11 - текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала). Далее берем второй номинал - это 2. Теперь вторая строка получается такая: 2 3 4 6 7 11 12- текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем). Далее берем третий номинал - это 5. Теперь вторая строка получается такая: 2 3 4 6 7 10 11 12 15- текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем). Далее берем четвертый номинал - это 10. Теперь вторая строка получается такая: 2 3 4 6 7 10 11 12 15 20 - окончательные значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем). Т. е. вторая строка получилась: 2 3 4 6 7 10 11 12 15 20 - т.е. такие суммы могут получится если взять две монетки. Теперь формируем третью строку (по тому же принципу): Берем первый номинал - 1. Третья строка: 3 4 5 7 8 11 13 16 21 Берем второй номинал - 2. Третья строка: 3 4 5 6 7 8 9 11 12 13 14 16 17 21 22 Берем третий номинал - 5. Третья строка: 3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25 Берем четвертый номинал - 10. Третья строка: 3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25 30 Окончательные значения третьей строки: 3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25 30 - все возможные значения сумм. Их кол-во - 19 и есть ответ. Сможете реализовать код или помочь?
1
|
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
|
|
06.12.2010, 20:15 [ТС] | 10 |
0
|
06.12.2010, 20:15 | |
06.12.2010, 20:15 | |
Помогаю со студенческими работами здесь
10
Определите минимальное число монеток, которые нужно перевернуть как остальные Алгоритм: Как выплатить заданную сумму денюжек за минимальный набор монеток? Задана некоторая сумма в рублях, определить минимальное количество монеток для набора этой суммы Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |