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

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

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

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

07.12.2013, 15:48. Просмотров 3809. Ответов 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++
Доброго времени суток. Помогите, пожалуйста, решить задачу. В банкомат заряжаются купюры различных номиналов в неограниченном...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 20:08     Банкомат #31
2 4 6 11 15
выводит 2.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
07.12.2013, 20:16  [ТС]     Банкомат #32
2
4 6
11
а 15 что ето?

Добавлено через 2 минуты
ну правельно
4
2 4 6 11
15
ответ 2 = 11+4

Добавлено через 2 минуты
Вот сайт на котором я время убиваю
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,736
07.12.2013, 20:23     Банкомат #33
слушайте
я не господь Бог, могу ошибаться
посему и написал
Цитата Сообщение от ValeryS Посмотреть сообщение
я бы решал так
я где то сказал что это правильное и единственное решение?
Цитата Сообщение от salam Посмотреть сообщение
никакого цикла, кроме динамики здесь быть не может.
переведи?
что есть динамика?
согласен косяк
я забивался на российские банкноты а они кратны 10
можно сделать так
не делится нацело на минимальную, берем следующую и т.д
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2013, 20:24     Банкомат #34
Цитата Сообщение от newyork7776 Посмотреть сообщение
контр пример можна?
попробуйте такой тест:
4
1 4 5 16
24
правильный ответ должен быть 3 купюры (16 4 4)

Не по теме:

сейчас компилятора под рукой нет чтобы самому проверить

salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
07.12.2013, 20:29     Банкомат #35
Цитата Сообщение от ValeryS Посмотреть сообщение
что есть динамика?
динамическое программирование.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,736
07.12.2013, 20:36     Банкомат #36
Цитата Сообщение от salam Посмотреть сообщение
динамическое программирование.
а по конкретнее?
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 21:00     Банкомат #37
http://en.wikipedia.org/wiki/Knapsack_problem
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 21:40     Банкомат #38
Через рекурсию не лучше будет?
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 21:57     Банкомат #39
Цитата Сообщение от RQdan Посмотреть сообщение
Через рекурсию не лучше будет?
Через рекурсию по-разному можно.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 22:34     Банкомат #40
Цитата Сообщение от Dani Посмотреть сообщение
Через рекурсию по-разному можно.
Тоже верно. Просто удивился, что за все обсуждение ни разу не возникло подобное предложение.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
07.12.2013, 22:37     Банкомат #41
Здесь однозначно рюкзак, только способы его реализации могут быть разные, а рекурсивный перебор будет работать только на небольших числах.
newyork7776
347 / 340 / 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
57 / 57 / 6
Регистрация: 11.07.2013
Сообщений: 303
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();
}
Можно конечно лучше написать, но это так... на скорую руку)
ЗЫ тапками не кидать, может и не так задание понял, но вроде все верно. Указываем купюры, а дальше циклом расчитываем как хотим.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2013, 01:05     Банкомат
Еще ссылки по теме:

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
08.12.2013, 01:05     Банкомат #45
uhx, к сожалению, программа не будет правильно работать. Если б так было просто, то не растягивали тему на пять страниц.
Yandex
Объявления
08.12.2013, 01:05     Банкомат
Ответ Создать тему
Опции темы

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