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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 61, средняя оценка - 4.66
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

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

04.07.2011, 16:47. Просмотров 8191. Ответов 19
Метки нет (Все метки)

Доброго времени суток
Задание: дано n чисел и число s. Нужно расставить между числами знаки + или - таким образом, чтобы получилось выражение, значение которого равно s и вывести его на экран. Если это невозможно - вывести "No solution". Полное условие .
Пример:
input.txt:
3 10 (n = 3)
15 25 30
output.txt:
15+25-30=10
Рекурсию под эту задачу я вроде как сделал, считает различные суммы, но как вывести выражение - не могу додуматься.
Хранить его вроде как негде, строка будет засорятся, да и загнать это выражение в строку проблематично будет...
Либо можно вывести весь массив до n, но где взять знаки...
Думаю, что нужно поставить какое-то условие в рекурсию, чтобы при его выполнении она выводила число, знак и завершала один вызов, и так пока не выведет все выражение. Но как это сделать слабо представляю.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
void pro(int * nums, int i, int sum, int n, int s){
    if ( i ){
                    pro(nums, i - 1, nums[i-1] + sum, n, s);
        if (i != n) pro(nums, i - 1, nums[i-1] - sum, n, s);
    }
    else if (sum == s){
        //Вывод выражения
        exit(0);
    }
}
 
int main(){
    int nums[24], n, s;
    std::cin >> n >> s;
    for (int i = 0; i < n; ++i)
        std::cin >> nums[i];
    pro(nums, n, 0, n, s);
    std::cout << "No solution\n";
    return 0;
}
P.S. интересует именно рекурсия, есть и другие способы решения этой задачи, но я хочу разобраться до конца с рекурсией.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2011, 16:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нужно расставить между числами знаки + или - таким образом, чтобы получилось выражение, значение которого равно s и вывести его на экран (C++):

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

Между заданными числами расставить знаки сложения и вычитания так, чтобы в итоге получилось указанное число - C++
Простая задачка из школьной олимпиады (задача на асмп №366). У меня превышает лимит времени. Если есть другие пути поделитесь пж ...

Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом - C++
Имеются цифры 1, 2, 3, 4, 5, 6, 7, 8, 9. Необходимо расставить между ними любое количество знаков &quot;плюс&quot; или &quot;минус&quot; так, чтобы получить...

Расставить знаки между цифрами так, чтобы получилось заданное число - C++
Помогите разобраться с алгоритмом. Вот задача: Имеются цифры 1, 2, 3, 4, 5, 6, 7, 8, 9. Необходимо расставить между ними любое...

Расставить знаки между числами от 1 до 9, чтобы получить заданное число - C++
Доброе время суток. Помогите разобраться с задачей, пожалуйста. Нужно расставить знаки &quot;+&quot;, &quot;-&quot; между числами от 1 до 9,...

В выражении расставить знаки арифметических операций, чтобы получилось заданное число - C++
В арифметическом выражении 1*2*3*4*5 вместо звездочек расставить арифметические операции + , - , * , / так, чтобы получилось число...

19
CEBEP
107 / 107 / 9
Регистрация: 21.03.2010
Сообщений: 444
04.07.2011, 17:14 #2
По моему здесь проблема с рекурсией всётаки. Ведь вы углубляетесь в рекурсию не сохраняя, плюс или минус был выбран в данной ветке... из суммы это не может следовать однозначно. Нужно ещё один параметр, скажем char sign, и углубление будет выглядеть так:
C++
1
2
3
4
        if ( i ){
                            pro(nums, i - 1, nums[i-1] + sum, n, s, '+');
                if (i != n) pro(nums, i - 1, nums[i-1] - sum, n, s, '-');
        }
тогда можно будет организовать вывод при подъёме из верно выбранной ветви рекурсии, а проверить, удалось ли найти такую ветвь можно просто добавив в конце
C++
1
2
if((i == n)//Мы на вершине рекурсии
        std::cout << "No solution\n";
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.07.2011, 18:07  [ТС] #3
Да, я делал также, даже переменную также обозвал =)
Получилось нечто такое
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
bool back = false;
void pro(int * nums, int i, int sum, int n, int s, char sign = '+'){
        if ( i && !back ){
                            pro(nums, i - 1, nums[i-1] + sum, n, s, '+');
                if (i != n) pro(nums, i - 1, nums[i-1] - sum, n, s, '-');
        }
        else if (sum == s) back = true;
        if (back && i < n - 1) std::cout << nums[i] << sign;
}
 
int main(){
        int nums[24], n, s;
        std::cin >> n >> s;
        for (int i = 0; i < n; ++i)
                std::cin >> nums[i];
        pro(nums, n, 0, n, s);
        if (!back) std::cout << "No solution\n";
        else std::cout << nums[n-1] << '=' << s << std::endl;
        return 0;
}
Однако выводятся лишние переменные и знаки из других вызовов рекурсии...
Да и глобальная переменная мне совсем не нравится.
Плюс иду я с конца и на каждом числе идет вызов рекурсии, т.е. в потолок упираться буду достаточно много раз.

В общем не хватает только условия для 10 строки, если ветка правильная, то выводить.
C++
1
if (back && i < n - 1 && !(ветка левая) )
Как бы это реализовать еще...
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.07.2011, 18:53 #4
Цитата Сообщение от diagon Посмотреть сообщение
Да и глобальная переменная мне совсем не нравится.
А я наоборот при решении олимпиадных задач часто ими пользуюсь. Кстати я заметил что Вы любитель писать самые короткие коды. Тогда один из методов сокращения кода - это использование глобальных переменных (в параметрах функции ее не нужно будет передовать).
Кстати могу показать свое решение этой задачи, если не осилите свое.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.07.2011, 19:02  [ТС] #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А я наоборот при решении олимпиадных задач часто ими пользуюсь. Кстати я заметил, что Вы любитель писать самые короткие коды. Тогда один из методов сокращения кода - это использование глобальных переменных (в параметрах функции ее не нужно будет передовать).
Кстати могу показать свое решение этой задачи, если не осилите свое.
Я знаю, но это считается плохим стилем =)
Сначала решу по нормальному, потому начну быдлокодить. Иначе просто не пойму как все это работает и не смогу достаточно оптимизировать код.
Да и не такой уж я и любитель, только два первых места =) Ну и в этой задаче я явно буду первым, здесь первое место 320 символов, вполне реально.
Да осилю рано или поздно, я настойчивый... Мне только алгоритм нужен. Сейчас завел массив знаков, с некоторыми багами, но вроде работает... А хочется красивый выход из рекурсии >_<
0
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
04.07.2011, 20:12 #6

Не по теме:

а свой быдлокод с глобальными переменными писать можно?


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
#include <fstream>
 
using namespace std;
 
char znaki[24];
 
int next(int *in, int pos, int size, int sum, int my_sum){
    extern char znaki[24];
    if(pos<size){
 
        if( next(in, pos+1, size, sum + in[pos], my_sum) ){
            znaki[pos]='+';
            return 1;
        }
 
        if( next(in, pos+1, size, sum - in[pos], my_sum) ){
            znaki[pos]='-';
            return 1;
        }
 
        return 0;
    }
    else{
        if (sum==my_sum) return 1;
        else return 0;
    }
}
 
 
int main(){
    extern char znaki[24];
 
    ifstream ifs("input.txt");
    ofstream ofs("output.txt");
 
    int in[24], size, i, my_sum;
 
    ifs >> size;
 
    ifs >> my_sum;
 
     for(i=0;i<size;++i)
        ifs>>in[i];
 
    if (!next(in, 1, size, in[0], my_sum)){
        ofs<<"No solution";
        return 0;
    }
 
 
ofs<<in[0];
 
for( i =1; i<size; ++i){
        if (znaki[i]=='+')  ofs<<"+";
        else  ofs<<"-";
        
        ofs<<in[i];
}
 
   ofs << "="<<my_sum;
 
   return 0;
 
}
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.07.2011, 20:21  [ТС] #7
Цитата Сообщение от no0ker Посмотреть сообщение

Не по теме:

а свой быдлокод с глобальными переменными писать можно?


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
#include <fstream>
 
using namespace std;
 
char znaki[24];
 
int next(int *in, int pos, int size, int sum, int my_sum){
    extern char znaki[24];
    if(pos<size){
 
        if( next(in, pos+1, size, sum + in[pos], my_sum) ){
            znaki[pos]='+';
            return 1;
        }
 
        if( next(in, pos+1, size, sum - in[pos], my_sum) ){
            znaki[pos]='-';
            return 1;
        }
 
        return 0;
    }
    else{
        if (sum==my_sum) return 1;
        else return 0;
    }
}
 
 
int main(){
    extern char znaki[24];
 
    ifstream ifs("input.txt");
    ofstream ofs("output.txt");
 
    int in[24], size, i, my_sum;
 
    ifs >> size;
 
    ifs >> my_sum;
 
     for(i=0;i<size;++i)
        ifs>>in[i];
 
    if (!next(in, 1, size, in[0], my_sum)){
        ofs<<"No solution";
        return 0;
    }
 
 
ofs<<in[0];
 
for( i =1; i<size; ++i){
        if (znaki[i]=='+')  ofs<<"+";
        else  ofs<<"-";
        
        ofs<<in[i];
}
 
   ofs << "="<<my_sum;
 
   return 0;
 
}
У меня похоже получилось, но вместо глобальной переменной я таскал за собой указатель на массив в аргументе...
Однако у меня есть какой-то баг, который я не могу выловить - правильно выводит знаки далеко не всегда. А трассировать рекурсию я не умею, тупо путаюсь >_<
P.S. зачем писать extern? Массив ведь и из функций виден.
P.P.S. напишу завтра с нуля...
1
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
04.07.2011, 20:31 #8
P.S. зачем писать extern? Массив ведь и из функций виден.
это ошибка? =(

просто хотел объявить массив. без объявления как то некрасиво. очевидно, что
C++
1
char znaki[24];
работать не будет. решил использовать extern.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.07.2011, 16:53  [ТС] #9
Цитата Сообщение от no0ker Посмотреть сообщение
это ошибка? =(

просто хотел объявить массив. без объявления как то некрасиво. очевидно, что
C++
1
char znaki[24];
работать не будет. решил использовать extern.
Ну так можно вообще его в функциях не объявлять, и так работать будет =) Ну или для наглядность писать еще ::znaki .

Часов 6 убил, но так и не смог выловить баг...
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
#include <iostream>
void pro(int * nums, char * signs, int i, int sum, int n, int s, char sign = '+'){    
    signs[i] = sign;
    //пока не достигнут первый элемент
    if ( i ){  
                pro(nums, signs, i - 1, nums[i-1] + sum, n, s, '+');
                pro(nums, signs, i - 1, nums[i-1] - sum, n, s, '-');
                
    }
    else if (sum == s){ 
    //если достигнут первый элемент и получившаяся сумма
    //равна заданной, то выводим массивы на экран
        for (i = 0; i < n - 1; ++i)
            std::cout << nums[i] << signs[i];
        std::cout << nums[i] << '=' << sum;
        std::cout << std::endl;
        exit(0);
    }
}
  
int main(){
        int nums[24], n, s;
        char signs[25];
        std::cin >> n >> s;
        for (int i = 0; i < n; ++i)
                std::cin >> nums[i];
        pro(nums, signs, n, 0, n, s);
        std::cout << "No solution\n";
        return 0;
}
Вроде все просто и логично, а баг не ловится...
15+25-30=10 выводит, а вот при n = 3, s = 0 и числах 3 6 3 выводит 3-6-3=0.
Что странно, пробовал с глобальным флагом как в #3 делать, ошибка была точно такой-же. Могу зайти под пингвином и соответствующий код скинуть...
0
grizlik78
Эксперт С++
1971 / 1464 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
05.07.2011, 16:57 #10
Цитата Сообщение от diagon Посмотреть сообщение
Вроде все просто и логично, а баг не ловится...
15+25-30=10 выводит, а вот при n = 3, s = 0 и числах 3 6 3 выводит 3-6-3=0.
Выглядит так, как будто вычисления происходят справа налево.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.07.2011, 16:58  [ТС] #11
Цитата Сообщение от grizlik78 Посмотреть сообщение
Выглядит так, как будто вычисления происходят справа налево.
Так и есть. Так удобнее просто =) И в идеале я хочу заставить работать этот код
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
#include <iostream>
bool back = false;
int s, res;
void pro(int * nums, int i, int sum, int n, char sign = '+'){
                if ( i && !back ){
                    pro(nums, i - 1, nums[i-1] + sum, n, '+');
                    pro(nums, i - 1, nums[i-1] - sum, n, '-');
                }
                else if (sum == s) back = true;
                if (back && i < n - 1 && sum == s) {
                    std::cout << nums[i] << sign;
                    if (sign == '+') s -= nums[i];
                    else s += nums[i];
                }
}
 
int main(){
        int nums[24], n;
        std::cin >> n >> s;
        res = s;
        for (int i = 0; i < n; ++i)
                std::cin >> nums[i];
        pro(nums, n, 0, n);
        if (!back) std::cout << "No solution\n";
                else std::cout << nums[n-1] << '=' << res << std::endl;
        return 0;
}
Если идти слева направо, так не получится.
Что странно, ошибка в обоих кодах одна и та же.
0
grizlik78
Эксперт С++
1971 / 1464 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
05.07.2011, 17:01 #12
Ну так справа налево оба варианта корректные
15+(25-30)=10
3-(6-3)=0
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.07.2011, 17:04  [ТС] #13
Аааа...
Мне хочется матюгаться.
Получается, что справа налево не получится?
В книге Меньшикова предложена именно такая рекурсия.
0
grizlik78
Эксперт С++
1971 / 1464 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
05.07.2011, 17:08 #14
Операция сложения ассоциативна, её можно выполнять в любом порядке.
Операция вычитания ассоциативной не является. То есть либо рассматривать числа как отрицательные и положительные и использовать только сложение, либо, если числа только неотрицательные, при использовании вычитания менять все последующие знаки.
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.07.2011, 11:41  [ТС] #15
В общем рекурсия вообще кривая какая-то у меня получилась, так что я забил на нее...
Решил через двоичную систему =)
Как ни странно, в книге Меньшикова написано, что такое решение не будет проходить по времени.
Однако же прошло за 0.97 =)
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
#include <iostream>
#include <cstdio>  //for freopen
#include <cstdlib> //for exit
int signs[24]; //чтобы не занулять вручную
void bin_inc(int * arr, int size){ //инкремент двоичного числа
    ++arr[size-1];
    for (int i = size-1; i && arr[i] > 1 ; --i){
        arr[i] = 0;
        ++arr[i-1];
    }
}
int get_sum(int * signs, int * nums, int size){
    long res = nums[0];
    for (int i = 1; i < size ; ++i)
        switch ( signs[i] ){
            case 0 : res -= nums[i]; break;
            case 1 : res += nums[i]; break;
            default: std::cerr << "\nWTF???\n";
        }
    return res;
}
            
        
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int nums[24];
    int size;
    int sum;
    std::cin >> size >> sum;
    for (int i = 0; i < size; ++i)
        std::cin >> nums[i];
    while (!*signs){
        if (get_sum(signs, nums, size) == sum){
            for (int i = 0; i < size - 1; ++i){
                std::cout << nums[i];
                if ( signs[i+1] == 0) std::cout << '-';
                else std::cout << '+';
            }
            std::cout << nums[size - 1] << '=' << sum;
            exit(0);
        }
        bin_inc(signs, size);
    }
    std::cout << "No solution";
    return 0;
}
0
06.07.2011, 11:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2011, 11:41
Привет! Вот еще темы с ответами:

В данном натуральном числе переставить цифры таким образом, чтобы получилось наименьшее число записанное этими же цифрами - C++
2. В данном натуральном числе переставить цифры таким образом, чтобы получилось наименьшее число записанное этими же цифрами.

Можно ли добавить в последовательность из различных скобок цифры и знаки, чтобы получилось правильное арифметическое выражение? - C++
Здравствуйте. Прошу помощи в решение задачи. Дана конечная последовательность, состоящая из левых и правых скобок pазличных заданных...

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

Дан вещественный массив А (n). Отсортировать его таким образом, чтобы - C++
Задача 45. Дан вещественный массив А (n). Отсор¬тировать его таким образом, чтобы все положительные числа находились в начале, а...


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

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

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