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

Банкомат - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.85
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 15:48     Банкомат #1
задание
Кликните здесь для просмотра всего текста
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.

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

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

Напишите нормально условие задание,а то я не могу понять условие.
Можна пример(прошу не код а пояснение задание).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2013, 15:48     Банкомат
Посмотрите здесь:

C++ Программа вылетает (банкомат)
C++ Программа-банкомат!
C++ Класс "Банкомат"
JavaFX Банкомат
C++ написать прогу банкомат
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
07.12.2013, 18:52     Банкомат #21
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])
{
при чем здесь номиналы?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
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
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
07.12.2013, 19:33     Банкомат #23
Цитата Сообщение от newyork7776 Посмотреть сообщение
ValeryS, а как можна сразу узнать No solution
очень просто
остаток от деления на младший номинал
например у тебя младшая купюра 10 руб
а нужно выдать 1234 рубля
четыре рубля ну никак не выплатим
пишем
C++
1
2
if(n%10!=0)
 printf("No solution");
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
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");
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 19:36     Банкомат #25
Эта задача решается ДП (salam реализовал именно этот вариант).
Решение задачи жадным алгоритмом, типа:
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
циклы while
сначала из суммы вычитаем достоинства максимальных банкнот, потом ниже и т.д
будет выдавать неправильный результат.
Вот контрпример:
3
1 70 100
140
Правильный ответ будет 2 банкноты номиналом 70
Жадный алгоритм выдаст другой результат.
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
07.12.2013, 19:40     Банкомат #26
ValeryS, неверно, если есть банкноты большие минимальной, но не делющиеся нацело на минимальную
Например
5
10 25 50 100 500
75
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
07.12.2013, 19:46     Банкомат #27
valeriikozlov, Cra3y,
еще раз повторяю
цикл по номиналам
если не решается по старшим
берем следующую и т.д
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.12.2013, 19:52     Банкомат #28
Цитата Сообщение от ValeryS Посмотреть сообщение
или мне задачу полностью решить?
я пытался обратить ваше внимание на то, что жадное решение легко валится.
никакого цикла, кроме динамики здесь быть не может.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 19:53     Банкомат #29
Цитата Сообщение от ValeryS Посмотреть сообщение
цикл по номиналам
если не решается по старшим
берем следующую и т.д
в котрпримере, который я привел решается по старшим номиналам, только ответ будет неправильный:
100 1 1 1 1 1 1 1 1 ... и т.д. всего 40 единиц
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
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.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.12.2013, 20:08     Банкомат #31
2 4 6 11 15
выводит 2.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 20:16  [ТС]     Банкомат #32
2
4 6
11
а 15 что ето?

Добавлено через 2 минуты
ну правельно
4
2 4 6 11
15
ответ 2 = 11+4

Добавлено через 2 минуты
Вот сайт на котором я время убиваю
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
07.12.2013, 20:23     Банкомат #33
слушайте
я не господь Бог, могу ошибаться
посему и написал
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
я где то сказал что это правильное и единственное решение?
Цитата Сообщение от salam Посмотреть сообщение
никакого цикла, кроме динамики здесь быть не может.
переведи?
что есть динамика?
согласен косяк
я забивался на российские банкноты а они кратны 10
можно сделать так
не делится нацело на минимальную, берем следующую и т.д
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 20:24     Банкомат #34
Цитата Сообщение от newyork7776 Посмотреть сообщение
контр пример можна?
попробуйте такой тест:
4
1 4 5 16
24
правильный ответ должен быть 3 купюры (16 4 4)

Не по теме:

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

salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.12.2013, 20:29     Банкомат #35
Цитата Сообщение от ValeryS Посмотреть сообщение
что есть динамика?
динамическое программирование.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
07.12.2013, 20:36     Банкомат #36
Цитата Сообщение от salam Посмотреть сообщение
динамическое программирование.
а по конкретнее?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 21:00     Банкомат #37
http://en.wikipedia.org/wiki/Knapsack_problem
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 21:40     Банкомат #38
Через рекурсию не лучше будет?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 21:57     Банкомат #39
Цитата Сообщение от RQdan Посмотреть сообщение
Через рекурсию не лучше будет?
Через рекурсию по-разному можно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2013, 22:34     Банкомат
Еще ссылки по теме:

C++ Банкомат. В чем ошибка?
Банкомат Java SE
Банкомат Run-Time Check Failure #3- The variable 'Sheets (и Moneym)' is being used without being initialized C++

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

Или воспользуйтесь поиском по форуму:
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 22:34     Банкомат #40
Цитата Сообщение от Dani Посмотреть сообщение
Через рекурсию по-разному можно.
Тоже верно. Просто удивился, что за все обсуждение ни разу не возникло подобное предложение.
Yandex
Объявления
07.12.2013, 22:34     Банкомат
Ответ Создать тему
Опции темы

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