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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.85
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
#1

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

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

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

Первая строка входных данных содержит натуральное число 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++ Visual Studio 2013 Принцип работы: 1.ввод пароля - введите 1 2. выход -...

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

Банкомат. В чем ошибка? - C++
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Автор: Фёдор Меньшиков, ВГПУ. Реальный текст...

написать прогу банкомат - C++
Вот надо написать прогу банкомат и столкнулся с проблемой вот код bool ATM::login() { cout<<"Username"<<endl; ...

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

Банкомат с помощью массивов и циклов - C++
есть 10 карточек. Сначала банкомат спрашивает номер карточки, а потом спрашивает сколько положить на нее. Потом надо вывести сумму на всех...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Михаил Чернобук
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 14
07.12.2013, 16:41     Банкомат #2
Ну к примеру: есть номиналы 1, 5, 10, 50, 100 рублей.
Банкомату надо выдать 22 рубля. Это можно сделать купюрами:
1) 1, 1, 10, 10 : 4 купюры
2) 1, 1, 5, 5, 10 : 5 купюр
...
n) 1, 1, 1, 1, 1, .. , 1 : 22 купюры и т.д.

Надо найти способ выдачи, при котором количество купюр минимально.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 16:50  [ТС]     Банкомат #3
Цитата Сообщение от newyork7776 Посмотреть сообщение
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую необходимо выдать.
а что именно здесь описано + к вашему примеру?

Добавлено через 35 секунд
5
1 5 10 50 100
а строка S?
Михаил Чернобук
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 14
07.12.2013, 16:54     Банкомат #4
Допустим есть номиналы: 1,3,5. Надо выдать 10 рублей.
Первая строка (количество номиналов) = 3
Вторая строка (номиналы): 1,3,5
Третья строка (сколько надо выдать) : 10
------------------
Ося Бендер пошел разменять 15 рублей. Разменяли на 7 и 8
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 17:02  [ТС]     Банкомат #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int main()
{
    int s,n,mas[100];
    cout << "Enter number = ";cin >> n;
    for(int i=0;i<n;i++)
    {
        cout << "Enter " << i+1 << " = ";
        cin >> mas[i];
    }
    cout << "Suma = ";cin >> s;
    cout << "Bankomat = ";
    for(int i=0;i<n;i++)
    {
        cout << mas[i] << " ";
    }
    cout << "\n";
    system("pause");
}
примерно вот ввод данных?
Михаил Чернобук
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 14
07.12.2013, 17:20     Банкомат #6
Да, так. Дальше комбинаторика
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 17:30  [ТС]     Банкомат #7
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
#include <iostream>
using namespace std;
int main()
{
    int s,n,mas[100],ans;
    cout << "Enter number = ";cin >> n;
    for(int i=0;i<n;i++)
    {
        cout << "Enter " << i+1 << " = ";
        cin >> mas[i];
    }
    cout << "Suma = ";cin >> s;
    cout << "Bankomat = ";
    for(int i=0;i<n;i++)
    {
        cout << mas[i] << " ";
    }
    if (s<mas[0])
    {
 
        cout << "\nNo solution.";
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if (s==mas[i])
            {
                cout << "\nAnswer = 1.";
                exit;
            }
        }
    }
    cout << "\n";
    system("pause");
}
вот условие.Правельно я думаю или нет?

Добавлено через 1 минуту
или проверять после нахожден мин колич купюр?

Добавлено через 1 минуту
Цитата Сообщение от Михаил Чернобук Посмотреть сообщение
Дальше комбинаторика
А что именно:размещения, перестановки, сочетания?

Добавлено через 2 минуты
А возможно решить задание через дин прог%, или можна сделать через 1 перемен?

Добавлено через 1 минуту
Я могу решить задание через жадный алгоритм но он не правельно пашет

