Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.92/170: Рейтинг темы: голосов - 170, средняя оценка - 4.92
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
1

Банкомат

07.12.2013, 15:48. Показов 31020. Ответов 58
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
задание
Кликните здесь для просмотра всего текста
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.

Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую необходимо выдать.

Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.

Напишите нормально условие задание,а то я не могу понять условие.
Можна пример(прошу не код а пояснение задание).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.12.2013, 15:48
Ответы с готовыми решениями:

Система банкомат
Создать принцип работы банкомата в консольном виде на C++ Visual Studio 2013 Принцип работы:...

Программа-банкомат!
Довольно интересная задача, описал ее как смог, если что неясно по условию, спрашивайте. ...

Банкомат. В чем ошибка?
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Автор: Фёдор...

написать прогу банкомат
Вот надо написать прогу банкомат и столкнулся с проблемой вот код bool ATM::login() { ...

58
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
07.12.2013, 18:52 21
Author24 — интернет-сервис помощи студентам
newyork7776,
все бы хорошо
ноя не врубился
Цитата Сообщение от newyork7776 Посмотреть сообщение
for (int i=1;i<=n;i++)
{
cout << "Enter " << i << " = ";cin >> mas[i];
это количество номиналов?
Цитата Сообщение от newyork7776 Посмотреть сообщение
for(int i=1;i<=n;i++)
{
if (s==mas[i])
{
при чем здесь номиналы?
0
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
07.12.2013, 19:19  [ТС] 22
Цитата Сообщение от ValeryS Посмотреть сообщение
for (int i=1;i<=n;i++)
{
cout << "Enter " << i << " = ";cin >> mas[i];
ввод номинала
Цитата Сообщение от ValeryS Посмотреть сообщение
for(int i=1;i<=n;i++)
{
if (s==mas[i])
{
ненужная часть с пред кода(проверка может быть ответ 1 и не пересчитывать все)

Добавлено через 4 минуты
ValeryS, а как можна сразу узнать No solution

Добавлено через 18 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int main()
{
    int n,ans=0;
    signed long mas[100],s,k;
    cin >> n;
    if (n==0)
        return -1;
    for (int i=1;i<=n;i++)
    {
        cin >> mas[i]; 
    };
    cin >> s;
    k=s;
    for (int i=n;i>=1;i--)
    {
        while (k>=mas[i])
        {
            k-=mas[i];
            cout << mas[i] << " ";
        }
    };
    if (k!=0)
    {
        cout << "\rNo solution.";
        system("pause");
        return -1;
    };
 
    cout << "\n";
    system("pause");
}
вот решил без проверки вначале на No solution
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
07.12.2013, 19:33 23
Цитата Сообщение от newyork7776 Посмотреть сообщение
ValeryS, а как можна сразу узнать No solution
очень просто
остаток от деления на младший номинал
например у тебя младшая купюра 10 руб
а нужно выдать 1234 рубля
четыре рубля ну никак не выплатим
пишем
C++
1
2
if(n%10!=0)
 printf("No solution");
0
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
07.12.2013, 19:36  [ТС] 24
C++
1
2
3
4
5
6
7
8
9
for (int i=0;i<n;i++)
    {
        if ((s%mas[i])!=0)
        {
            cout << "No solution.";
            system("pause");
            return -1;
        }
    }
так или нет?

Добавлено через 53 секунды
тогда код вот
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
int main()
{
    int n,ans=0;
    signed long mas[100],s,k;
    cin >> n;
    if (n==0)
        return -1;
    for (int i=1;i<=n;i++)
    {
        cin >> mas[i]; 
    };
    cin >> s;
    for (int i=0;i<n;i++)
    {
        if ((s%mas[i])!=0)
        {
            cout << "No solution.";
            system("pause");
            return -1;
        }
    }
    k=s;
    for (int i=n;i>=1;i--)
    {
        while (k>=mas[i])
        {
            k-=mas[i];
            cout << mas[i] << " ";
        }
    };
    cout << "\n";
    system("pause");
}
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.12.2013, 19:36 25
Эта задача решается ДП (salam реализовал именно этот вариант).
Решение задачи жадным алгоритмом, типа:
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
циклы while
сначала из суммы вычитаем достоинства максимальных банкнот, потом ниже и т.д
будет выдавать неправильный результат.
Вот контрпример:
3
1 70 100
140
Правильный ответ будет 2 банкноты номиналом 70
Жадный алгоритм выдаст другой результат.
0
шКодер самоучка
2227 / 1921 / 927
Регистрация: 09.10.2013
Сообщений: 4,260
Записей в блоге: 7
07.12.2013, 19:40 26
ValeryS, неверно, если есть банкноты большие минимальной, но не делющиеся нацело на минимальную
Например
5
10 25 50 100 500
75
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
07.12.2013, 19:46 27
valeriikozlov, Cra3y,
еще раз повторяю
цикл по номиналам
если не решается по старшим
берем следующую и т.д
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
07.12.2013, 19:52 28
Цитата Сообщение от ValeryS Посмотреть сообщение
или мне задачу полностью решить?
я пытался обратить ваше внимание на то, что жадное решение легко валится.
никакого цикла, кроме динамики здесь быть не может.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.12.2013, 19:53 29
Цитата Сообщение от ValeryS Посмотреть сообщение
цикл по номиналам
если не решается по старшим
берем следующую и т.д
в котрпримере, который я привел решается по старшим номиналам, только ответ будет неправильный:
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
господа прошу комент + критику
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,ans[100];
    signed long mas[100],s,k,min;
    cout << "Enter numnber = ";cin >> n;
    if (n==0) return -1;
    for (int i=1;i<=n;i++)
    {
        cout << "Enter " << i << " = ";cin >> mas[i]; 
    };
    cout << "Enter suma = ";cin >> s;
    for(int q=n;q>=1;q--)
    {
        ans[q]=0;
        k=s;
        for (int i=q;i>=1;i--)
        {
            while (k>=mas[i])
            {
                k-=mas[i];
                ans[q]++;
            }
        };
    }
    min=ans[1];
    for(int i=1;i<=n;i++)
    {
        if (ans[i]<min) 
        {
            min=ans[i];
        }
    }
    if ((min==0)||(min==ans[1]))
    {
        cout << "No solution.";
    }
    else 
    {
        cout << "Answer = " << min;
    }
    cout << "\n";
    system("pause");
}


Добавлено через 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
слушайте
я не господь Бог, могу ошибаться
посему и написал
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
я где то сказал что это правильное и единственное решение?
Цитата Сообщение от salam Посмотреть сообщение
никакого цикла, кроме динамики здесь быть не может.
переведи?
что есть динамика?
согласен косяк
я забивался на российские банкноты а они кратны 10
можно сделать так
не делится нацело на минимальную, берем следующую и т.д
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.12.2013, 20:24 34
Цитата Сообщение от newyork7776 Посмотреть сообщение
контр пример можна?
попробуйте такой тест:
4
1 4 5 16
24
правильный ответ должен быть 3 купюры (16 4 4)

Не по теме:

сейчас компилятора под рукой нет чтобы самому проверить

0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
07.12.2013, 20:29 35
Цитата Сообщение от ValeryS Посмотреть сообщение
что есть динамика?
динамическое программирование.
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
07.12.2013, 20:36 36
Цитата Сообщение от salam Посмотреть сообщение
динамическое программирование.
а по конкретнее?
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
07.12.2013, 21:00 37
http://en.wikipedia.org/wiki/Knapsack_problem
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 21:40 38
Через рекурсию не лучше будет?
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
07.12.2013, 21:57 39
Цитата Сообщение от RQdan Посмотреть сообщение
Через рекурсию не лучше будет?
Через рекурсию по-разному можно.
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 22:34 40
Цитата Сообщение от Dani Посмотреть сообщение
Через рекурсию по-разному можно.
Тоже верно. Просто удивился, что за все обсуждение ни разу не возникло подобное предложение.
0
07.12.2013, 22:34
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.12.2013, 22:34
Помогаю со студенческими работами здесь

Программа вылетает (банкомат)
Здравствуйте, есть задача В некотором государстве в обращении находятся банкноты определенных...

Задача про банкомат
В банкомате есть купюры номиналом, 5000, 2000, 1000, 500 и тд. Но, купюры каждого номинала всего 5...

Банкомат с помощью массивов и циклов
есть 10 карточек. Сначала банкомат спрашивает номер карточки, а потом спрашивает сколько положить...

Оператор goto в коде под Банкомат
Начал изучать C++ и сейчас возникла проблема з оператором goto,немогу понять как сделать так,если...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru