пазл — Как разработать алгоритм для вычисления математического числа в стиле обратного отсчета

Конечно, это экспоненциально, но крошечно, так что хорошая (достаточно) наивная реализация была бы хорошим началом. Я предлагаю вам отказаться от обычной инфиксной нотации с помощью скобок и использовать постфикс, это проще для программирования. Вы всегда можете предварительно настроить выходы как отдельный этап.

Начните с перечисления и оценки всех (действительных) последовательностей чисел и операторов. Например (в постфиксе):

1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26

Моя Java смехотворна, я не прихожу сюда, чтобы смеяться, поэтому я оставлю кодирование вам.

Всем умным людям, которые читают это: да, я знаю, что даже для небольшой проблемы, подобной этой, есть более разумные подходы, которые, вероятно, будут быстрее, я просто указываю OP на первоначальное рабочее решение. Кто-то другой может написать ответ с более умным решением (ями).

Итак, чтобы ответить на ваши вопросы:

• Я начну с алгоритма, который, я думаю, быстро приведет меня к рабочему решению. В этом случае очевидным (для меня) выбором является исчерпывающий перечень и проверка всех возможных расчетов.
• Если очевидный алгоритм выглядит непривлекательным по соображениям производительности, я начну задумываться о нем более подробно, вспомнив другие известные мне алгоритмы, которые, вероятно, будут обеспечивать более высокую производительность. Я могу вместо этого начать кодировать один из них.
• Если я придерживаюсь исчерпывающего алгоритма и обнаружу, что на практике время выполнения слишком велико, я мог бы вернуться к предыдущему шагу и снова написать код. Но это должно стоить моего времени, должна быть сделана оценка затрат / выгод — пока мой код может превзойти Рэйчел Райли, я был бы удовлетворен.
• Важные соображения включают мое время против компьютерное время у меня чертовски дороже.

Рабочее решение на с ++ 11 ниже.

Основная идея заключается в использовании оценки на основе стека (см. RPN) и преобразовать жизнеспособные решения в инфиксная запись только для демонстрации.

Если у нас есть N входные цифры, мы будем использовать (N-1) операторы, так как каждый оператор является двоичным.

Сначала мы создаем действительные перестановки операндов и операторов ( selector_ массив). Допустимая перестановка — это такая, которая может быть оценена без потери значения в стеке и заканчивается ровно одним значением (результатом) в стеке. таким образом 1 1 + действителен, но 1 + 1 не является.

Мы проверяем каждую такую ​​перестановку операндов-операторов с каждой перестановкой операндов ( values_ массив) и каждая комбинация операторов ( ops_ массив). Соответствующие результаты довольно напечатаны.

Аргументы взяты из командной строки как [-s] <target> <digit>[ <digit>...], -s Переключатель предотвращает исчерпывающий поиск, выводится только первый соответствующий результат.

(использование ./mathpuzzle 348 1 3 7 6 8 3 чтобы получить ответ на оригинальный вопрос)

Это решение не позволяет объединять входные цифры в числа. Это может быть добавлено в качестве дополнительного внешнего цикла.

Рабочий код можно скачать с Вот. (Примечание: я обновил этот код с поддержкой объединения входных цифр, чтобы сформировать решение)

Смотрите комментарии к коду для дополнительного объяснения.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iterator>
#include <string>

