Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
1

Расставить между числами знаки "+" и "-" так, чтобы значение выражение стало равно S

19.03.2017, 12:20. Просмотров 1642. Ответов 16
Метки нет (Все метки)

Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.

Входные данные
В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= Xi <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000.

Выходные данные
Если получить требуемый результат невозможно, вывести "No solution", если можно, то вывести равенство. Если решение не единственное, вывести любое.

Примеры
входные данные
3 13
7 3 9
выходные данные
7-3+9=13
входные данные
3 3
7 10 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;
int f(int b, int y)
{
    if (y==1)
    return b;
    if (y==0)
    return 1;
    int r=b;
    for (int u=2;u<=y;u++)
    b*=r;
    return b;
}
int main()
{
    int N,q=0,w=0,a,S,S_0=0;;
    bool g[32768][32768];
    cin >> N >> S;
    for (int o=0;o<N;o++)
    cin >> g[o][0];
    for (int p=0;p<=f(2,N-1);p++)
    {
        a=p;
        while (a>0)
        {
            if (a%2==0)
            {
                q++;
                a/=2;
            }
            else
            {
                g[q+1][w]=-g[1+q][w];
                q++;
                a/=2;
            }
        }
        for (int k=0;k<N;k++)
        S_0+=g[k][w];
        if (S_0==S)
        {
            cout << g[0][0];
            for (int v=1;v<N;v++)
            if (g[v][w]>0)
            cout << '+' << g[v][w];
            else 
            cout << g[v][w];
            cout << '=' << S;
        }
        S_0=0;
        q=0;
        w++;
    }
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2017, 12:20
Ответы с готовыми решениями:

Сколько существует способов расставить между цифр знаки "+" и "-"
Вот сама задача - {удалено} Не могу сделать норм перебор

Нужно расставить между числами знаки + или - таким образом, чтобы получилось выражение, значение которого равно s и вывести его на экран
Доброго времени суток Задание: дано n чисел и число s. Нужно расставить между числами знаки + или...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;,...

"Вычеркнуть" 5 цифр из числа так, чтобы число стало наименьшим
Здравствуйте дорогие форумчане! Я впервые у вас на форуме, прошу простить если будут какие-то...

Расставить между данными числами знаки +/-, чтобы значение получившегося выражения было равно заданному целому S
Даны N целых чисел X1, X2, …, XN. Требуется расставить между ними знаки «+» и «-» так, чтобы...

16
DemolitionMan
130 / 156 / 87
Регистрация: 06.04.2016
Сообщений: 992
19.03.2017, 14:21 2
Цитата Сообщение от KO0 Посмотреть сообщение
входные данные
3 3
7 10 0
выходные данные
No solution
- перед 7 нельзя "-" ставить?

Добавлено через 5 минут
Ну опишите программу, что-то она по-моему сложная для своего понимания. Нужно описать main.

Добавлено через 1 минуту
Цитата Сообщение от KO0 Посмотреть сообщение
C++
1
2
3
4
5
6
7
int main()
{
* * int N,q=0,w=0,a,S,S_0=0;;
* * bool g[32768][32768];
* * cin >> N >> S;
* * for (int o=0;o<N;o++)
* * cin >> g[o][0];
- почему тип-то булевский у массива, если тут нужен int.

Добавлено через 8 минут
Что делает функция f()?

Добавлено через 1 минуту
b^y возвращает что-ли? Так есть же функция pow() из библиотеки math.h.

Добавлено через 1 час 30 минут
Не могу что-то понять, что здесь не работает:http://cpp.sh/9unkj
Вроде так правильно написал, но не работает полностью ввод элементов в массив(?) и не работает сам проект, как будто дальше после ввода вообще ничего не работает. Профессионалы могут прокомментировать что-нибудь? Косяк CPP SHELL?

Добавлено через 1 минуту
А онлайн компиляторы есть с отладчиком?
0
Байт
Эксперт C
20456 / 12985 / 2729
Регистрация: 24.12.2010
Сообщений: 27,174
19.03.2017, 16:06 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[N];  // Заданные числа
int M = (1 << (N-1));
int sum, b;
for(b=1; b<M; b++) {
 sum = a[0];
 for(int i=0; i<N-1; i++)
   if ((b>>i)&1) sum += a[i+1];
   else         sum -= a[i+1];
 if (sum==S) {
  cout << a[0];
  for(int i=0; i<N-1; i++)
    cout << ((b>>i)&1) ? '+' : '-' << a[i+1];
  cout << "=" << S << endl;
  break;
 }
}
if (b==M) cout << "No solution\n";
Вот так как-то....
0
DemolitionMan
130 / 156 / 87
Регистрация: 06.04.2016
Сообщений: 992
19.03.2017, 16:54 4
http://ideone.com/71FDvV
0
19.03.2017, 16:54
altmax
185 / 52 / 19
Регистрация: 23.12.2016
Сообщений: 159
Завершенные тесты: 1
19.03.2017, 20:28 5
я такое уже решал с месяц назад, прям один в один
Между заданными числами расставить знаки сложения и вычитания так, чтобы в итоге получилось указанное число
0
Байт
Эксперт C
20456 / 12985 / 2729
Регистрация: 24.12.2010
Сообщений: 27,174
19.03.2017, 21:26 6
У меня ошибочка в строке 4, конечно, for(b=0;...
А идея простая. Набор операций (+-) представляется в виде битовой шкалы. 1 - Плюсик, 0 - Минусик. Перебор их всех осуществляется простым прибавлением 1 до 2N-1 (до всех плюсиков). Прием довольно стандартный - перебрать все подмножества небольшого множества.
0
no swear
178 / 154 / 80
Регистрация: 01.07.2016
Сообщений: 863
Завершенные тесты: 1
19.03.2017, 22:02 7
Цитата Сообщение от Байт Посмотреть сообщение
C++
1
2
int M = (1 << (N-1));
if ((b>>i)&1)
Что эти значки означают "<<", ">>", "&"?
0
altmax
185 / 52 / 19
Регистрация: 23.12.2016
Сообщений: 159
Завершенные тесты: 1
19.03.2017, 22:33 8
Цитата Сообщение от Байт Посмотреть сообщение
А идея простая. Набор операций (+-) представляется в виде битовой шкалы. 1 - Плюсик, 0 - Минусик. Перебор их всех осуществляется простым прибавлением 1 до 2N-1 (до всех плюсиков).
Пробовал сделать и так. С рекурсией проще получилось и быстрее работает.
0
Байт
Эксперт C
20456 / 12985 / 2729
Регистрация: 24.12.2010
Сообщений: 27,174
19.03.2017, 22:52 9
Цитата Сообщение от no swear Посмотреть сообщение
Что эти значки означают "<<", ">>", "&"?
Это битовые операции.
Пусть есть число int b = 45 = 32+8+4+1 = 01011012
"<<" - сдвиг влево b << 2 = 010110100
">>" - сдвиг вправо b>>2 = 01011
"&" побитовое умножение, выделение одного или группы битов b&1 = 01, b&2 = 0, b&4 = 100, b&7 = 0101

Добавлено через 1 минуту
Есть и другие битовые операции. Пошукай в интернете.
1
Njibx
0 / 0 / 0
Регистрация: 19.03.2017
Сообщений: 4
19.03.2017, 23:13 10
не могли бы вы мне помочь с с++?
0
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
19.03.2017, 23:31  [ТС] 11
что такое S
0
_Ivana
4041 / 1881 / 235
Регистрация: 01.03.2013
Сообщений: 5,117
Записей в блоге: 16
20.03.2017, 01:08 12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
const int N=24;
int a[N], n, S;
char o[N];
 
bool f(int i, int s) {
    return i==n ? s==S : (o[i]='-') && f(i+1,s-a[i]) || (o[i]='+') && f(i+1,s+a[i]); }
 
void show() { cout<<a[0]; for(int i=1; i<n; i++) cout<<o[i]<<a[i]; cout<<"="<<S; }
 
int main() {
    cin>>n>>S; for(int i=0; i<n; i++) cin>>a[i];
    if (f(1, a[0])) show(); else cout<<"No solution";
}
Но конечно можно влепить отсечения, т.к. числа в наборе неотрицательны.
0
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
22.03.2017, 23:26  [ТС] 13
Я так понимаю в ошибку в моей программе вы не нашли?
0
Байт
Эксперт C
20456 / 12985 / 2729
Регистрация: 24.12.2010
Сообщений: 27,174
22.03.2017, 23:34 14
Цитата Сообщение от KO0 Посмотреть сообщение
Я так понимаю в ошибку в моей программе вы не нашли?
Правильно понимаете. Вашу программу вообще видеть не хочется, не то что бы еще искать в ней блох. Чего стоит один этот массивчик
Цитата Сообщение от KO0 Посмотреть сообщение
C++
1
bool g[32768][32768];
Да и оформлен ваш код безо всякого уважения к читающему. Однобуквенные идентификаторы, лишенные намека на смысл, полное отсутствие комментариев. Предлагать такой код для прочтения - себя не уважать.
0
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
23.03.2017, 00:06  [ТС] 15
Моя идея основывается на переборе в лоб знаков, с помощью перевода из десятичной с.с. в двоичную. Например число входных чисел 4 (Х1, Х2, Х3, Х4), программа должна перебрать от 0000 до 1111, того 2^4 проверки, но только 0 - "+", 1 - "-". N чисел, 2^N - проверки.

Добавлено через 22 минуты
Теперь понятно?
0
DemolitionMan
130 / 156 / 87
Регистрация: 06.04.2016
Сообщений: 992
23.03.2017, 07:45 16
Цитата Сообщение от KO0 Посмотреть сообщение
Например число входных чисел 4 (Х1, Х2, Х3, Х4), программа должна перебрать от 0000 до 1111, того 2^4 проверки, но только 0 - "+", 1 - "-". N чисел, 2^N - проверки.
- по-моему тут уже ошибка. Потому что если 4 числа, то знака между ними 3(т.е. на 1 меньше), соответственно число комбинации будет от 000 до 111, или 2N-1,т.е. 8 для 4-х чисел. Не умеете Вы программы писать.
0
KO0
0 / 0 / 0
Регистрация: 10.03.2017
Сообщений: 18
23.03.2017, 07:49  [ТС] 17
Спасибо уже не надо программа работает

Добавлено через 42 секунды
DemolitionMan я знаю просто ошибся

Добавлено через 1 минуту
Вот сама программа
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 F(int q)
{
    int w=1;
    for (int e=1;e<=q;e++)
    w*=2;
    return w;
}
 
int main()
{
    int N,S,t,k=0;
    bool h=0;
    bool m[23][83886]; int r[24];
    cin >> N >> S;
    for (int q=0;q<N;q++)
    cin >> r[q];
    for (int w=0;w<F(N-1);w++)
    {
        t=w;
        for (int y=0;y<N-1;y++)
        {
            if (t%2!=0)
            m[y][w]=1;
            else
            m[y][w]=0;
            t/=2;
        }
    }
    for (int c=0;c<F(N-1);c++)
    {
        for (int p=0;p<N-1;p++)
        if (m[p][c]==1)
        k+=-r[p+1];
        else
        k+=r[p+1];
        if (k+r[0]==S)
        {
            cout << r[0];
            for (int p=0;p<N-1;p++)
            if (m[p][c]==1)
            cout << -r[p+1];
            else
            cout << '+' << r[p+1];
            cout << '=' << S;
            h=1;
        }
        else
        k=0;
    }
    if (h==0)
    cout << "No solution";
    return 0;
}
Добавлено через 1 минуту
На массив в 83886 не смотрите его можете подбирать с учетом возможности
0
23.03.2017, 07:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2017, 07:49

Как сделать так, чтобы scanf в переменную double мог считывать с клавиатуры не только "0,01", но и "0.01"
Помогите!) Не знаю, искал, не нашел, возможно ли вообще. Чтобы и так и так понимал.

Как сделать, так чтобы i и j можно было вводить самому "i" И "j" в цикле, есть программа
#include &lt;iostream&gt; using namespace std; int main() {int a=0,b=0; int i=0; cout&lt;&lt;&quot;Vvedite...

Как сделать так, чтобы введенное с клавиатуры слово "helllo" в памяти сохранялось в виде "Hello".
Здравствуйте. Подскажите пожалауйста как сделать чтоб согда я вводу с клавиатуры helllo, в памяти...


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

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

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