Форум программистов, компьютерный форум CyberForum.ru

Комбинации с монеток - C++

Восстановить пароль Регистрация
 
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 18:02     Комбинации с монеток #1
В копилке есть монетки следующих номиналов:
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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Darky
Быдлокодер
 Аватар для Darky
507 / 294 / 45
Регистрация: 22.11.2009
Сообщений: 892
Завершенные тесты: 1
06.12.2010, 18:03     Комбинации с монеток #2
спасибо, ознакомился.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 18:38  [ТС]     Комбинации с монеток #3
Вообще-то количество разных вариантов можно посчитать за формулой Название: formula.jpg
Просмотров: 43

Размер: 3.5 Кб
но как узнать количество разных сум, как перебрать все возможные варианты сум?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 18:42  [ТС]     Комбинации с монеток #4
Цитата Сообщение от Darky Посмотреть сообщение
спасибо, ознакомился.
пожалуйста, вот ещё
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.12.2010, 19:28     Комбинации с монеток #5
Mayonez, Какие ограничения К, кол-во номиналов и максимальный номинал?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 19:37  [ТС]     Комбинации с монеток #6
количество номиналов 7:
1____2____5____10____25____50_____100
максимальный номинал 100
К меньше 1000
и вводится в конце
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.12.2010, 19:45     Комбинации с монеток #7
Количество номиналов не более 7? В приведенных ранее двух примерах кол-во номиналов было 2 и 4. А по времени есть ограничения?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 19:49  [ТС]     Комбинации с монеток #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Количество номиналов не более 7?
да

Цитата Сообщение от valeriikozlov Посмотреть сообщение
А по времени есть ограничения?
нет
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.12.2010, 20:10     Комбинации с монеток #9
Цитата Сообщение от Mayonez Посмотреть сообщение
Ввод:
4 1 2 5 10 3
Вывод: 19
Реализовывать здесь алгоритм (который сейчас опишу) можно и массивами и векторами (во втором случае получится быстрее и экономичнее по используемой памяти).
Итак есть 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 и есть ответ.
Сможете реализовать код или помочь?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2010, 20:15     Комбинации с монеток
Еще ссылки по теме:

Комбинации C++
Поиск, числа и комбинации C++
Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 20:15  [ТС]     Комбинации с монеток #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сможете реализовать код или помочь?
попробую...
спасибо за помощь!
если не трудно --- вот
Yandex
Объявления
06.12.2010, 20:15     Комбинации с монеток
Ответ Создать тему
Опции темы

Текущее время: 04:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru