Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Dendendena
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 11
#1

Расстановка знаков операций - C++

23.07.2015, 12:13. Просмотров 556. Ответов 3
Метки нет (Все метки)

Не получается решить задачу,не могу понять в чем проблема.Вроде все правильно все выводит,но проваливает почти все тесты.Помогите найти в чем проблема!
Даны 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
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
# include <iostream> 
using namespace std; 
int main()
{
    int a[1000],d[1000],n,s;
    char b[1000],c[1000];
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i];
        
    }
    for(int i=2;i<=n-1;i++){
        int t=a[i];
        int maxi=abs(a[i]);
        int nummax=i;
        for(int j=i+1;j<=n;j++){
            if(abs(a[j])>maxi){
                maxi=a[j];
                nummax=j;
            }
        }
    a[i]=maxi;
    a[nummax]=t;
    }
    int sum=a[1];
    for(int i=2;i<=n;i++){
        if(abs(s-sum+a[i])>abs(s-sum-a[i])){
            sum=sum+a[i];
            for(int j=2;j<=n;j++ ){
                if(a[i]==d[j]){
                    b[j-1]='+'; 
                }
 
            }
                
        }
        else{
            sum=sum-a[i];
            for(int j=2;j<=n;j++ ){
                if(a[i]==d[j]){
                    b[j-1]='-'; 
                }
 
            }
        }
        }
    if(sum==s){
        for(int i=1;i<=n;i++){
            cout<<d[i]<<b[i];               
                
        
        }cout<<"="<<s;
    }
    else{
        cout<<"No solution";
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2015, 12:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Расстановка знаков операций (C++):

Расстановка знаков препинания - C++
По правилу расстановки знаков препинания перед каждым знаком препинания пробел отсутствует, а после него обязательно стоит пробел. Учитывая...

Классы для арифметических операций с большими числами (целые числа более 10 знаков) - C++
C++ ,Классы для арифметических операций с большими числами(целые числа более 10 знаков), и бывают ли стандартные классы поддерживающие...

Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 - C++
Составить программу, которая бы нашла все варианты размещения знаков арифметических операций +,-,* на месте вопросительных знаков в...

Определить количество вхождений строки из n знаков в строку из k знаков - C++
Всем доброй ночи ребят. Вы последняя надежда:( помогите пожалуйста 2 задачи решить последняя ночь( сразу препод говорил, что контрольную...

Вставить между цифрами 1, 2,..., 8, 9 в данном порядке, знак одной из 4-х арифметических операций так, чтобы результат восьми послед-х операций =100 - C++
Вычисления проводятся слева-направо, ни одна операция не имеет приоритета. Добавлено через 2 минуты задача вынесла моск, прошу помочь

Последовательность из цифр, букв и знаков. Подсчитать чего больше и составить строки только из цифр, букв и знаков - C++
Дана последовательность состоящая из цифр, букв и знаков пунктуации в произвольном порядке. Подсчитать чего больше и составить строки...

3
ture
441 / 334 / 126
Регистрация: 27.11.2014
Сообщений: 1,042
23.07.2015, 13:20 #2
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
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
using std::string;
#include <string>
using std::to_string;
 
bool next(int *,int,int,int,int,string);
 
int main(){
    setlocale(LC_ALL, "rus");
    //Спрашиваем
    cout << "Укажите количество целых чисел и требуемый результат" << endl;
    int n, s;
    cin >> n >> s;
    int * m = new int[n];
    for(int i = 0; i < n; i++)
        cin >> m[i];
 
    //Рекурсивный поиск вариантов
    string strR = "";
    if(!next(m, 1, n, s, m[0], to_string(m[0])))
        cout << "Нет вариантов" << endl;
 
    delete[] m;
    system("pause");
    return 0;
}
 
bool next(int * m, int k, int n, int s, int sum, string strR){
    bool isOk = false;
    if(k == n && sum == s){
        cout << strR << "=" << s << endl;
        isOk = true;
    }else
        for(int i = k; i < n; i++){
            isOk = isOk || next(m, k + 1, n, s, sum + m[i], strR + '+' + (m[i] >= 0 ? to_string(m[i]) : "(" + to_string(m[i]) + ')'));
            isOk = isOk || next(m, k + 1, n, s, sum - m[i], strR + '-' + (m[i] >= 0 ? to_string(m[i]) : "(" + to_string(m[i]) + ')'));
        }   
    return isOk;
}
1
Dendendena
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 11
23.07.2015, 17:58  [ТС] #3
Но что не так с моим кодом?Вроде вес верно выводит)
0
ture
441 / 334 / 126
Регистрация: 27.11.2014
Сообщений: 1,042
24.07.2015, 11:06 #4
c[1000] не используется

Массивы a[1000] и d[1000] заполняются с индекса 1, а не 0.

Массивы a[1000] сортируется по абсолютной величине за исключением первого элемента (это не замечание, просто для понимания моего восприятия кода, ведь коментов нет).

int sum сумма строится по критерию приближения к 0, а знак сохраняется в элемент массива b[1000], соответствующего d[1000] (но поиск на основе сравнения значений, что сразу исключает повторяющиеся числа и требует их различности).
Критерий требует выбора 13-(7+3), т.е. 3 со знаком "+".

Добавлено через 16 часов 38 минут
Я там ошибся со знаком в конце. Верность критерия опровергнуть не могу.
1
24.07.2015, 11:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2015, 11:06
Привет! Вот еще темы с ответами:

Расстановка кирпичей - C++
Сколькими способами можно замостить 3xn прямоугольник при помощи 2x1 доминошек? Ниже наведен пример замощения такими плитками...

«Расстановка кубиков» - C++
Программа играющая в игру «Расстановка кубиков». Игральный кубик можно перекатывать по клеткам поля n*m. Причём, если клетка имеет вес i,...

Расстановка 8 ферзей - C++
Привет всем, слушайте, вот исходник на С++ задача &lt;&lt;о восьми ферзях&gt;&gt;: #include&lt;iostream&gt; #include&lt;cmath&gt; #include&quot;pent&quot; void...

Расстановка игральных костей - C++
Программа играющая в игру «Расстановка игральных костей». Задана частичная двумерная сетка. В некоторых позициях сетки расставлены...


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

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

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