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

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

Войти
Регистрация
Восстановить пароль
 
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 14
#1

Разобраться с алгоритмом задачи - C++

01.11.2016, 13:51. Просмотров 156. Ответов 5
Метки нет (Все метки)

Помогите разобраться с алгоритмом, как работает программа. Я понимаю что здесь 38 перестановок. Но мне нужно знать как именно работает эта программа, точный алгоритм.

Вот задача:

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

Вот код:
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
#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
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2016, 13:51     Разобраться с алгоритмом задачи
Посмотрите здесь:

C++ Помогите с алгоритмом
Помогите разобраться с сутью задачи. C++
помогите с алгоритмом! C++
Помогите с алгоритмом C++
C++ Помогите с алгоритмом
C++ Не могу разобраться в условии задачи.
Помощь с алгоритмом C++
Проблемы с алгоритмом решения задачи C++
C++ Не могу разобраться с алгоритмом
Кодирование алгоритмом Хаффмана C++
C++ Не могу разобраться с алгоритмом деления романа на отдельные тома

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 55
01.11.2016, 15:32     Разобраться с алгоритмом задачи #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
перебор всех вариантов.
У тебя 9 чисел (1*2*3*4*5*6*7*8*9) и 8 позиций куда можно поставить знак за место *.
Есть 3 вариант знаков
1) нечего не ставить.
2)+
3)-
И начинаем перебирать.
1 шаг нечего не ставим. получаем 123456789 и сравниваем с тем что ввели. если верно то стоп. если нет то дальше
2 шаг 1 2 3 4 5 6 7 8 + 9 сравниваем
3 шаг 1 2 3 4 5 6 7 8 -9 сравниваем
4 шаг 1 2 3 4 5 6 7 + 89
5 шаг 1 2 3 4 5 6 7 + 8 + 9
6 шаг 1 2 3 4 5 6 7 + 8 - 9
7 шаг 1 2 3 4 5 6 7 - 89
8 шаг 1 2 3 4 5 6 7 - 8 + 9
9 шаг 1 2 3 4 5 6 7 - 8 - 9
и так пока не найдем решение, если его нету то переберем все варианты.
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 14
01.11.2016, 15:54  [ТС]     Разобраться с алгоритмом задачи #3
Это тут successfully_inc_ternary_number происходит перебор. Не мог бы описать каждую строку этой процедуры? Спасибо)
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 55
01.11.2016, 16:09     Разобраться с алгоритмом задачи #4
Тут заполняется вектор который отвечает за значение знаком вежду числами.
0 - нечего не ставим
1 - плюс
2 - минус
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool successfully_inc_ternary_number(T_ternary_number & ternary_number)
{// на вход принимаем вектор
  for (int i = ternary_number.size() - 1; i >= 0; --i) // цикл от (размер вектора ternary_number -1) до 0
  {
    if (ternary_number[i] < 3)  //если еще не все варианты для данной позиции перебрали то
    {
      ++ternary_number[i]; //делаем + 1, 
      return true; //завершаем и пробуем новый вариант перебора
    }
    else //для данной позиции перебрали 3 варианта знаков то
    {
      ternary_number[i] = 0; // зануляем ее и переходим к след. элементу вектора
    }
  }//for
 
  return false; // если все варианты перебрали и не нашли решения
}
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 14
01.11.2016, 16:35  [ТС]     Разобраться с алгоритмом задачи #5
И последний вопрос) В этой процедуре successfully_set_expr я так понимаю идет сравнивание результатов successfully_inc_ternary_number с числом n введенным с клавиатуры?
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 55
01.11.2016, 17:01     Разобраться с алгоритмом задачи #6
MDefs, Да.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool successfully_set_expr(int n, T_expr & expr) //принимаем n- число с клавиатуры и пустую строку
{
static const T_expr DIGITS{ "123456789" }; // создаем строку из наших чисел
T_ternary_number ternary_number(DIGITS.size() - 1); // вектор размером длина строки -1
 
do
{
expr = make_expr(ternary_number, DIGITS); //из строки DIGITS и вектора значений получаем новую строку типо 1234567+89
if (calc_expr( expr ) == n) //из новой строки получаем числа и считаем результат после сравниваем с числом введеным из клав.
{
return true; //если совпало то все завершаем.
}
}
while (successfully_inc_ternary_number( ternary_number )); //тут заполняем вектор разными вариантами пока все не переберем
 
return false; // если все варианты перебрали то нету решения
}
Yandex
Объявления
01.11.2016, 17:01     Разобраться с алгоритмом задачи
Ответ Создать тему
Опции темы

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