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

Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
24.06.2011, 23:56     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #1
У покупателя есть n монет достоинством H(1),...,H(n). У продавца есть m монета достоинством B(1),...,B(1). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2011, 23:56     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача
Посмотрите здесь:

Точная P-ая степень C++
Обработать строку так, чтобы чтобы в ней остались только те слова которые содержат буквы и цифры C++
Почему тип char не может делать вот так += C++
C++ Дописать программу так, чтобы в массив вводились как целые числа так и вещественные
C++ нужно чтоб нашлась страна и все данные об этой стране вывелись в таблицу...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitry_gdv
 Аватар для Dmitry_gdv
64 / 64 / 5
Регистрация: 18.03.2010
Сообщений: 351
25.06.2011, 15:40     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #2


может

или не может

а вдруг он и может и не может?
а как ты думаш?
JeyKip
53 / 45 / 2
Регистрация: 23.06.2011
Сообщений: 122
25.06.2011, 18:21     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #3
заинтересовала задача...поэтому, интересно было сделать...дает правильный ответ с высокой вероятностью...

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <cstdlib>
#include <time.h>
#include <set>
#include <math.h>
using namespace std;
 
int  Summ(int * mas, int count_el);
set<int> CombinationSumm (int * mas, int count_el);
int Sochetanie (int n, int m);
int CountSet (set<int> s);
int CanZdacha (set<int> prod, set<int> pokup, int price);
 
void main()
{
    
    setlocale(0,"");
    int m_prod, m_pokup;
    int *nom_prod, *nom_pokup;
    int price;
 
    printf("%s","Введите количество монет у продавца и покупателя соответственно\n");
    scanf("%d %d",&m_prod, &m_pokup);
 
    nom_prod = new int [m_prod];
    nom_pokup = new int [m_pokup];
 
    printf("%s","Введите номиналы монет у продавца\n");
    for (int i=0; i<m_prod; i++)
        scanf("%d",&nom_prod[i]);
 
    printf("%s","Введите номиналы монет у покупателя\n");
    for (int i=0; i<m_pokup; i++)
        scanf("%d",&nom_pokup[i]);
 
    printf("%s","Введите стоимость покупки\n");
    scanf("%d", &price);
 
    //хватит ли денег на покупку
    if (price > Summ(nom_pokup, m_pokup))
    {
        printf("%s", "\nПокупатель не может приобрести покупку. У него недостаточно денег");
        getch();
        exit(0);
    }
    else
    {
        int z = CanZdacha(CombinationSumm (nom_prod, m_prod), CombinationSumm (nom_pokup, m_pokup), price);
        switch (z)
        {
        case 0:
            printf("%s","\nКлиент дал под расчет");
            break;
        case 1:
            printf("%s", "\nЗдача есть");
            break;
        case 2:
            printf("%s", "\nЗдачи нет");
            break;
        }
    } 
    getch();
}
 
int Summ(int * mas, int count_el)
{
    int summ = 0;
    for (int i = 0; i<count_el; i++)
        summ+=mas[i];
    return summ;
}
 
set<int> CombinationSumm (int * mas, int count_el)
{
    int sum = 0;
    int money = 0;
    set<int> sets;
    set<int> sets_2;
    set<int>::iterator it1 = sets.begin();
    set<int>::iterator it2 = sets_2.begin();
 
    srand(time(0));
 
    for (int i=1; i<=count_el; i++)
    {
        for (int j=0; j<Sochetanie(count_el, i)*5; j++)
        {
            do
            {
                sets_2.insert(rand()%count_el);
            }
            while (CountSet(sets_2) != i);
 
            it2 = sets_2.begin();
            while (it2 != sets_2.end())
            {
                sum+=mas[*it2];
                it2++;
            }
            sets_2.clear();
            sets.insert(sum);
            sum = 0;
        }
    }
    return sets;
}
 
int Sochetanie (int n, int m)
{
    int p = 1;
    for (int i = m; i>0; i--)
        p*=(n--);
    return p;
}
 
int CountSet (set<int> s)
{
    set<int>::iterator it = s.begin();
    int count = 0;
    while (it != s.end())
    {
        count++;
        it++;
    }
    return count;
}
 
int CanZdacha (set<int> prod, set<int> pokup, int price)
{
    int zdacha = 2;
    set<int>::iterator it1 = prod.begin();
    set<int>::iterator it2 = pokup.begin();
 
    while (it1 != prod.end())
    {
        it2 = pokup.begin();
        while (it2 != pokup.end())
        {
            if ((*it2 - price) == *it1)
            {
                zdacha = 1;
                break;
            }
            else if ((*it2 - price) == 0)
            {
                zdacha = 0;
                break;
            }
            it2++;
        }
        it1++;
    }
    return zdacha;
}
sandye51
25.06.2011, 18:32
  #4

Не по теме:

жесть, ассоциативные контейнеры STL и стандартный вывод С

povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 07:51  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #5
Цитата Сообщение от JeyKip Посмотреть сообщение
заинтересовала задача...поэтому, интересно было сделать...дает правильный ответ с высокой вероятностью...

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <cstdlib>
#include <time.h>
#include <set>
#include <math.h>
using namespace std;
 
int  Summ(int * mas, int count_el);
set<int> CombinationSumm (int * mas, int count_el);
int Sochetanie (int n, int m);
int CountSet (set<int> s);
int CanZdacha (set<int> prod, set<int> pokup, int price);
 
void main()
{
    
    setlocale(0,"");
    int m_prod, m_pokup;
    int *nom_prod, *nom_pokup;
    int price;
 
    printf("%s","Введите количество монет у продавца и покупателя соответственно\n");
    scanf("%d %d",&m_prod, &m_pokup);
 
    nom_prod = new int [m_prod];
    nom_pokup = new int [m_pokup];
 
    printf("%s","Введите номиналы монет у продавца\n");
    for (int i=0; i<m_prod; i++)
        scanf("%d",&nom_prod[i]);
 
    printf("%s","Введите номиналы монет у покупателя\n");
    for (int i=0; i<m_pokup; i++)
        scanf("%d",&nom_pokup[i]);
 
    printf("%s","Введите стоимость покупки\n");
    scanf("%d", &price);
 
    //хватит ли денег на покупку
    if (price > Summ(nom_pokup, m_pokup))
    {
        printf("%s", "\nПокупатель не может приобрести покупку. У него недостаточно денег");
        getch();
        exit(0);
    }
    else
    {
        int z = CanZdacha(CombinationSumm (nom_prod, m_prod), CombinationSumm (nom_pokup, m_pokup), price);
        switch (z)
        {
        case 0:
            printf("%s","\nКлиент дал под расчет");
            break;
        case 1:
            printf("%s", "\nЗдача есть");
            break;
        case 2:
            printf("%s", "\nЗдачи нет");
            break;
        }
    } 
    getch();
}
 
int Summ(int * mas, int count_el)
{
    int summ = 0;
    for (int i = 0; i<count_el; i++)
        summ+=mas[i];
    return summ;
}
 
set<int> CombinationSumm (int * mas, int count_el)
{
    int sum = 0;
    int money = 0;
    set<int> sets;
    set<int> sets_2;
    set<int>::iterator it1 = sets.begin();
    set<int>::iterator it2 = sets_2.begin();
 
    srand(time(0));
 
    for (int i=1; i<=count_el; i++)
    {
        for (int j=0; j<Sochetanie(count_el, i)*5; j++)
        {
            do
            {
                sets_2.insert(rand()%count_el);
            }
            while (CountSet(sets_2) != i);
 
            it2 = sets_2.begin();
            while (it2 != sets_2.end())
            {
                sum+=mas[*it2];
                it2++;
            }
            sets_2.clear();
            sets.insert(sum);
            sum = 0;
        }
    }
    return sets;
}
 
int Sochetanie (int n, int m)
{
    int p = 1;
    for (int i = m; i>0; i--)
        p*=(n--);
    return p;
}
 
int CountSet (set<int> s)
{
    set<int>::iterator it = s.begin();
    int count = 0;
    while (it != s.end())
    {
        count++;
        it++;
    }
    return count;
}
 
int CanZdacha (set<int> prod, set<int> pokup, int price)
{
    int zdacha = 2;
    set<int>::iterator it1 = prod.begin();
    set<int>::iterator it2 = pokup.begin();
 
    while (it1 != prod.end())
    {
        it2 = pokup.begin();
        while (it2 != pokup.end())
        {
            if ((*it2 - price) == *it1)
            {
                zdacha = 1;
                break;
            }
            else if ((*it2 - price) == 0)
            {
                zdacha = 0;
                break;
            }
            it2++;
        }
        it1++;
    }
    return zdacha;
}
эта программа не запускается помогите исправит ошибки в программе
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 07:54     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #6
Цитата Сообщение от povtiasd051 Посмотреть сообщение
эта программа не запускается помогите исправит ошибки в программе
Какой у вас компилятор? Если борланд - забудьте.
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 07:57  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #7
Цитата Сообщение от diagon Посмотреть сообщение
Какой у вас компилятор? Если борланд - забудьте.
На борланде не пашет что, а сможешь выложит вариант который работает с на нем
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 08:01     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #8
С таким условием - нет.
Цитата Сообщение от povtiasd051 Посмотреть сообщение
У продавца есть m монета достоинством B(1),...,B(1).
Как это понимать? У продавца m монет достоинством в 1 единицу?
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
08.07.2011, 08:04     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #9
врядли тут у кого то борланд есть, так что "точить" самому придётся
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 08:06  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #10
Цитата Сообщение от diagon Посмотреть сообщение
С таким условием - нет.

Как это понимать? У продавца m монет достоинством в 1 единицу?
В этом месте ошибка не B(1),...B(1) должен быт там вот так B(1),...B(m)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 08:16     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #11
Со убожеством борланда я не знаком, однако алгоритм примерно такой:
Перебираете все возможные комбинации из монет покупателя, сумма которых больше S, и к ним подбираете все возможные комбинации из монет продавца. Если монеты покупателя - монеты продавца == S то сделка возможна...
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 08:45  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #12
Цитата Сообщение от diagon Посмотреть сообщение
Со убожеством борланда я не знаком, однако алгоритм примерно такой:
Перебираете все возможные комбинации из монет покупателя, сумма которых больше n, и к ним подбираете все возможные комбинации из монет продавца. Если монеты покупателя - монеты продавца == S то сделка возможна...
На этом спасибо а ты не знаешь кто его сможет сделать

Добавлено через 4 минуты
Цитата Сообщение от diagon Посмотреть сообщение
Со убожеством борланда я не знаком, однако алгоритм примерно такой:
Перебираете все возможные комбинации из монет покупателя, сумма которых больше S, и к ним подбираете все возможные комбинации из монет продавца. Если монеты покупателя - монеты продавца == S то сделка возможна...
Дружище на Паскале Сможешь выложит

Добавлено через 19 минут
Кто хорош шарит в borland С++ помогите да
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
08.07.2011, 09:26     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #13
да ни у кого нету тут borland c++, в каком году его последняя версия вышла? Есть шанс что во фрилансе кто-нибудь за умеренную плату специально для тебя скачает его и будет колбаситься с ним, а так врядли
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 09:32  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #14
Цитата Сообщение от pito211 Посмотреть сообщение
да ни у кого нету тут borland c++, в каком году его последняя версия вышла? Есть шанс что во фрилансе кто-нибудь за умеренную плату специально для тебя скачает его и будет колбаситься с ним, а так врядли
че так слабо с этим языком вроде он как бы самый популярный чем Паскал
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 09:35     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #15
а тем что он уже 10 лет не обновляется, а прогресс не стоит на месте, как известно.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
08.07.2011, 09:48     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #16
с языком всё в порядке, а вот последняя версия твоего компилятора выходила в прошлом веке. Поэтому сам понимаешь...
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
08.07.2011, 23:29  [ТС]     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #17
Цитата Сообщение от pito211 Посмотреть сообщение
с языком всё в порядке, а вот последняя версия твоего компилятора выходила в прошлом веке. Поэтому сам понимаешь...
А кто знает какая последняя версия этого компилятора скиньте силку на этот компилятор
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
09.07.2011, 05:17     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #18
www.google.ru
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.07.2011, 08:28     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #19
Маленькая поправка:

Цитата Сообщение от diagon Посмотреть сообщение
Перебираете все возможные комбинации из монет покупателя, сумма которых больше S
Правильнее будет: сумма которых больше и равна S

А для большого кол-ва монет есть более быстрое решение, чем перебор всех возможных комбинаций.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2014, 22:59     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача
Еще ссылки по теме:

Сколько единиц товара сможет купить покупатель и какова его сдача? C++
C++ Составить алгоритм и программу, которая определит сколько досок надо купить, чтобы поставить сплошной забор
Сделать так, чтобы функция возвращала как целые, так и дробные значения C++

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

Или воспользуйтесь поиском по форуму:
nikitos7832
 Аватар для nikitos7832
3 / 3 / 0
Регистрация: 26.03.2012
Сообщений: 27
07.06.2014, 22:59     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача #20
Писал недавно аналогичную задачу... может кому поможет
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "stdafx.h"
#include <fstream>
#include <ctime>
using namespace std;
bool inc(int *a, int n)                                 //2 perebor, doshli do konca - return false
{                 
    int i=0;
while((a[i]!=0)&&(i<n))
    i++;
if (i<n){
for (int j=0; j<i; j++)
    a[j]=0;
    a[i]=1;
    return true;}
else return false;
}
 
void zero(int *a, int n)                                //obnulenie 2-massiva
{                
    for (int i=0; i<n; i++)
        a[i]=0;
}
 
 
int cash(int *a, int *b, int n){
int s=0;
for (int i=0; i<n; i++)
    s+=a[i]*b[i];
return s;
} 
 
    
int main()
{
    ifstream in("in.txt");
    ofstream out("out.txt");
    int s=0, *a, *b, *p1, *p2, n, m, st=0;
    in >> n;
    a=new int[n];
    p1=new int[n];
    zero(p1,n);
    in >> m;
    b=new int[m];
    p2=new int[m];
    zero(p2,m);
    in >> s;
    for(int i=0; i<n; i++)
    {
        in >> a[i];
    }
    for(int i=0; i<m; i++)
    {
        in >> b[i];
    }
    int i=0, razn=0, zd=0;
    while(inc(p1,n))
    {
        zero(p2,m);
        st=cash(a,p1,n);
        razn=st-s;
        if (st>s)
            while(inc(p2,m))
                {
                    zd=cash(b,p2,m);
                    if(zd==razn)
                    {
                        out << "Yes";
                        return 0;
                    }
                }
        if (st==s)
        {
            out << "Yes";
            return 0;
        }
    }
    out << "No";
    return 0;
}
З.Ы. есть 1 но! задача олимпиадная - т.е. на нее есть ограничения (например время выполнения - не более 3 секунд). Так вот при очень больших тестах (сумма поядка 2 000 000, и количиство монет и у продавца и у покупателя ~ 100) программа вылетает за пределы выполнения в 3 секунды.

Добавлено через 4 минуты
забыл сказать... ничего присущего сугобо MVS не использовал поэтому по идее на Борланде тоже должно работать
Yandex
Объявления
07.06.2014, 22:59     Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача
Ответ Создать тему
Опции темы

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