namespace {

enum class Op {
Add,
Sub,
Mul,
Div,
};

const std::size_t NumOps = static_cast<std::size_t>(Op::Div) + 1;
const Op FirstOp = Op::Add;

using Number = int;

class Evaluator {
std::vector<Number> values_; // stores our digits/number we can use
std::vector<Op> ops_; // stores the operators
std::vector<char> selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector<bool>, but that's broken

template <typename T>
using Stack = std::stack<T, std::vector<T>>;

// checks if a given number/operator order can be evaluated or not
bool isSelectorValid() const {
int numValues = 0;
for (auto s : selector_) {
if (s) {
if (--numValues <= 0) {
return false;
}
}
else {
++numValues;
}
}
return (numValues == 1);
}

// evaluates the current values_ and ops_ based on selector_
Number eval(Stack<Number> &stack) const {
auto vi = values_.cbegin();
auto oi = ops_.cbegin();
for (auto s : selector_) {
if (!s) {
stack.push(*(vi++));
continue;
}
Number top = stack.top();
stack.pop();
switch (*(oi++)) {
case Op::Add:
stack.top() += top;
break;
case Op::Sub:
stack.top() -= top;
break;
case Op::Mul:
stack.top() *= top;
break;
case Op::Div:
if (top == 0) {
return std::numeric_limits<Number>::max();
}
Number res = stack.top() / top;
if (res * top != stack.top()) {
return std::numeric_limits<Number>::max();
}
stack.top() = res;
break;
}
}
Number res = stack.top();
stack.pop();
return res;
}

bool nextValuesPermutation() {
return std::next_permutation(values_.begin(), values_.end());
}

bool nextOps() {
for (auto i = ops_.rbegin(), end = ops_.rend(); i != end; ++i) {
std::size_t next = static_cast<std::size_t>(*i) + 1;
if (next < NumOps) {
*i = static_cast<Op>(next);
return true;
}
*i = FirstOp;
}
return false;
}

bool nextSelectorPermutation() {
// the start permutation is always valid
do {
if (!std::next_permutation(selector_.begin(), selector_.end())) {
return false;
}
} while (!isSelectorValid());
return true;
}

static std::string buildExpr(const std::string& left, char op, const std::string &right) {
return std::string("(") + left + ' ' + op + ' ' + right + ')';
}

std::string toString() const {
Stack<std::string> stack;
auto vi = values_.cbegin();
auto oi = ops_.cbegin();
for (auto s : selector_) {
if (!s) {
stack.push(std::to_string(*(vi++)));
continue;
}
std::string top = stack.top();
stack.pop();
switch (*(oi++)) {
case Op::Add:
stack.top() = buildExpr(stack.top(), '+', top);
break;
case Op::Sub:
stack.top() = buildExpr(stack.top(), '-', top);
break;
case Op::Mul:
stack.top() = buildExpr(stack.top(), '*', top);
break;
case Op::Div:
stack.top() = buildExpr(stack.top(), '/', top);
break;
}
}
return stack.top();
}

public:
Evaluator(const std::vector<Number>& values) :
values_(values),
ops_(values.size() - 1, FirstOp),
selector_(2 * values.size() - 1, 0) {
std::fill(selector_.begin() + values_.size(), selector_.end(), 1);
std::sort(values_.begin(), values_.end());
}

// check for solutions
// 1) we create valid permutations of our selector_ array (eg: "1 1 + 1 +",
//    "1 1 1 + +", but skip "1 + 1 1 +" as that cannot be evaluated
// 2) for each evaluation order, we permutate our values
// 3) for each value permutation we check with each combination of
//    operators
//
// In the first version I used a local stack in eval() (see toString()) but
// it turned out to be a performance bottleneck, so now I use a cached
// stack. Reusing the stack gives an order of magnitude speed-up (from
// 4.3sec to 0.7sec) due to avoiding repeated allocations.  Using
// std::vector as a backing store also gives a slight performance boost
// over the default std::deque.
std::size_t check(Number target, bool singleResult = false) {
Stack<Number> stack;

std::size_t res = 0;
do {
do {
do {
Number value = eval(stack);
if (value == target) {
++res;
std::cout << target << " = " << toString() << "\n";
if (singleResult) {
return res;
}
}
} while (nextOps());
} while (nextValuesPermutation());
} while (nextSelectorPermutation());
return res;
}
};

} // namespace

int main(int argc, const char **argv) {
int i = 1;
bool singleResult = false;
if (argc > 1 && std::string("-s") == argv[1]) {
singleResult = true;
++i;
}
if (argc < i + 2) {
std::cerr << argv[0] << " [-s] <target> <digit>[ <digit>]...\n";
std::exit(1);
}
Number target = std::stoi(argv[i]);
std::vector<Number> values;
while (++i <  argc) {
values.push_back(std::stoi(argv[i]));
}
Evaluator evaluator{values};
std::size_t res = evaluator.check(target, singleResult);
if (!singleResult) {
std::cout << "Number of solutions: " << res << "\n";
}
return 0;
}

Ввод, очевидно, представляет собой набор цифр и операторов: D = {1,3,3,6,7,8,3} и Op = {+, -, *, /}. Самый простой алгоритм будет грубая сила решатель, который перечисляет все возможные комбинации этих наборов. Где элементы множества Op могут использоваться так часто, как хотелось бы, но элементы из множества D используются ровно один раз. Псевдокод:

D={1,3,3,6,7,8,3}
Op={+,-,*,/}
Solution=348
for each permutation D_ of D:
for each binary tree T with D_ as its leafs:
for each sequence of operators Op_ from Op with length |D_|-1:
label each inner tree node with operators from Op_
result = compute T using infix traversal
if result==Solution
return T
return nil

Кроме этого: прочитайте ответы jedrus07 и HPM.

Я думаю, вам нужно строго определить проблему в первую очередь. Что вам разрешено делать, а что нет. Вы можете начать с простого и умножения, деления, вычитания и сложения.

Теперь вы знаете свое проблемное пространство — набор входов, набор доступных операций и желаемый вход. Если у вас есть только 4 операции и x входов, количество комбинаций меньше чем:

Номер порядка, в котором вы можете выполнять операции (x!), Умноженный на возможные варианты операций на каждом шаге: 4 ^ x. Как видно из 6 номеров, это дает разумные 2949120 операций. Это означает, что это может быть вашим пределом для алгоритма перебора.

Если у вас есть грубая сила, и вы знаете, что это работает, вы можете начать улучшать свой алгоритм с Алгоритм * что потребует от вас определить эвристические функции.

На мой взгляд, лучший способ думать об этом — это проблема поиска. Основной трудностью будет поиск хорошей эвристики или способов уменьшить пространство проблем (если у вас есть числа, которые не суммируют с ответом, вам потребуется хотя бы одно умножение и т. Д.). Начните с малого, постройте это и задавайте дополнительные вопросы, как только у вас появится код.

Я нашел отличный алгоритм из Оксфордские документы по информатике (с исходным кодом Java) давно. И я восхищаюсь этим каждый раз, когда читаю это решение. Я верю, что это будет полезно.