Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Dendendena
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 11
#1

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

23.07.2015, 12:13. Просмотров 816. Ответов 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
Ответы с готовыми решениями:

Найти все варианты размещения знаков арифметических операций на месте вопросительных знаков
Составить программу, которая нашла все варианты размещения знаков...

Расстановка знаков препинания
По правилу расстановки знаков препинания перед каждым знаком препинания пробел...

Как осуществить ввод только чисел и знаков операций?
мне нужно чтобы при вводе я не мог ничего вводить кроме чисел и математических...

Поставить знаки арифметических операций вместо знаков вопроса в выражении
Вот интересная задача. Сам не мог решить , возможно у вас получится . ...

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

3
ture
528 / 336 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
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
528 / 336 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2015, 11:06

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

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

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


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

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

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