С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

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

06.12.2010, 18:02. Просмотров 809. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2010, 18:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинации с монеток (C++):

задана некоторая сумма в рублях.определить минимальное количество монеток - C++
задана некоторая сумма в рублях.определить минимальное количество монеток достоинством 1, 2 и 5 рублей, необходимое для того, чтобы набрать...

Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной - C++
Добрый вечер, наткнулся на простую задачу - сложность всего лишь 8%. Её нужно решить с использованием цикла for. Задачу, я, конечно, решил,...

Комбинации - C++
Здраствуйте форумчани. Столкнулся с проблемой что немогу решить головоломку. Допустим у нас есть строка символ AAB. В результате программа...

Комбинации - C++
Всем привет! Есть массив array, в переменной s хранится его размер. Нужно написать прогу, которая выведет на экран все возможные...

комбинации чисел - C++
здравствуйте, помогите дауну создать проэкт. visual studio 2005-2008 вот мне данно готовый пакет string ;IntToString(int intValue) //...

Комбинации отобразить в целое - C++
Добрый день! Вот такая у меня задача: Получаю на входе 5 значений double. Пусть переменные a,b,c,d,e 1 задача расположить их в...

9
Darky
Быдлокодер
507 / 294 / 45
Регистрация: 22.11.2009
Сообщений: 892
Завершенные тесты: 1
06.12.2010, 18:03 #2
спасибо, ознакомился.
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 18:38  [ТС] #3
Вообще-то количество разных вариантов можно посчитать за формулой Название: formula.jpg
Просмотров: 43

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

Цитата Сообщение от valeriikozlov Посмотреть сообщение
А по времени есть ограничения?
нет
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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 и есть ответ.
Сможете реализовать код или помочь?
1
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
06.12.2010, 20:15  [ТС] #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сможете реализовать код или помочь?
попробую...
спасибо за помощь!
если не трудно --- вот
0
06.12.2010, 20:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2010, 20:15
Привет! Вот еще темы с ответами:

Поиск, числа и комбинации - C++
Здравствуйте! В недавних моих темах я затрагивал подобные поиски комбинаций. Дальнейшие размышления меня привели к тому, что я хочу...

Все комбинации чисел от 1 до 4 - C++
Все комбинации чисел от 1 до 4. Как сделать:)? 1111, 1112, 1113, 1114, ...... 4443, 4444 - как-то так

Максимальное число из комбинации цифр - C++
Ребята помогите пожалуйста написать код к программе с комментариями в Visual Studio.Буду Очень признательна:thank_you: ...

Все возможные комбинации длины k из 0 и 1 - C++
Как бы это реализовать? Подкиньте идей или может есть готовая у кого-то. Ввод k:3 Вывод: 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 и...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.