Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

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

Система банкомат - 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 карточек. Сначала банкомат спрашивает номер карточки, а потом спрашивает сколько положить на нее. Потом надо вывести сумму на всех...

58
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 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.
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,205
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++;
  };
1
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 750
07.12.2013, 18:23 #18
ValeryS, почитайте тему.
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,205
07.12.2013, 18:33 #19
Цитата Сообщение от salam Посмотреть сообщение
ValeryS, почитайте тему.
почитал и что?
вижу что по моей идее не всегда набирается
значит на проверять нужно что после всех циклов нужно проверять на t равно 0
если не равно то значит сумму не набрали то значит задача не решена
нужно проверять с другого номинала
на лицо цикл
или мне задачу полностью решить?
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 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 Посмотреть сообщение
ерунда получаеться
по той же причине
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,205
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])
{
при чем здесь номиналы?
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 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
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,205
07.12.2013, 19:33 #23
Цитата Сообщение от newyork7776 Посмотреть сообщение
ValeryS, а как можна сразу узнать No solution
очень просто
остаток от деления на младший номинал
например у тебя младшая купюра 10 руб
а нужно выдать 1234 рубля
четыре рубля ну никак не выплатим
пишем
C++
1
2
if(n%10!=0)
 printf("No solution");
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 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");
}
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 19:36 #25
Эта задача решается ДП (salam реализовал именно этот вариант).
Решение задачи жадным алгоритмом, типа:
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
циклы while
сначала из суммы вычитаем достоинства максимальных банкнот, потом ниже и т.д
будет выдавать неправильный результат.
Вот контрпример:
3
1 70 100
140
Правильный ответ будет 2 банкноты номиналом 70
Жадный алгоритм выдаст другой результат.
0
Max Dark
шКодер самоучка
1851 / 1651 / 603
Регистрация: 09.10.2013
Сообщений: 3,678
Записей в блоге: 6
Завершенные тесты: 2
07.12.2013, 19:40 #26
ValeryS, неверно, если есть банкноты большие минимальной, но не делющиеся нацело на минимальную
Например
5
10 25 50 100 500
75
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,205
07.12.2013, 19:46 #27
valeriikozlov, Cra3y,
еще раз повторяю
цикл по номиналам
если не решается по старшим
берем следующую и т.д
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 750
07.12.2013, 19:52 #28
Цитата Сообщение от ValeryS Посмотреть сообщение
или мне задачу полностью решить?
я пытался обратить ваше внимание на то, что жадное решение легко валится.
никакого цикла, кроме динамики здесь быть не может.
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 19:53 #29
Цитата Сообщение от ValeryS Посмотреть сообщение
цикл по номиналам
если не решается по старшим
берем следующую и т.д
в котрпримере, который я привел решается по старшим номиналам, только ответ будет неправильный:
100 1 1 1 1 1 1 1 1 ... и т.д. всего 40 единиц
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 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.
0
07.12.2013, 20:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2013, 20:04
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

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