Форум программистов, компьютерный форум 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++ написать прогу банкомат
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Михаил Чернобук
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
 Аватар для newyork7776
346 / 339 / 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
 Аватар для newyork7776
346 / 339 / 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
 Аватар для newyork7776
346 / 339 / 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 17:50  [ТС]     Банкомат #12
salam, знаю
в банке 20 50 а мне нужно 60 ответ невозвожно
а правельно 20 20 20
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.12.2013, 17:52     Банкомат #13
Цитата Сообщение от newyork7776 Посмотреть сообщение
salam, знаю
в банке 20 50 а мне нужно 60 ответ невозвожно
а правельно 20 20 20
например, так, да.

Добавлено через 52 секунды
я попробую что-нибудь загнать, если получится, то напишу вам.
newyork7776
 Аватар для newyork7776
346 / 339 / 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");
}

вот мои наброски
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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;
}
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 18:21  [ТС]     Банкомат #16
Цитата Сообщение от salam Посмотреть сообщение
fill(sum, sum + ml, -1);
* * fill(cnt, cnt + ml, ml);
???

Добавлено через 8 минут
Кликните здесь для просмотра всего текста
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
55
56
#include <iostream>
using namespace std;
int main()
{
    int ost,k=0,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;
            }
        }
         exit;
    }
    cout << "\n\n";
    ans1=0;
    ans2=100;//а что нужно взять за макс колич купюр(с чем сравнить?)
    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");
}

пашет НЕнормально

Добавлено через 1 минуту
возможно нужно + условие (No solution.)
если в наш масив % s !=0 то No solution.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
07.12.2013, 18:22     Банкомат #17
Цитата Сообщение от Михаил Чернобук Посмотреть сообщение
есть номиналы 1,2,5,10
надо выдать 22 рубля
1. Берем 10+10 мало
я бы решал так
циклы while
сначала из суммы вычитаем достоинства максимальных банкнот, потом ниже и т.д
пример банкноты(российские ) 1000 500 100 50 10
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
int n1000=0;
int n500=0;
int n100=0;
int n50=0;
int n10=0;
int t=k;
while(t>=1000)
  {
   t-=1000;
   n1000++;
  };
while(t>=500)
  {
   t-=500;
   n500++;
  };
while(t>=100)
  {
   t-=100;
   n100++;
  };
while(t>=50)
  {
   t-=50;
   n50++;
  };
while(t>=10)
  {
   t-=10;
   n10++;
  };
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.12.2013, 18:23     Банкомат #18
ValeryS, почитайте тему.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
07.12.2013, 18:33     Банкомат #19
Цитата Сообщение от salam Посмотреть сообщение
ValeryS, почитайте тему.
почитал и что?
вижу что по моей идее не всегда набирается
значит на проверять нужно что после всех циклов нужно проверять на t равно 0
если не равно то значит сумму не набрали то значит задача не решена
нужно проверять с другого номинала
на лицо цикл
или мне задачу полностью решить?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2013, 18:48     Банкомат
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 18:48  [ТС]     Банкомат #20
ValeryS, попробовал написать по примеру
Кликните здесь для просмотра всего текста
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
#include <iostream>
using namespace std;
int main()
{
    int n,mas[100],s,k,ans=0;;
    cout << "Enter number = ";cin >> n;
    for (int i=0;i<n;i++)
    {
        cout << "Enter " << i+1 << " = ";cin >> mas[i];
    }
    cout << "Enter Suma = ";cin >> s;
    k=s;
    for (int i=n;i>0;i--)
    {
        while (k>=mas[i])
        {
            k-=mas[i];
            ans++;
        }
    }
    if (k==0)
    {
        cout << "Answer = " << ans;
    }
    else 
    {
        cout << "\nNo solution.";
    }
    cout << "\n";
    system("pause");
}

ерунда получаеться + долго думает

Добавлено через 3 минуты
1
5
5
ответ No solution

Добавлено через 8 минут
ValeryS, вот так правельно!?!?!
Кликните здесь для просмотра всего текста
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
#include <iostream>
using namespace std;
int main()
{
    int n,mas[100],s,k,ans=0;;
    cout << "Enter number = ";cin >> n;
    for (int i=1;i<=n;i++)
    {
        cout << "Enter " << i << " = ";cin >> mas[i];
    }
    cout << "Enter Suma = ";cin >> s;
    for(int i=1;i<=n;i++)
    {
        if (s==mas[i])
        {
            cout << "Answer = 1.\n";
            system("pause");
            return -1;
            
        }
    }
    k=s;
    for (int i=n;i>=1;i--)
    {
        while (k>=mas[i])
        {
            k-=mas[i];
            ans++;
        }
    }
    if (k==0)
    {
        cout << "Answer = " << ans;
    }
    else 
    {
        cout << "\nNo solution.";
    }
    cout << "\n";
    system("pause");
}

попробуйте на правельность
у меня 5/5 ок

Добавлено через 1 минуту
Цитата Сообщение от newyork7776 Посмотреть сообщение
долго думает
запускал счетчик не от mas[n] а от mas[n+1]

Добавлено через 18 секунд
Цитата Сообщение от newyork7776 Посмотреть сообщение
ерунда получаеться
по той же причине
Yandex
Объявления
07.12.2013, 18:48     Банкомат
Ответ Создать тему
Опции темы

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