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

Банкомат

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

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

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

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

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

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

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

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

58
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
07.12.2013, 22:37
Студворк — интернет-сервис помощи студентам
Здесь однозначно рюкзак, только способы его реализации могут быть разные, а рекурсивный перебор будет работать только на небольших числах.
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
08.12.2013, 00:19  [ТС]
А как можна через рекурсию?
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 00:41
Цитата Сообщение от newyork7776 Посмотреть сообщение
А как можна через рекурсию?
Вот так:
Кликните здесь для просмотра всего текста
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
57
58
59
#include<iostream>
using namespace std;
 
void Recur_Search(int sum,int n,int mas[],int &num_min,int num_cur,int mas_ef[],int mas_cur[]);
 
void main()
{
    int mas[100],n,sum;
    cout<<"Enter number = ";cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Enter "<<i+1<<" = ";
        cin>>mas[i];
    }
    cout<<"Suma = ";cin>>sum;
    cout<<"Bankomat = ";
    for(int i=0;i<n;i++)
        cout<<mas[i]<<" ";
    cout<<endl;
    int mas_ef[100],mas_cur[100],num_cur=-1,num_min=100,buf=n-1;
 
    Recur_Search(sum,n-1,mas,num_min,num_cur,mas_ef,mas_cur);
    if(num_min==100)cout<<"No solution";
    else
    {
        cout<<"Number of banknotes = "<<num_min<<endl;
        for(int i=0;i<num_min;i++) cout<<mas_ef[i]<<" ";
    }
    cout<<endl; 
}
 
void Recur_Search(int sum,int n,int mas[],int &num_min,int num_cur,int mas_ef[],int mas_cur[])
{
    if(num_cur!=-1)//начальная проверка - необходима из-за первого входа в рекурсивную процедуру
    {
        sum-=mas[n];//формирование суммы, необходимой для дозаполнения
        mas_cur[num_cur]=mas[n];//добавляем номинал к текущей последовательности
        num_cur++;
    }else num_cur=0;
 
    if(sum==0)//проверка, что необходимую сумму набрали.
    {
        if(num_min>num_cur)
        {//запись новой минимальной последовательности номиналов
            for(int i=0;i<num_cur;i++) mas_ef[i]=mas_cur[i];
            num_min=num_cur;
        }
    }
    else
        if((float(sum)/mas[n])<(num_min-num_cur)) //проверка на возможность добить сумму !!!текущими!!! максимальными купюрами
                //за меньшее количество купюр, чем текущее значение. Иначе возврат на предыдущую итерацию!!!
        {
            while((n>=0)&&(sum<mas[n])) n--;//поиск номинала меньше или равного необходимой суммы
            if(n>=0)//если нашелся необходимый номинал - обрабатываем дальше. Иначе возврат на предыдущую итерацию!!!
            {//последовательно прорабатываем все варианты для номиналов вниз
                for(int i=n;i>=0;i--) Recur_Search(sum,i,mas,num_min,num_cur,mas_ef,mas_cur);
            }
        }
}

Все тесты, которые в этой теме выложены проходит на отлично. Что совсем не значит, что не найдется и на него соответствующий болт с резьбой . Тестирование только приветствуется.
Ну, и на мое скромное мнение, программа должна работать довольно оперативно: я вложил туда пару условий, что должны воспрепятствовать тупому перебору всех значений и повысить скорость работы. Но только при соблюдении некоторых условий, а именно: номиналы в массиве банкомата должны быть в обязательном порядке отсортированы по возрастанию. Т.е. или надо вводить значения сразу в такой последовательности, или перед рекурсией провести сортировку.
2
 Аватар для uhx
60 / 60 / 19
Регистрация: 11.07.2013
Сообщений: 305
08.12.2013, 00:59
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
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main()
{
    setlocale(0,"");
  int bt[4] = {
      10,
      50,
      100,
      1000
  };
  int summa;
  cout<<"Введите сумму: ";
  cin>>summa;
while(summa>0){
    if(summa-bt[3]>=0){summa-=bt[3];cout<<bt[3]<<endl;}
    else if(summa-bt[2]>=0){summa-=bt[2];cout<<bt[2]<<endl;}
    else if(summa-bt[1]>=0){summa-=bt[1];cout<<bt[1]<<endl;}
    else if(summa-bt[0]>=0){summa-=bt[0];cout<<bt[0]<<endl;}
}
 
  getch();
}
Можно конечно лучше написать, но это так... на скорую руку)
ЗЫ тапками не кидать, может и не так задание понял, но вроде все верно. Указываем купюры, а дальше циклом расчитываем как хотим.
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 01:05
uhx, к сожалению, программа не будет правильно работать. Если б так было просто, то не растягивали тему на пять страниц.
0
 Аватар для uhx
60 / 60 / 19
Регистрация: 11.07.2013
Сообщений: 305
08.12.2013, 01:45
Цитата Сообщение от RQdan Посмотреть сообщение
uhx, к сожалению, программа не будет правильно работать. Если б так было просто, то не растягивали тему на пять страниц.
А что собственно не так? Какая задача, если не все так просто?
Даны купюры, как я понял, и надо выдать сумму наименьшим кол-ом купюр.
Т.е., сумма 110 - программа выдаст 100 и 10, как самое оптимальное. Все. Или не так?

Добавлено через 10 минут
Да, кстати, вот Ваша программа в действии:


Добавлено через 23 минуты
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
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
  setlocale(0,"");
  int t,bk[256],summa;
  cout<<"Установите кол-во банкнот: ";
  cin>>t;
  for(int i=0;i<t;i++){
      cout<<i+1<<" банкнота = "; // Задаем ценность банкнотам
      cin>>bk[i];
  }
  for(int i=t-1;i>=0;i--){
      for(int j=0;j<t-1;j++)
          if(bk[j]>bk[j+1])swap(bk[j],bk[j+1]); // Пузырьковая сортировка ^^
  }
  cout<<"\nВведите сумму для получения: ";
  cin>>summa;
  cout<<"Банкомат = ";
for(int i=t-1;summa>0;i--){ // Начинаем с самой большой банкноты перебор, что собственно и оптимально.
    if(summa-bk[i]>=0){
        summa-=bk[i];
        cout<<bk[i]<<" "; // Показываем банкноту, которая подошла
        i++; // Чтоб следующий цикл опять начался с этой банкноты, вдруг она подойдет еще раз.
    }
}
 
  getch();
}
Вот собственно и весь код... массив вводить в любом порядке, все вроде соответствует... Автор может под свою задачу код подстроить, если ему надо массив заполнять с файла, это вроде не тяжело.
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
08.12.2013, 01:53  [ТС]
uhx,
1
2
17
ответ 0 0 0 0 0 0 0 0 .....

Добавлено через 4 минуты
Цитата Сообщение от RQdan Посмотреть сообщение
if(num_cur!=-1)//начальная проверка - необходима из-за первого входа в рекурсивную процедуру
а зачем если у нас числа натурал?
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 01:54
Цитата Сообщение от uhx Посмотреть сообщение
Да, кстати, вот Ваша программа в действии:
Ну так неправильные исходные данные - мной было указано, что номиналы должны вводится по возрастанию, а у Вас они по убыванию.
Вот такой результат должен быть:

Цитата Сообщение от uhx Посмотреть сообщение
Т.е., сумма 110 - программа выдаст 100 и 10, как самое оптимальное. Все. Или не так?
Рассмотрим случай, если номиналы 2 55 100, то программа выдаст 100 2 2 2 2 2 - 6 купюр, а правильный ответ: 55 55 - 2 купюры.
0
 Аватар для uhx
60 / 60 / 19
Регистрация: 11.07.2013
Сообщений: 305
08.12.2013, 01:58
Цитата Сообщение от newyork7776 Посмотреть сообщение
uhx,
1
2
17
ответ 0 0 0 0 0 0 0 0 .....
Да, я что-то забыл про "No solution"
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>
#include <conio.h>
using namespace std;
int main()
{
  setlocale(0,"");
  int t,bk[256],summa;
  cout<<"Установите кол-во банкнот: ";
  cin>>t;
  for(int i=0;i<t;i++){
      cout<<i+1<<" банкнота = "; // Задаем ценность банкнотам
      cin>>bk[i];
  }
  for(int i=t-1;i>=0;i--){
      for(int j=0;j<t-1;j++)
          if(bk[j]>bk[j+1])swap(bk[j],bk[j+1]); // Пузырьковая сортировка ^^
  }
  cout<<"\nВведите сумму для получения: ";
  cin>>summa;
  cout<<"Банкомат = ";
for(int i=t-1;i>=0;i--){ // Начинаем с самой большой банкноты перебор, что собственно и оптимально.
    if(summa-bk[i]>=0){
        summa-=bk[i];
        cout<<bk[i]<<" "; // Показываем банкноту, которая подошла
        i++; // Чтоб следующий цикл опять начался с этой банкноты, вдруг она подойдет еще раз.
    }
}
 if(summa!=0){
    system("cls");
    cout<<"No solution";
 }
  getch();
}
Если тебе все записывать в аутпут - то там можно в какой-нибудь массив помещать эти числа (или кол-во купюр, тогда уже просто это будет числом) и при summa==0 выводить все в аутпут.
ЗЫ спать хочу, лень править на случай "нет решения" ... набыдлокодил пару строк Удачи.

Добавлено через 4 минуты
Цитата Сообщение от RQdan Посмотреть сообщение
Ну так неправильные исходные данные - мной было указано, что номиналы должны вводится по возрастанию, а у Вас они по убыванию.
Вот такой результат должен быть:


Рассмотрим случай, если номиналы 2 55 100, то программа выдаст 100 2 2 2 2 2 - 6 купюр, а правильный ответ: 55 55 - 2 купюры.
Да уж, не подумал. Все, мозг не работает.
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
08.12.2013, 01:59  [ТС]
uhx,
попробуйте такой тест:
4
1 4 5 16
24
правильный ответ должен быть 3 купюры (16 4 4)
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:00
Цитата Сообщение от newyork7776 Посмотреть сообщение
а зачем если у нас числа натурал?
эта проверка нужна исключительно ради первого входа в процедуру: тогда нельзя работать с sum, mas_cur и num_cur, которые всередине if'а - я просто не нашел другого способа как обойтись без нее. Если Вам удастся так переписать код, чтобы ее убрать - это будет прекрастно. Но у меня что-то не получается пока .
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
08.12.2013, 02:02
РЮКЗАК - Я ЖЕ ПИСАЛ. Прогуглите, если хотите узнать больше.
0
 Аватар для uhx
60 / 60 / 19
Регистрация: 11.07.2013
Сообщений: 305
08.12.2013, 02:05
Цитата Сообщение от newyork7776 Посмотреть сообщение

а зачем если у нас числа натурал?
А там ведь изначально оно было объявлено как -1. Это для того, чтобы определить первый вход в функцию, потом присваивается значение 0 и идет уже условие будет срабатывать, вроде.
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
08.12.2013, 02:10  [ТС]
Enter number = 1
Enter 1 = 5
Suma = 5
Bankomat = 5
Number of banknotes = 0

Для продолжения нажмите любую клавишу . . .
что-то неправельно

Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   cout<<"Suma = ";cin>>sum;
    cout<<"Bankomat = ";
    for(int i=0;i<n;i++)
        cout<<mas[i]<<" ";
    cout<<endl;
    if (n==1)
    {
        if (sum==mas[0])
        {
            cout << "Answer = 1.\n";
                system("pause");
            return 0;
        }
    }
    int mas_ef[100],mas_cur[100],num_cur=-1,num_min=100,buf=n-1;
Добавлено через 20 секунд
а так можна или нет?
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:18
Цитата Сообщение от newyork7776 Посмотреть сообщение
Enter number = 1
Enter 1 = 5
Suma = 5
Bankomat = 5
Number of banknotes = 0
Для продолжения нажмите любую клавишу . . .
что-то неправельно
А у меня показывает правильно:
Ничего не меняли в коде?

Добавлено через 6 минут
Наверняка убрали проверку - у меня тогда такой же результат появляется, только с ошибкой в придачу )
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
08.12.2013, 02:21  [ТС]
RQdan, спасиба за помошь
спасиба всем
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:24
Всегда пожалуйста!
0
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
11.12.2013, 19:42  [ТС]
посмотрите плис Перебор
0
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 26
19.05.2016, 23:16
Цитата Сообщение от salam Посмотреть сообщение
странно, заходит.

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;
}
Объясните, пожалуйста, код программы
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.05.2016, 23:16

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
59
Ответ Создать тему
Новые блоги и статьи
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков | 1 l I;. . .
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
Генератор паролей (вариант №2)
Maks 30.10.2026
Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .
Генератор паролей (вариант №1)
Maks 29.10.2026
Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru