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

РЕКУРСИВНЫЕ АЛГОРИТМЫ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Rikimaru
7 / 7 / 0
Регистрация: 25.09.2010
Сообщений: 31
27.10.2010, 10:12     РЕКУРСИВНЫЕ АЛГОРИТМЫ #1
Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом (функция M воз-вращает максимальный из своих параметров, а функция m — минималь-ный):
<выражение> ::= <цифра> | M(<параметры>) | m(<параметры>)
<параметры> ::= <выражение> | <выражение> , <параметры>
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rikimaru
7 / 7 / 0
Регистрация: 25.09.2010
Сообщений: 31
26.11.2010, 12:42  [ТС]     РЕКУРСИВНЫЕ АЛГОРИТМЫ #2
помогите разобраться с заданием, что требуется?
или хотябы пример (то что ввести с клавиатуры и какой будет результат)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2010, 15:55     РЕКУРСИВНЫЕ АЛГОРИТМЫ #3
Суть в том, чтобы посчитать значение примерно такого выражения:
M(1, 2, m(M(1, 2, 3), 4, 2), 2, m(1, 9)) = 2
Т.е. выражение с любой вложенностью функций m и M (по сути нечто вроде своеобразного калькулятора).
Вечером попробую написать, пока занят.

Добавлено через 3 часа 5 минут
Вот, что-то в этом роде.

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
#include <iostream>
#include <vector>
 
int expression();
int arguments(char);
 
int number();
 
int m(const std::vector< int > &);
int M(const std::vector< int > &);
 
void check(char);
 
int main()
{
    setlocale(LC_ALL, "Rus");
 
    int result;
 
    std::cout << "Введите выражение: ";
 
    result = expression();
 
    std::cout << "Результат вычисления: " << result << std::endl;
 
    return 0;
}
 
int expression()
{
    char c = std::cin.get();
 
    if (c >= '0' && c <= '9')
        return c - '0';
    else
    {
        switch (c)
        {
        case 'm':
            check('(');
 
            return arguments('m');
        case 'M':
            check('(');
 
            return arguments('M');
        default:
            std::cout << "Синтаксическая ошибка!" << std::endl;
            exit(-1);
        }
    }
}
 
int arguments(char f)
{
    std::vector< int > result;
    char c;
 
    while (true)
    {
        result.push_back(expression());
 
        if ((c = std::cin.get()) != ')')
        {
            std::cin.putback(c);
            check(',');
            check(' ');
        }
        else
            break;
    }
 
    switch (f)
    {
    case 'm':
        return m(result);
    case 'M':
        return M(result);
    default:
        std::cout << "Синтаксическая ошибка!" << std::endl;
        exit(-1);
    }
}
 
int m(const std::vector< int > &arr)
{
    unsigned int size = arr.size();
    int min = arr[0];
 
    for (unsigned int i = 1; i < size; i++)
        if (min > arr[i])
            min = arr[i];
 
    return min;
}
 
int M(const std::vector< int > &arr)
{
    unsigned int size = arr.size();
    int max = arr[0];
 
    for (unsigned int i = 1; i < size; i++)
        if (max < arr[i])
            max = arr[i];
 
    return max;
}
 
void check(char c)
{
    if (std::cin.get() != c)
    {
        std::cout << "Синтаксическая ошибка!" << std::endl;
        exit(-1);
    }
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,687
26.11.2010, 17:21     РЕКУРСИВНЫЕ АЛГОРИТМЫ #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
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
//////////////////////////////////////////////////////////////////////////////////////
//Вывести значение целочисленного выражения, заданного в виде строки S. 
//Выражение определяется следующим образом (функция M возвращает 
//максимальный из своих параметров, а функция m — минимальный):
//<выражение> ::= <цифра> | M(<параметры>) | m(<параметры>)
//<параметры> ::= <выражение> | <выражение> , <параметры> 
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string       T_expr;
typedef std::vector<int>  T_parameters;
//////////////////////////////////////////////////////////////////////////////////////
//Объявления функций:
bool  calculate_expr           (T_expr&  expr,  int&           res        );
bool  calculate_parameters     (T_expr&  expr,  T_parameters&  parameters );
bool  calculate_prefix         (T_expr&  expr,  const T_expr&  PREFIX     );
bool  calculate_CLOSE_BRACKET  (T_expr&  expr                             );
//////////////////////////////////////////////////////////////////////////////////////
void  remove_spaces(T_expr&  expr)
{    
    for(;;)
    {
        T_expr::size_type  pos = expr.find_first_of(" \t");
        if(pos == T_expr::npos) break;        
        expr.erase(pos, 1);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_dig(T_expr&  expr, int&  res)
{
    bool  res_bool = !expr.empty() 
                     && isdigit(expr[0]);
 
    if(res_bool)
    {
        res = expr[0] - '0';
        expr.erase(0, 1);
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_m_open_bracket(T_expr&  expr)
{
    return  calculate_prefix(expr, "m(");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_m(T_expr&  expr, int& res)
{ 
    T_parameters  parameters;
    bool          res_bool =    calculate_m_open_bracket(expr)
                             && calculate_parameters(expr, parameters)
                             && calculate_CLOSE_BRACKET(expr);
 
    if(res_bool)
    {
        res = *std::min_element(parameters.begin(), parameters.end());
    }      
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_CLOSE_BRACKET(T_expr&  expr)
{
    return  calculate_prefix(expr, ")");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_prefix(T_expr&  expr, const T_expr&  PREFIX)
{    
    T_expr::size_type  pos       = expr.find(PREFIX);
    bool               res_bool  = (pos == 0);
    if(res_bool)
    {        
        expr.erase(0, PREFIX.size());
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_COMMA(T_expr&  expr)
{
    return  calculate_prefix(expr, ",");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameters_tail(T_expr&  expr, T_parameters&  parameters)
{
    return  !calculate_COMMA(expr) 
            || calculate_parameters(expr, parameters);
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameter(T_expr&  expr, T_parameters&  parameters)
{
    int   res       = 0;
    bool  res_bool  = calculate_expr(expr, res);
    if(res_bool)
    {
        parameters.push_back(res);
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameters(T_expr&  expr, T_parameters&  parameters)
{        
    return    calculate_parameter(expr, parameters)
           && calculate_parameters_tail(expr, parameters);    
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_M_open_bracket(T_expr&  expr)
{
    return  calculate_prefix(expr, "M(");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_M(T_expr&  expr, int& res)
{    
    T_parameters  parameters;
    bool  res_bool =    calculate_M_open_bracket(expr)
                     && calculate_parameters(expr, parameters)
                     && calculate_CLOSE_BRACKET(expr);
 
    if(res_bool)
    {
        res = *std::max_element(parameters.begin(), parameters.end());
    }
 
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_expr(T_expr&  expr, int& res)
{    
    if(expr.empty()) return  false;
    
    switch(expr[0])
    {
    case 'M':
        return  calculate_M(expr, res);
 
    case 'm':
        return calculate_m(expr, res);
 
    default:
        if(isdigit(expr[0]))
        {
            return  calculate_dig(expr, res);
        }
        return false;
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_expr_start(T_expr&  expr, int&  res)
{
    remove_spaces(expr);    
    return    calculate_expr(expr, res)
           && expr.empty();    
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    //test
    srand(static_cast<unsigned>(time(0)));
    
    T_expr  expr = "0";
    T_expr mM;
    for(int i = 0; i < 3; ++i)
    {
        mM.clear();
        mM += (rand() % 2 ? "m" : "M");        
        mM += (rand() % 10 ? " " : "\t");
        mM += '(';
        mM += (rand() % 10 ? " " : "\t");
        mM += rand() % 10 + '0';
        mM += (rand() % 10 ? " " : "\t");
        mM += ",";
        mM += (rand() % 10 ? " " : "\t");
        mM += rand() % 10 + '0';
 
        mM += (rand() % 10 ? " " : "\t");
        mM += ")";
        mM += (rand() % 10 ? " " : "\t");
 
        T_expr::size_type  pos = expr.find_first_of("0123456789");
 
        if(pos == T_expr.npos) break;
 
        rand() % 10 ? expr.replace(pos, 1, mM) : expr.replace(pos, 1, "$");
    }
 
    std::cout << expr
              << std::endl;    
 
    int  res = 0;
    if(calculate_expr_start(expr, res))
    {
        std::cout << "Result: "
                  << res;                       
    }
    else
    {
        std::cout << "Expression is not correct.";
    }
    std::cout << std::endl
              << std::endl
              << std::endl;   
 
    /*    
    for(;;)
    {
        std::cout << "Input expression: ";
        T_expr  expr;
        std::getline(std::cin, expr);        
        int     res;                
 
        if(expr.empty()) break;
 
        if(calculate_expr_start(expr, res))
        {
            std::cout << "Result: "
                      << res;                       
        }
        else
        {
            std::cout << "Expression is not correct.";
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl; 
    } 
    */
}
Rikimaru
7 / 7 / 0
Регистрация: 25.09.2010
Сообщений: 31
26.11.2010, 22:28  [ТС]     РЕКУРСИВНЫЕ АЛГОРИТМЫ #5
мой вариант.. немного упрощенный для 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
#include <stdio.h>
#include <conio.h>
 
 
int Formula ()
{
    int f=0, x, y;
    char c, op, t, p, e, m, M;
    bool proverka=true;
    c = getchar ();
 
    {   
        if ((c >= '0') && (c <= '9')) 
        {
            return (c - '0');
        }
        else
        {
            e = getchar ();
            if (e=='(')
            {
                x = Formula (); 
                op = getchar ();
                y = Formula ();
                t = getchar();
                
                if (c=='M')
                {
                    if (x>=y) f=x;
                    else f=y;
                }
                
                else if (c=='m')
                {
                    if (x<=y) f=x;
                    else f=y;
                }
                if ((t!=')') || (op!=',')) proverka=false;
                if (proverka==false) printf("error");           
                return f;   
            }
        }
    }
    return 0;
}
 
int main ()
{
    printf ("Vvedite vyrazhenie:\n");
    int t=Formula ();
    if (t!=0) printf ("%d", t);
    else printf("error");
    getch();
    return 0;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
27.11.2010, 12:11     РЕКУРСИВНЫЕ АЛГОРИТМЫ #6
Rikimaru, я в код не вникал, но при вводе M(1, 2) выдаёт 1, а при вводе m(1, 2) выдаёт error, как и при вводе, скажем, M(m(1, 2), m(3, 4))
Rikimaru
7 / 7 / 0
Регистрация: 25.09.2010
Сообщений: 31
27.11.2010, 13:09  [ТС]     РЕКУРСИВНЫЕ АЛГОРИТМЫ #7
Цитата Сообщение от silent_1991 Посмотреть сообщение
Rikimaru, я в код не вникал, но при вводе M(1, 2) выдаёт 1, а при вводе m(1, 2) выдаёт error, как и при вводе, скажем, M(m(1, 2), m(3, 4))
без пробела после запятой все работает
M(m(1,2),m(3,4)) попробуй
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
27.11.2010, 13:11     РЕКУРСИВНЫЕ АЛГОРИТМЫ #8
Rikimaru, да, об этом не подумал.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2010, 17:41     РЕКУРСИВНЫЕ АЛГОРИТМЫ
Еще ссылки по теме:

C++ рекурсивные алгоритмы
C++ Итерационные и рекурсивные алгоритмы
C++ Рекурсивные алгоритмы, вычисление a^n

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,687
27.11.2010, 17:41     РЕКУРСИВНЫЕ АЛГОРИТМЫ #9
Удалось обойтись без оператора switch:
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
//////////////////////////////////////////////////////////////////////////////////////
//Вывести значение целочисленного выражения, заданного в виде строки S. 
//Выражение определяется следующим образом (функция M возвращает 
//максимальный из своих параметров, а функция m — минимальный):
//<выражение> ::= <цифра> | M(<параметры>) | m(<параметры>)
//<параметры> ::= <выражение> | <выражение> , <параметры> 
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string       T_expr;
typedef std::vector<int>  T_parameters;
//////////////////////////////////////////////////////////////////////////////////////
//Объявления функций:
bool  calculate_expr           (T_expr&  expr,  int&           res        );
bool  calculate_parameters     (T_expr&  expr,  T_parameters&  parameters );
bool  calculate_prefix         (T_expr&  expr,  const T_expr&  PREFIX     );
bool  calculate_CLOSE_BRACKET  (T_expr&  expr                             );
//////////////////////////////////////////////////////////////////////////////////////
void  remove_spaces(T_expr&  expr)
{    
    for(;;)
    {
        T_expr::size_type  pos = expr.find_first_of(" \t");
        if(pos == T_expr::npos) break;        
        expr.erase(pos, 1);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_dig(T_expr&  expr, int&  res)
{
    bool  res_bool =    !expr.empty() 
                     && isdigit(expr[0]);
 
    if(res_bool)
    {
        res = expr[0] - '0';
        expr.erase(0, 1);
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_m_open_bracket(T_expr&  expr)
{
    return  calculate_prefix(expr, "m(");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_m(T_expr&  expr, int& res)
{ 
    T_parameters  parameters;
    bool          res_bool =    calculate_m_open_bracket  (expr)
                             && calculate_parameters      (expr, parameters)
                             && calculate_CLOSE_BRACKET   (expr);
 
    if(res_bool)
    {
        res = *std::min_element(parameters.begin(), parameters.end());
    }      
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_CLOSE_BRACKET(T_expr&  expr)
{
    return  calculate_prefix(expr, ")");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_prefix(T_expr&  expr, const T_expr&  PREFIX)
{    
    T_expr::size_type  pos       = expr.find(PREFIX);
    bool               res_bool  = (pos == 0);
    if(res_bool)
    {        
        expr.erase(0, PREFIX.size());
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_COMMA(T_expr&  expr)
{
    return  calculate_prefix(expr, ",");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameters_tail(T_expr&  expr, T_parameters&  parameters)
{
    return    !calculate_COMMA(expr) 
           || calculate_parameters(expr, parameters);
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameter(T_expr&  expr, T_parameters&  parameters)
{
    int   res       = 0;
    bool  res_bool  = calculate_expr(expr, res);
    if(res_bool)
    {
        parameters.push_back(res);
    }
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_parameters(T_expr&  expr, T_parameters&  parameters)
{        
    return    calculate_parameter        (expr, parameters)
           && calculate_parameters_tail  (expr, parameters);    
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_M_open_bracket(T_expr&  expr)
{
    return  calculate_prefix(expr, "M(");
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_M(T_expr&  expr, int& res)
{    
    T_parameters  parameters;
    bool          res_bool =    calculate_M_open_bracket  (expr)
                             && calculate_parameters      (expr, parameters)
                             && calculate_CLOSE_BRACKET   (expr);
 
    if(res_bool)
    {
        res = *std::max_element(parameters.begin(), parameters.end());
    }
 
    return  res_bool;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_expr(T_expr&  expr, int& res)
{
    return    calculate_M    (expr, res)
           || calculate_m    (expr, res)
           || calculate_dig  (expr, res);
}
//////////////////////////////////////////////////////////////////////////////////////
bool  calculate_expr_start(T_expr&  expr, int&  res)
{
    remove_spaces(expr);    
    return    calculate_expr(expr, res)
           && expr.empty();    
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    //test
    srand(static_cast<unsigned>(time(0)));
    
    T_expr  expr = "0";
    T_expr  mM;
    for(int i = 0; i < 3; ++i)
    {
        mM.clear();
        mM += (rand() % 2 ? "m" : "M");        
        mM += (rand() % 10 ? " " : "\t");
        mM += '(';
        mM += (rand() % 10 ? " " : "\t");
        mM += rand() % 10 + '0';
        mM += (rand() % 10 ? " " : "\t");
        mM += ",";
        mM += (rand() % 10 ? " " : "\t");
        mM += rand() % 10 + '0';
 
        mM += (rand() % 10 ? " " : "\t");
        mM += ")";
        mM += (rand() % 10 ? " " : "\t");
 
        T_expr::size_type  pos = expr.find_first_of("0123456789");
 
        if(pos == T_expr.npos) break;
 
        rand() % 10 ? expr.replace(pos, 1, mM) : expr.replace(pos, 1, "$");
    }
 
    std::cout << expr
              << std::endl;    
 
    int  res = 0;
    if(calculate_expr_start(expr, res))
    {
        std::cout << "Result: "
                  << res;                       
    }
    else
    {
        std::cout << "Expression is not correct.";
    }
    std::cout << std::endl
              << std::endl
              << std::endl;   
 
    /*    
    for(;;)
    {
        std::cout << "Input expression: ";
        T_expr  expr;
        std::getline(std::cin, expr);        
        int     res;                
 
        if(expr.empty()) break;
 
        if(calculate_expr_start(expr, res))
        {
            std::cout << "Result: "
                      << res;                       
        }
        else
        {
            std::cout << "Expression is not correct.";
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl; 
    } 
    */
}
Yandex
Объявления
27.11.2010, 17:41     РЕКУРСИВНЫЕ АЛГОРИТМЫ
Ответ Создать тему
Опции темы

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