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

Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом - C++

Восстановить пароль Регистрация
 
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
01.10.2016, 14:28     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #1
Имеются цифры 1, 2, 3, 4, 5, 6, 7, 8, 9.
Необходимо расставить между ними любое количество знаков "плюс" или "минус" так, чтобы получить выражение, равное числу введенного пользователем.

Например: Ввожу число 100. Результат: 123+4-5+67-89=100. Число 123 вышло из склеивания соседних цифр 1, 2 и 3. Также 67 и 89.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2016, 14:28     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом
Посмотрите здесь:

C++ Расставить знаки арифметических операций так, чтобы сошелся результат
Нужно расставить между числами знаки + или - таким образом, чтобы получилось выражение, значение которого равно s и вывести его на экран C++
C++ Можно ли добавить в последовательность из различных скобок цифры и знаки, чтобы получилось правильное арифметическое выражение?
C++ Написать функции сложения, умножения и вычитания квадратных матриц, и вычислить с их помощью выражение
В выражении расставить знаки так, чтобы результат вычислений был равен 35 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
01.10.2016, 14:59     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #2
Например: Ввожу число 100. Результат: 123+4-5+67-89=100. Число 123 вышло из склеивания соседних цифр 1, 2 и 3. Также 67 и 89.
Дело в том, что предложенная вами задача - комбинаторная: т.е. число 100 может быть получено суммой множества других вариантов слагаемых а не только: 123+4-5+67-89=100. Вопрос: скажите вам нужно найти все варианты, я так понимаю ??
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
01.10.2016, 15:35  [ТС]     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #3
Invader0x7F, мне нужно любой вариант используя эти цифры и склеивания)
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
01.10.2016, 15:55     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #4
Сделаю и выложу.
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
01.10.2016, 15:56  [ТС]     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #5
Спасибоооо)))
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
01.10.2016, 18:16     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #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
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
//Имеются цифры 1, 2, 3, 4, 5, 6, 7, 8, 9.
//Необходимо расставить между ними любое количество знаков
//"плюс" или "минус" так, чтобы получить выражение, равное
//числу введенного пользователем.
 
//Например: Ввожу число 100. Результат: 123+4-5+67-89=100.
//Число 123 вышло из склеивания соседних цифр 1, 2 и 3. Также 67 и 89.
///////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                 T_expr;
typedef std::vector     < int   >   T_ternary_number;
///////////////////////////////////////////////////////////////////////////////
T_expr  make_expr
    (
        T_ternary_number    const   &   ternary_number,
        T_expr              const   &   digits
    )
{
    T_expr  res;
 
    for( size_t  i{}; i < digits.size(); ++i )
    {
        if(i)
        {
            switch  (
                        ternary_number[ i - 1 ]
                    )
            {
            case    1   :   res     +=  '+';    break;
            case    2   :   res     +=  '-';    break;
            default     :
                ;
            }//switch
        }//if
 
        res     +=  digits[i];
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     calc_expr( T_expr   expr )
{
    size_t  pos{};
    int     res     =   std::stoi   (
                                        expr,
                                        &pos
                                    );
 
    expr    =   expr.substr( pos );
 
    while   (
                !expr.empty()
            )
    {
        char    op  =   expr.front();
        expr.erase(0, 1);
        int     term    =   std::stoi   (
                                            expr,
                                            &pos
                                        );
 
        expr    =   expr.substr( pos );
        op  ==  '+'
            ?   res     +=  term
            :   res     -=  term;
    }//while
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_inc_ternary_number( T_ternary_number     &   ternary_number )
{
    for (
            int
            i   =    ternary_number.size()  -   1;
            i   >=  0;
            --i
        )
    {
        if  (
                ternary_number[i]   <   3
            )
        {
            ++ternary_number[i];
            return  true;
        }
        else
        {
            ternary_number[i]   =   0;
        }
    }//for
 
    return  false;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_set_expr
    (
        int         n,
        T_expr  &   expr
    )
{
    static  const       T_expr  DIGITS  { "123456789"   };
 
    T_ternary_number    ternary_number  (
                                            DIGITS.size() - 1
                                        );
 
    do
    {
        expr    =   make_expr   (
                                    ternary_number,
                                    DIGITS
                                );
 
        if  (
                    calc_expr( expr )
                ==  n
            )
        {
            return  true;
        }
    }
    while   (
                successfully_inc_ternary_number( ternary_number )
            );
 
    return  false;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        int     n{};
        std::cout   <<  "n = ";
        std::cin    >>  n;
 
        T_expr  expr;
 
        std::cout   <<  (
                            successfully_set_expr( n,   expr )
                                ?   expr
                                :   "no solution"
                        )
 
                    <<  std::endl
                    <<  std::endl;
    }//for
}
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
01.10.2016, 23:33  [ТС]     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #7
Большое спасибо! Но в какой среде ты разрабатывал? У меня ошибки:
Миниатюры
Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом  
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
01.10.2016, 23:49     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #8
Цитата Сообщение от MDefs Посмотреть сообщение
У меня ошибки
С++11 надо подключить.
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
02.10.2016, 00:00  [ТС]     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #9
Всем Всем СПАСИБО!!!) Вопрос. Что посоветуете начинающему. Как выучить это программирования?
GbaLog-
Не Эксперт C++
1477 / 622 / 176
Регистрация: 24.08.2014
Сообщений: 2,531
Записей в блоге: 1
Завершенные тесты: 2
02.10.2016, 00:02     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #10
Цитата Сообщение от MDefs Посмотреть сообщение
Как выучить это программирования?
Читайте книжки.
Литература C++
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
02.10.2016, 00:04     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #11
Цитата Сообщение от MDefs Посмотреть сообщение
Что посоветуете начинающему. Как выучить это программирования?
Читать толковые книжки и программировать непрерывно!

Добавлено через 1 минуту
Цитата Сообщение от GbaLog- Посмотреть сообщение
Читайте книжки.
*************
GbaLog-
Не Эксперт C++
1477 / 622 / 176
Регистрация: 24.08.2014
Сообщений: 2,531
Записей в блоге: 1
Завершенные тесты: 2
02.10.2016, 00:06     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Дайте совет, куда двигаться дальше
Цитата Сообщение от Mr.X Посмотреть сообщение
1) STL (Джосаттис)
2) Дискретная математика (Новиков)
3) Алгоритмы (Седжвик, Кормен)
4) ООП (осваивать на практике, почитывая Страуструпа, Липпмана и Прату)
5) Паттерны проектирования (Банда четырех)
6) Шаблоны (Вандевурд, Александреску)
7) Параллельное программирование (Уильямс)
8) Книги по оформлению кода (Чистый код, Совершенный код, Ален Голуб)
9) Графика - Qt
10) Как только все это изучите - приступайте к Бусту
11) Скотт Майерс и ему подобные - перечитывать постоянно.
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
02.10.2016, 04:58     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #13
Вот написал программу которая находит все комбинации чисел в сумме дающие число x = 100 заданной длины count = 5.
Извините пожалуйста за опоздание, но вчера имел много работы и не мог быстро выполнить ваше задание.
В отличие от других программ данная программа находит все комбинации в том числе и заданную вами.
К данному посту прилагаю exe-шник и скриншот для демонстрации (см. аттачмент ниже).

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
#include <map>
#include <ctime>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
 
using std::multimap;
using std::vector;
 
using namespace std;
 
const int N = 9;
 
int main()
{
    std::vector<int> magic_values;
    std::vector<int> A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    int x = 0, count = 0;
    std::cout << "x = "; cin >> x;
    std::cout << "count = "; cin >> count;
 
    int cnt = 0, n_val = x;
    for (; n_val >= 1; n_val /= 10)
        cnt++;
 
    for (int t = 0; t < N; t += cnt)
        for (int pos = t; pos < t + cnt; pos++)
            for (int n_count = (t + cnt) - pos; n_count > 0; n_count--)
            {
                int n_digit = n_count - 1; n_val = 0;
                for (int t1 = pos; t1 < pos + n_count; t1++, n_digit--)
                    n_val += A[t1] * int(pow(10.0, n_digit));
 
                magic_values.push_back(n_val);
            }
 
    for (int r = cnt; r < N; r += cnt)
        magic_values.push_back(A[r] + A[r - 1] * 10);
 
    std::sort(magic_values.begin(), magic_values.end(), std::greater<int>());
 
    std::multimap<vector<int>,int> mvsets;
 
    std::vector<int> sampl_v;
    sampl_v.push_back(magic_values[2]);
 
    mvsets.insert(std::make_pair(sampl_v, magic_values[2]));
 
    for (auto it = mvsets.begin(); it != mvsets.end(); it++)
    {
        std::vector<int> magic_seq = it->first;
        int n_val = magic_seq[magic_seq.size() - 1];
 
        if (it->second != x && magic_seq.size() != count)
        {
            std::size_t i = 0; bool found = false;
            while (i < magic_values.size() && !found)
                found = magic_values[i++] == std::abs(n_val) ? 1 : 0;
 
            for (std::size_t t = i; t < magic_values.size(); t++)
            {
                std::vector<int> new_seq = magic_seq;
                new_seq.push_back(it->second > x ? -magic_values[t] : magic_values[t]);
 
                int sum = 0;
                for (std::size_t v = 0; v < new_seq.size(); v++)
                    sum += new_seq[v];
 
                mvsets.insert(std::make_pair(new_seq, sum));
            }
        }
 
        else
        {
            for (auto&& a : it->first)
                std::cout << a << " ";
            std::cout << endl;
        }
    }
 
    std::cin.get();
    std::cin.get();
 
    return 0;
}
Миниатюры
Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом  
Вложения
Тип файла: zip magic_nums.zip (48.0 Кб, 1 просмотров)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2016, 21:01     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
24.10.2016, 21:01  [ТС]     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом #14
Mr.X, Здравствуй!) Не мог бы ты добавить комментарии к своему коду пожалуйста.
Yandex
Объявления
24.10.2016, 21:01     Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом
Ответ Создать тему
Опции темы

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