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

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

Восстановить пароль Регистрация
 
MDefs
0 / 0 / 0
Регистрация: 01.10.2016
Сообщений: 13
01.11.2016, 13:51     Разобраться с алгоритмом задачи #1
Помогите разобраться с алгоритмом, как работает программа. Я понимаю что здесь 38 перестановок. Но мне нужно знать как именно работает эта программа, точный алгоритм.

Вот задача:

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

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 53
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
Сообщений: 13
01.11.2016, 15:54  [ТС]     Разобраться с алгоритмом задачи #3
Это тут successfully_inc_ternary_number происходит перебор. Не мог бы описать каждую строку этой процедуры? Спасибо)
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 53
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
Сообщений: 13
01.11.2016, 16:35  [ТС]     Разобраться с алгоритмом задачи #5
И последний вопрос) В этой процедуре successfully_set_expr я так понимаю идет сравнивание результатов successfully_inc_ternary_number с числом n введенным с клавиатуры?
Igor_s
11 / 11 / 4
Регистрация: 16.07.2014
Сообщений: 53
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     Разобраться с алгоритмом задачи
Ответ Создать тему
Опции темы

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