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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 15:03     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #1
Составить программу, которая бы нашла все варианты размещения знаков арифметических операций +,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.06.2014, 15:03     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100
Посмотрите здесь:

C++ Классы для арифметических операций с большими числами (целые числа более 10 знаков)
C++ Найти все возможные варианты написания слова в верхнем и нижнем регистрах букв.
Вставить между цифрами 1, 2,..., 8, 9 в данном порядке, знак одной из 4-х арифметических операций так, чтобы результат восьми послед-х операций =100 C++
C++ Найти все варианты перебора циклов
В строке, состоящей из слов и знаков препинания найти все слова-палиндромы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sonance
6 / 6 / 3
Регистрация: 15.02.2013
Сообщений: 55
27.06.2014, 16:29     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
На каждой позиции возможны 3 варианта действий, при условии что приоритет выполнения действий не важен и все действия выполняются слева направо:
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
#include <iostream>
 
 
int mass[9]={1,2,3,4,5,6,7,8,9}, Sf, Ss;
 
 
int Do(int znak, int a, int b, int &S){
    if(znak == 0){
        S=a-b;
    }
    if(znak == 1){
        S=a+b;
    }
    if(znak == 2){
        S=a*b;
    }
    return 0;
}
char Znak(int i){
    char Znak;
    if(i == 0){
        Znak='-';
    }
    if(i == 1){
        Znak='+';
    }
    if(i == 2){
        Znak='*';
    }
    return Znak;
}
void main(){
    int count(0);
    std::cout<<"Varianti podstanovki znakov pri kotorom virazhenie ravno 100:"<<"\n";
    for(int a(0); a<3; a++){
        for(int b(0); b<3; b++){
            for(int c(0); c<3; c++){
                for(int d(0); d<3; d++){
                    for(int e(0); e<3; e++){
                        for(int f(0); f<3; f++){
                            for(int g(0); g<3; g++){
                                for(int h(0); h<3; h++){
                                    Do(e, mass[0], mass[1], Sf);
                                    Ss=0;
                                    Do(b, Sf, mass[2], Ss);
                                    Sf=0;
                                    Do(c, Ss, mass[3], Sf);
                                    Ss=0;
                                    Do(d, Sf, mass[4], Ss);
                                    Sf=0;
                                    Do(e, Ss, mass[5], Sf);
                                    Ss=0;
                                    Do(f, Sf, mass[6], Ss);
                                    Sf=0;
                                    Do(g, Ss, mass[7], Sf);
                                    Ss=0;
                                    Do(h, Sf, mass[8], Ss);
                                    Sf=0;
                                    if(Ss == 100){
 
                                        std::cout<<"1"<<Znak(a)<<"2"<<Znak(b)<<"3"<<Znak(c)<<"4"<<Znak(d)<<"5"<<Znak(e)<<"6"<<Znak(f)<<"7"<<Znak(g)<<"8"<<Znak(h)<<"9"<<" = 100"<<"\n";
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
std::cout<<"Kol-vo variantov podstanovki znakov pri kotorom virazhenie ravno 100"<<"\t"<<count<<"\n";
system("pause");
 
}
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 16:47  [ТС]     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #3
Спасибо огромное,а можно описание методов реализации данной программы,в частности к вот этой части:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
      Do(e, mass[0], mass[1], Sf);
                                    Ss=0;
                                    Do(b, Sf, mass[2], Ss);
                                    Sf=0;
                                    Do(c, Ss, mass[3], Sf);
                                    Ss=0;
                                    Do(d, Sf, mass[4], Ss);
                                    Sf=0;
                                    Do(e, Ss, mass[5], Sf);
                                    Ss=0;
                                    Do(f, Sf, mass[6], Ss);
                                    Sf=0;
                                    Do(g, Ss, mass[7], Sf);
                                    Ss=0;
                                    Do(h, Sf, mass[8], Ss);
                                    Sf=0;
                                    if(Ss == 100)
FraidZZ
Модератор
 Аватар для FraidZZ
3878 / 1504 / 227
Регистрация: 06.01.2013
Сообщений: 4,029
Завершенные тесты: 1
27.06.2014, 17:04     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #4
Рекурсией:
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
#include <iostream>
#include <vector>
 
using namespace std;
 
int eval(vector<int> arr){
    int total = 0;
    vector<int> p = arr, m = arr, mp = arr;
    if (arr.size() > 2){
        p[1] = p[0] + p[1]; p.erase(p.begin()); total += eval(p);
        m[1] = m[0] - m[1]; m.erase(m.begin()); total += eval(m);
        mp[1]=mp[0] *mp[1];mp.erase(mp.begin()); total+=eval(mp);
    } else {
        if ((arr[0] - arr[1]) == 100) total++;
        if ((arr[0] + arr[1]) == 100) total++;
        if ((arr[0] * arr[1]) == 100) total++;
    }
    return total;
}
 
int main(){
    vector<int> arr; for (int i = 1; i < 10; i++) arr.push_back(i);
    cout<<eval(arr);
}
Добавлено через 16 секунд
Но находит только количество.
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 17:05  [ТС]     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #5
спасибо,разобрался!
FraidZZ
Модератор
 Аватар для FraidZZ
3878 / 1504 / 227
Регистрация: 06.01.2013
Сообщений: 4,029
Завершенные тесты: 1
27.06.2014, 17:15     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #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
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
string str(int n);
 
int eval(vector<int> arr, string expr){
    int total = 0;
    vector<int> p = arr, m = arr, mp = arr;
    int sp = p[1], sm = m[1], smp = mp[1];
    if (arr.size() > 2){
        p[1] = p[0] + p[1]; p.erase(p.begin()); total += eval(p, expr + string("+") + str('0' + sp));
        m[1] = m[0] - m[1]; m.erase(m.begin()); total += eval(m, expr + string("-") + str('0' + sm));
        mp[1]=mp[0] *mp[1];mp.erase(mp.begin()); total+=eval(mp, expr + string("*") + str('0' + smp));
    } else {
        if ((arr[0] - arr[1]) == 100) {total++; cout<<expr<<"-"<<arr[1]<<endl;}
        if ((arr[0] + arr[1]) == 100) {total++; cout<<expr<<"+"<<arr[1]<<endl;}
        if ((arr[0] * arr[1]) == 100) {total++; cout<<expr<<"*"<<arr[1]<<endl;}
    }
    return total;
}
 
string str(int n){
    string a = "0";
    a[0] = (char) n;
    return a;
}
 
int main(){
    string expr = "1";
    vector<int> arr; for (int i = 1; i < 10; i++) arr.push_back(i);
    eval(arr, expr);
}
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 17:41  [ТС]     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #7
Sonance,приоритет выполнения действий не важен и все действия выполняются слева направо,а в данной программе действия выполняются по приоритету.

Добавлено через 1 минуту
FraidZZ, я только учусь и данного не изучал,мне ближе первый вариант,но там приоритет действий есть.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
27.06.2014, 17:50     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #8
ответ 7?

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
int ans = 0;
 
void rec(int val, int cur)
{
    if(val == 9)
    {
        if(cur == 100)
        {
            ans++;
        }
 
        return;
    }
 
 
    int ncur = cur + (val + 1);
    rec(val + 1, ncur);
    ncur = cur - (val + 1);
    rec(val + 1, ncur);
    ncur = cur * (val + 1);
    rec(val + 1, ncur);
}
 
int main()
{
    rec(1, 1);
    cout << ans << endl;
    return 0;
}
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 18:10  [ТС]     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #9
SlavaSSU, да, 7

Добавлено через 5 минут
FraidZZ, а можно описание методов реализации данной программы?
FraidZZ
Модератор
 Аватар для FraidZZ
3878 / 1504 / 227
Регистрация: 06.01.2013
Сообщений: 4,029
Завершенные тесты: 1
27.06.2014, 18:28     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #10
rayJIB, да все просто) Создается вектор (считай это массивом, просто вектор удобнее и передается из функции в функцию). Так же создается строка, в которую потом записывается выражение. И затем просто функция до тех пор пока у нее больше двух чисел в векторе рекурсивно подбирает знаки. Если же ответ сошелся, она его выводит)
rayJIB
0 / 0 / 0
Регистрация: 27.06.2014
Сообщений: 9
27.06.2014, 18:59  [ТС]     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #11
FraidZZ, а можно проделать подобное используя массив?
FraidZZ
Модератор
 Аватар для FraidZZ
3878 / 1504 / 227
Регистрация: 06.01.2013
Сообщений: 4,029
Завершенные тесты: 1
27.06.2014, 19:27     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #12
rayJIB, придется пилить очень много костылей.
Sonance
6 / 6 / 3
Регистрация: 15.02.2013
Сообщений: 55
27.06.2014, 21:27     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #13
Где вы тут приоритет увидели, все считается по порядку с лева направо, функция do() принимает аргументы 1- действие, 2-3-числа с которыми нужно проделать действие, 4- куда записать результат
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Do(a, mass[0], mass[1], Sf);//тут опечатка была 1 аргумент "a" а не "e"
Ss=0;
Do(b, Sf, mass[2], Ss);
Sf=0;
Do(c, Ss, mass[3], Sf);
Ss=0;
Do(d, Sf, mass[4], Ss);
Sf=0;
Do(e, Ss, mass[5], Sf);
Ss=0;
Do(f, Sf, mass[6], Ss);
Sf=0;
Do(g, Ss, mass[7], Sf);
Ss=0;
Do(h, Sf, mass[8], Ss);
Sf=0;
if(Ss == 100)
Из-за опечатки выдавало 9 ответов что не верно, вот так все работает, надеюсь теперь все понятно, если нет пишите завтра время будет опишу каждую строку.
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
29.06.2014, 11:18     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #14
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
/////////////////////////////////////////////////////////////////////////////////////////
//Составить программу, которая бы нашла все варианты размещения знаков арифметических операций 
//+,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения 
//равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.
/////////////////////////////////////////////////////////////////////////////////////////
#include <deque>
#include <iostream>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef std::deque<int>     T_operands;
/////////////////////////////////////////////////////////////////////////////////////////
T_str   num_to_str( int  num )
{
    std::ostringstream  sout;
    sout    <<  num;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_variants_for_add_subtr_mult
    (
        T_operands      operands,
        int             result_target,
        int             result_cur      =   0,
        T_str           str_result      =   T_str()
    )
{
    if  (
            operands.empty()
        )
    {
        if( result_cur == result_target )
        {
            str_result  +=  " = ";
            str_result  +=  num_to_str( result_target );
 
            std::cout   <<  str_result
                        <<  std::endl;
        }
        return;
    }//if
 
    int     operand     =   operands.front();
    operands.pop_front();
 
    if  (
            str_result.empty()
        )
    {
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                operand,
                num_to_str( operand )
            );
    }
    else
    {
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur + operand,
                str_result + " + " + num_to_str( operand )
            );
 
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur - operand,
                str_result + " - " + num_to_str( operand )
            );
 
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur * operand,
                str_result + " * " + num_to_str( operand )
            );
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    int         operands_arr[]  =   {1, 2, 3, 4, 5, 6, 7, 8, 9};
 
    T_operands  operands
        (
            operands_arr,
            operands_arr + sizeof( operands_arr ) / sizeof( operands_arr[0] )
        );
 
    int     result_target   =   100;
 
    print_variants_for_add_subtr_mult
        (
            operands,
            result_target
        );
 
    system( "pause" );
}
Добавлено через 6 часов 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
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/////////////////////////////////////////////////////////////////////////////////////////
//Составить программу, которая бы нашла все варианты размещения знаков арифметических операций 
//+,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения 
//равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <deque>
#include <iostream>
#include <iterator>
#include <set>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string             T_str;
typedef std::set    < T_str >   T_strings;
typedef std::deque  < int   >   T_operands;
/////////////////////////////////////////////////////////////////////////////////////////
T_str   num_to_str( int  num )
{
    std::ostringstream  sout;
    sout    <<  num;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
void    set_variants_strings_for_add_subtr_mult
    (
        T_operands      operands,
        int             result_target,
        T_strings   &   variants_strings,
        int             result_cur      =   0,
        T_str           str_result      =   T_str()
    )
{
    if  (
            operands.empty()
        )
    {
        if( result_cur == result_target )
        {
            str_result  +=  " = ";
            str_result  +=  num_to_str( result_target );
 
            variants_strings.insert( str_result );
        }
    }
    else
    {
        int     operand     =   operands.front();
        operands.pop_front();
 
        if  (
                str_result.empty()
            )
        {
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    operand,
                    num_to_str( operand )
                );
        }
        else
        {
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur + operand,
                    str_result + " + " + num_to_str( operand )
                );
 
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur - operand,
                    str_result + " - " + num_to_str( operand )
                );
 
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur * operand,
                    str_result + " * " + num_to_str( operand )
                );
        }//else
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val
    (
        T_str   const   &   prompt,
        int             &   val
    )
{
    std::cout   <<  prompt;
    std::cin    >>  val;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val_not_less_than
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 left_bound
    )
{
    do
    {
        print_prompt_and_input_val
            (
                prompt,
                val
            );
    }
    while( val < left_bound );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        int     operands_count  =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Введите количество операндов: ",
                operands_count,
                1
            );
 
        std::cout   <<  "Введите "
                    <<  operands_count
                    <<  " операндов:"
                    <<  std::endl;
 
        T_operands  operands;
 
        for( int  i = 0; i < operands_count; ++i )
 
        {
            int     operand_cur     =   0;
 
            print_prompt_and_input_val
                (
                    "#" + num_to_str( i + 1 ) + "\t: ",
                    operand_cur
                );
 
            operands.push_back( operand_cur );
        }
 
        int     result_target   =   0;
 
        print_prompt_and_input_val
            (
                "\nВведите желаемый результат: ",
                result_target
            );
 
        std::cout   <<  std::endl;
        T_strings   variants_strings;
 
        set_variants_strings_for_add_subtr_mult
            (
                operands,
                result_target,
                variants_strings
            );
 
        std::copy
            (
                variants_strings.begin          (),
                variants_strings.end            (),
                std::ostream_iterator<T_str>    ( std::cout, "\n" )
            );
 
        int     variants_total  =   variants_strings.size();
 
        std::cout   <<  (
                            variants_total == 0
                                ?   "Нет решений."
                                :   "Всего " + num_to_str( variants_total ) + " решений."
                        )
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
Sonance
6 / 6 / 3
Регистрация: 15.02.2013
Сообщений: 55
29.06.2014, 11:40     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #15
Mr.X, а можно комментарии к первому коду, что то я не могу разобраться, как он работает
Объясните пожалуйста функцию print_variants_for_add_subtr_mult()
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
29.06.2014, 13:42     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #16
Цитата Сообщение от Sonance Посмотреть сообщение
Объясните пожалуйста функцию print_variants_for_add_subtr_mult()
Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый.
Sonance
6 / 6 / 3
Регистрация: 15.02.2013
Сообщений: 55
29.06.2014, 15:56     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #17
Цитата Сообщение от Mr.X Посмотреть сообщение
Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый.
Спасибо, посмотрел что такое рекурсия, нашел факториал с её помощью. В случае с факториалом все просто, можно сказать интуитивно понятно, но в данном случае все как то путается, объясните пожалуйста ход мыслей при разработке программы для данной задачи.
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
29.06.2014, 17:41     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #18
Цитата Сообщение от Sonance Посмотреть сообщение
объясните пожалуйста ход мыслей при разработке программы для данной задачи
Каждая функция вызывает три (по числу возможных различных операторов в каждой позиции), т.е. получаем троичное дерево вызовов высотой 8 (по числу операторов в выражении). Каждая ветвь дерева соответствует одному из вариантов расстановки операторов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2014, 18:34     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100
Еще ссылки по теме:

Рассчитать все возможные варианты для 3 знаков C++
C++ Найти все варианты возможной замены проводов с заданной точностью подбора
Расстановка знаков операций C++

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

Или воспользуйтесь поиском по форуму:
Sonance
6 / 6 / 3
Регистрация: 15.02.2013
Сообщений: 55
29.06.2014, 18:34     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 #19
Верно я понял?
Контейнер deque - это стек;
при каждом вызове функции - из стека достается 1 элемент, размер стека уменьшается на 1, и функция вызывает сама себя 3 раза(для каждой операции), уже с меньшим стеком и так пока стек не опустеет

И еще вопрос: есть ли какие-то преимущества у этого способа, перед алгоритмами не использующими рекурсию. В консоли алгоритм с рекурсией работает заметно медленнее, чем без неё.

P.s. Возможно глупые вопросы задаю, но хотелось бы разобраться. Просто я рекурсивный алгоритм впервые вижу. Интересный способ.
Yandex
Объявления
29.06.2014, 18:34     Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100
Ответ Создать тему
Опции темы

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