Добавлено через 1 минуту
Взять мак купюру а потом к ней + макс-1 -) если оно больше чем нужно вивести то вывод невозможен
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 17:32     Банкомат #8
вообще решается динамикой. но если в лоб, то порядок 108 будет. это много. надо думать.
сложность у решения O(S * k), где S - искомая сумма, k - количество банкнот.
Михаил Чернобук
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 14
07.12.2013, 17:36     Банкомат #9
Я бы последний вариант взял, самая крупная купюра + добирать по аналогии остальными, более мелкими.
Следующая итерация с менее крупной и добрать более мелкими; гденить запомнить минимум купюр и т.д.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 17:37     Банкомат #10
Цитата Сообщение от Михаил Чернобук Посмотреть сообщение
Я бы последний вариант взял, самая крупная купюра + добирать по аналогии остальными, более мелкими.
Следующая итерация с менее крупной и добрать более мелкими; гденить запомнить минимум купюр и т.д.
к такому решению очень легко подбираются контртесты.
Михаил Чернобук
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 14
07.12.2013, 17:48     Банкомат #11
Хотя, на первый взгляд, решение кажется правильным, но уверенности что по такому алгоритму будет найден минимум купюр, у меня нет. Я не знаю строгого докачательства, но:
Например
есть номиналы 1,2,5,10
надо выдать 22 рубля
1. Берем 10+10 мало
добавляем 10 много
добавляем 5 много
добавляем 2 нормально
итого 3 купюры.
2. Пробуем 10+5+5 уже 3 купюры. Не годится
3. Пробуем 5+5+5 уже 3 купюры, недобор
Ну что-то вроде того, только я не знаю при других раскладах как (другие номиналы и суммы), голова дымит, точно доказать, что это рабочий алгоритм как не знаю
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 17:50  [ТС]     Банкомат #12
salam, знаю
в банке 20 50 а мне нужно 60 ответ невозвожно
а правельно 20 20 20
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 17:52     Банкомат #13
Цитата Сообщение от newyork7776 Посмотреть сообщение
salam, знаю
в банке 20 50 а мне нужно 60 ответ невозвожно
а правельно 20 20 20
например, так, да.

Добавлено через 52 секунды
я попробую что-нибудь загнать, если получится, то напишу вам.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 17:53  [ТС]     Банкомат #14
Кликните здесь для просмотра всего текста
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
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
int main()
{
    int k=0,i,s,n,mas[100],ans1,ans2;
    cout << "Enter number = ";cin >> n;
    for(int i=0;i<n;i++)
    {
        cout << "Enter " << i+1 << " = ";
        cin >> mas[i];
    }
    cout << "Suma = ";cin >> s;
    cout << "Bankomat = ";
    for(int i=0;i<n;i++)
    {
        cout << mas[i] << " ";
    }
    if (s<mas[0])
    {
 
        cout << "\nNo solution.";
        exit;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if (s==mas[i])
            {
                cout << "\nAnswer = 1.";
                exit;
            }
        }
    }
    cout << "\n\n\n";
    ans1=0;ans2=mas[n];
    for (int q=0;q<n;q++)
    {
        if (s>mas[q])
        {
            while (s>k)
            {
                k+=mas[q];
                ans1++;
            }
            if (ans1<ans2){ans2=ans1;};
            ans1=0;
            k=0;
        }
    }
    cout << "Answer = " << ans2;
    cout << "\n";
    system("pause");
}

вот мои наброски
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2013, 18:09     Банкомат
Еще ссылки по теме:

Банкомат Run-Time Check Failure #3- The variable 'Sheets (и Moneym)' is being used without being initialized - C++
Помогите разобраться с ошибками, недавно начал учить С++ и не понятно что с ними делать Условие: Банкомат свойства: •...

Создать класс "Банкомат" с реализацией функций банкомата. - C++
Всем привет. Есть задание: создать класс &quot;банкомат&quot; с реализацией функций банкомата. То есть это определение клиента (можно по номеру карты...

Реализовать класс "Банкомат" - C++
есть две задачи, хочу их реализовать в С++, используя классы..., я новичок в программировании... Создать класс «банкомат» для работы с...

Класс "Банкомат" - C++
Класс «Банкомат». В классе должны содержаться поля для хранения идентификационного номера банкомата, информация о текущей сумме денег,...

Банкомат - JavaFX
Эта программка имитирует работу банкомата....есть баланс и есть сумма ...и две кнопки:снять и пополнить.....не получается связать кнопки с...


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

Или воспользуйтесь поиском по форуму:
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 18:09     Банкомат #15
странно, заходит.

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
const int ml = 1000010;
int sum[ml], cnt[ml];
 
int main()
{
    int n, S;
    int a[100];
    cin >> n;
    for(int i=0; i < n; ++i)
        cin >> a[i];
    cin >> S;
    fill(sum, sum + ml, -1);
    fill(cnt, cnt + ml, ml);
    cnt[0] = 0;
    for(int i=0; i < S; ++i)
        if(cnt[i] < ml)
            for(int j=0; j < n; ++j)
                if(i + a[j] < ml && cnt[i + a[j]] > cnt[i] + 1) {
                    cnt[i + a[j]] = cnt[i] + 1;
                    sum[i + a[j]] = i;
                }
    if(cnt[S] == ml) cout << "No solution" << endl;
    else {
        int j = S;
        while(sum[j] != -1) {
            cout << j - sum[j] << " ";
            j = sum[j];
        }
    }
    return 0;
}
Yandex
Объявления
07.12.2013, 18:09     Банкомат
Ответ Создать тему
Опции темы

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