351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
|
|
1 | |
Банкомат07.12.2013, 15:48. Показов 31020. Ответов 58
Метки нет (Все метки)
задание
Кликните здесь для просмотра всего текста
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую необходимо выдать. Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution. Напишите нормально условие задание,а то я не могу понять условие. Можна пример(прошу не код а пояснение задание).
0
|
07.12.2013, 15:48 | |
Ответы с готовыми решениями:
58
Система банкомат Программа-банкомат! Банкомат. В чем ошибка? написать прогу банкомат |
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
|
||||||
07.12.2013, 19:19 [ТС] | 22 | |||||
ввод номинала
ненужная часть с пред кода(проверка может быть ответ 1 и не пересчитывать все) Добавлено через 4 минуты ValeryS, а как можна сразу узнать No solution Добавлено через 18 минут
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
07.12.2013, 19:33 | 23 | |||||
очень просто
остаток от деления на младший номинал например у тебя младшая купюра 10 руб а нужно выдать 1234 рубля четыре рубля ну никак не выплатим пишем
0
|
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
|
|||||||||||
07.12.2013, 19:36 [ТС] | 24 | ||||||||||
Добавлено через 53 секунды тогда код вот Кликните здесь для просмотра всего текста
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
07.12.2013, 19:36 | 25 |
Эта задача решается ДП (salam реализовал именно этот вариант).
Решение задачи жадным алгоритмом, типа: будет выдавать неправильный результат. Вот контрпример: 3 1 70 100 140 Правильный ответ будет 2 банкноты номиналом 70 Жадный алгоритм выдаст другой результат.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
07.12.2013, 19:52 | 28 |
я пытался обратить ваше внимание на то, что жадное решение легко валится.
никакого цикла, кроме динамики здесь быть не может.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
07.12.2013, 19:53 | 29 |
в котрпримере, который я привел решается по старшим номиналам, только ответ будет неправильный:
100 1 1 1 1 1 1 1 1 ... и т.д. всего 40 единиц
0
|
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
|
||||||
07.12.2013, 20:04 [ТС] | 30 | |||||
господа прошу комент + критику
Кликните здесь для просмотра всего текста
Добавлено через 38 секунд контр пример можна? Добавлено через 1 минуту нашол Error 3 1 1 1 5 ответ No solution.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
07.12.2013, 20:08 | 31 |
2 4 6 11 15
выводит 2.
0
|
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
|
|
07.12.2013, 20:16 [ТС] | 32 |
2
4 6 11 а 15 что ето? Добавлено через 2 минуты ну правельно 4 2 4 6 11 15 ответ 2 = 11+4 Добавлено через 2 минуты Вот сайт на котором я время убиваю
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|
07.12.2013, 20:23 | 33 |
слушайте
я не господь Бог, могу ошибаться посему и написал я где то сказал что это правильное и единственное решение? переведи? что есть динамика? согласен косяк я забивался на российские банкноты а они кратны 10 можно сделать так не делится нацело на минимальную, берем следующую и т.д
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
07.12.2013, 20:24 | 34 |
попробуйте такой тест:
4 1 4 5 16 24 правильный ответ должен быть 3 купюры (16 4 4) Не по теме: сейчас компилятора под рукой нет чтобы самому проверить
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
07.12.2013, 20:29 | 35 |
0
|
07.12.2013, 21:00 | 37 |
0
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
|
07.12.2013, 21:40 | 38 |
Через рекурсию не лучше будет?
0
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
|
07.12.2013, 22:34 | 40 |
Тоже верно. Просто удивился, что за все обсуждение ни разу не возникло подобное предложение.
0
|
07.12.2013, 22:34 | |
07.12.2013, 22:34 | |
Помогаю со студенческими работами здесь
40
Программа вылетает (банкомат) Задача про банкомат Банкомат с помощью массивов и циклов Оператор goto в коде под Банкомат Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |