Форум программистов, компьютерный форум 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++ написать прогу банкомат
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 22:37     Банкомат #41
Здесь однозначно рюкзак, только способы его реализации могут быть разные, а рекурсивный перебор будет работать только на небольших числах.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
08.12.2013, 00:19  [ТС]     Банкомат #42
А как можна через рекурсию?
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 00:41     Банкомат #43
Цитата Сообщение от 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);
            }
        }
}

Все тесты, которые в этой теме выложены проходит на отлично. Что совсем не значит, что не найдется и на него соответствующий болт с резьбой . Тестирование только приветствуется.
Ну, и на мое скромное мнение, программа должна работать довольно оперативно: я вложил туда пару условий, что должны воспрепятствовать тупому перебору всех значений и повысить скорость работы. Но только при соблюдении некоторых условий, а именно: номиналы в массиве банкомата должны быть в обязательном порядке отсортированы по возрастанию. Т.е. или надо вводить значения сразу в такой последовательности, или перед рекурсией провести сортировку.
uhx
 Аватар для uhx
56 / 56 / 6
Регистрация: 11.07.2013
Сообщений: 300
08.12.2013, 00:59     Банкомат #44
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();
}
Можно конечно лучше написать, но это так... на скорую руку)
ЗЫ тапками не кидать, может и не так задание понял, но вроде все верно. Указываем купюры, а дальше циклом расчитываем как хотим.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 01:05     Банкомат #45
uhx, к сожалению, программа не будет правильно работать. Если б так было просто, то не растягивали тему на пять страниц.
uhx
 Аватар для uhx
56 / 56 / 6
Регистрация: 11.07.2013
Сообщений: 300
08.12.2013, 01:45     Банкомат #46
Цитата Сообщение от RQdan Посмотреть сообщение
uhx, к сожалению, программа не будет правильно работать. Если б так было просто, то не растягивали тему на пять страниц.
А что собственно не так? Какая задача, если не все так просто?
Даны купюры, как я понял, и надо выдать сумму наименьшим кол-ом купюр.
Т.е., сумма 110 - программа выдаст 100 и 10, как самое оптимальное. Все. Или не так?

Добавлено через 10 минут
Да, кстати, вот Ваша программа в действии:
http://joxi.ru/uploads/prod/2013/12/...1d0a5a593a.png

Добавлено через 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();
}
Вот собственно и весь код... массив вводить в любом порядке, все вроде соответствует... Автор может под свою задачу код подстроить, если ему надо массив заполнять с файла, это вроде не тяжело.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
08.12.2013, 01:53  [ТС]     Банкомат #47
uhx,
1
2
17
ответ 0 0 0 0 0 0 0 0 .....

Добавлено через 4 минуты
Цитата Сообщение от RQdan Посмотреть сообщение
if(num_cur!=-1)//начальная проверка - необходима из-за первого входа в рекурсивную процедуру
а зачем если у нас числа натурал?
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 01:54     Банкомат #48
Цитата Сообщение от uhx Посмотреть сообщение
Да, кстати, вот Ваша программа в действии:
http://joxi.ru/uploads/prod/2013/12/...1d0a5a593a.png
Ну так неправильные исходные данные - мной было указано, что номиналы должны вводится по возрастанию, а у Вас они по убыванию.
Вот такой результат должен быть:http://joxi.ru/OZijUtg5CbAhLIF8ND4

Цитата Сообщение от uhx Посмотреть сообщение
Т.е., сумма 110 - программа выдаст 100 и 10, как самое оптимальное. Все. Или не так?
Рассмотрим случай, если номиналы 2 55 100, то программа выдаст 100 2 2 2 2 2 - 6 купюр, а правильный ответ: 55 55 - 2 купюры.
uhx
 Аватар для uhx
56 / 56 / 6
Регистрация: 11.07.2013
Сообщений: 300
08.12.2013, 01:58     Банкомат #49
Цитата Сообщение от 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 Посмотреть сообщение
Ну так неправильные исходные данные - мной было указано, что номиналы должны вводится по возрастанию, а у Вас они по убыванию.
Вот такой результат должен быть:http://joxi.ru/OZijUtg5CbAhLIF8ND4


Рассмотрим случай, если номиналы 2 55 100, то программа выдаст 100 2 2 2 2 2 - 6 купюр, а правильный ответ: 55 55 - 2 купюры.
Да уж, не подумал. Все, мозг не работает.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
08.12.2013, 01:59  [ТС]     Банкомат #50
uhx,
попробуйте такой тест:
4
1 4 5 16
24
правильный ответ должен быть 3 купюры (16 4 4)
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:00     Банкомат #51
Цитата Сообщение от newyork7776 Посмотреть сообщение
а зачем если у нас числа натурал?
эта проверка нужна исключительно ради первого входа в процедуру: тогда нельзя работать с sum, mas_cur и num_cur, которые всередине if'а - я просто не нашел другого способа как обойтись без нее. Если Вам удастся так переписать код, чтобы ее убрать - это будет прекрастно. Но у меня что-то не получается пока .
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
08.12.2013, 02:02     Банкомат #52
РЮКЗАК - Я ЖЕ ПИСАЛ. Прогуглите, если хотите узнать больше.
uhx
 Аватар для uhx
56 / 56 / 6
Регистрация: 11.07.2013
Сообщений: 300
08.12.2013, 02:05     Банкомат #53
Цитата Сообщение от newyork7776 Посмотреть сообщение

а зачем если у нас числа натурал?
А там ведь изначально оно было объявлено как -1. Это для того, чтобы определить первый вход в функцию, потом присваивается значение 0 и идет уже условие будет срабатывать, вроде.
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
08.12.2013, 02:10  [ТС]     Банкомат #54
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 секунд
а так можна или нет?
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:18     Банкомат #55
Цитата Сообщение от newyork7776 Посмотреть сообщение
Enter number = 1
Enter 1 = 5
Suma = 5
Bankomat = 5
Number of banknotes = 0
Для продолжения нажмите любую клавишу . . .
что-то неправельно
А у меня показывает правильно: Смотреть

Ничего не меняли в коде?

Добавлено через 6 минут
Наверняка убрали проверку - у меня тогда такой же результат появляется, только с ошибкой в придачу )
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
08.12.2013, 02:21  [ТС]     Банкомат #56
RQdan, спасиба за помошь
спасиба всем
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 02:24     Банкомат #57
Всегда пожалуйста!
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:42  [ТС]     Банкомат #58
посмотрите плис Перебор
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2016, 23:16     Банкомат
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Rigbi
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 26
19.05.2016, 23:16     Банкомат #59
Цитата Сообщение от salam Посмотреть сообщение
странно, заходит.

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
Объявления
19.05.2016, 23:16     Банкомат
Ответ Создать тему
Опции темы

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