如何设计算法来计算倒计时风格的数学数字拼图
我一直想这样做但每次我开始思考这个问题时都会因为其指数性而引起我的注意。
我希望能够理解和编码的问题解决方案是倒计时数学问题：
给定数字X1到X5的集合计算如何使用数学运算来组合Y.您可以应用乘法，除法，加法和减法。
那么1,3,7,6,8,3如何制作348 ？
答案： (((8 * 7) + 3) -1) *6 = 348 。
如何编写可以解决这个问题的算法？ 在尝试解决这样的问题时你从哪里开始？ 在设计这样的算法时，您需要考虑哪些重要的考虑因素？
Java中非常快速和肮脏的解决方案：
public class JavaApplication1 { public static void main(String[] args) { List list = Arrays.asList(1, 3, 7, 6, 8, 3); for (Integer integer : list) { List runList = new ArrayList<>(list); runList.remove(integer); Result result = getOperations(runList, integer, 348); if (result.success) { System.out.println(integer + result.output); return; } } } public static class Result { public String output; public boolean success; } public static Result getOperations(List numbers, int midNumber, int target) { Result midResult = new Result(); if (midNumber == target) { midResult.success = true; midResult.output = ""; return midResult; } for (Integer number : numbers) { List newList = new ArrayList (numbers); newList.remove(number); if (newList.isEmpty()) { if (midNumber - number == target) { midResult.success = true; midResult.output = "-" + number; return midResult; } if (midNumber + number == target) { midResult.success = true; midResult.output = "+" + number; return midResult; } if (midNumber * number == target) { midResult.success = true; midResult.output = "*" + number; return midResult; } if (midNumber / number == target) { midResult.success = true; midResult.output = "/" + number; return midResult; } midResult.success = false; midResult.output = "f" + number; return midResult; } else { midResult = getOperations(newList, midNumber - number, target); if (midResult.success) { midResult.output = "-" + number + midResult.output; return midResult; } midResult = getOperations(newList, midNumber + number, target); if (midResult.success) { midResult.output = "+" + number + midResult.output; return midResult; } midResult = getOperations(newList, midNumber * number, target); if (midResult.success) { midResult.output = "*" + number + midResult.output; return midResult; } midResult = getOperations(newList, midNumber / number, target); if (midResult.success) { midResult.output = "/" + number + midResult.output; return midResult } } } return midResult; } }
UPDATE
它基本上只是具有指数复杂性的简单蛮力算法。 但是，您可以通过利用一些启发式函数来获得一些改进，这将有助于您订购数字序列或（和）您将在每个级别的getOperatiosn()函数递归中处理的操作。
这种启发式函数的示例例如是中间结果和总目标结果之间的差异。
然而，这种方式只能改善最佳情况和平均情况的复杂性。 最糟糕的案件复杂性仍未受到影响。
通过某种分支切割可以改善最坏情况的复杂性。 我不确定在这种情况下是否可行。
当然它是指数但它很小，所以一个好的（足够）天真的实现将是一个良好的开端。 我建议你删除通常的中缀符号括号，并使用postfix，它更容易编程。 您总是可以将输出美化为一个单独的阶段。
首先列出并评估所有（有效）数字和运算符序列。 例如（在后缀中）：
1 3 7 6 8 3 + + + + + -> 28 1 3 7 6 8 3 + + + + - -> 26
我的Java是可笑的，我不是来这里被嘲笑所以我会把这个编码留给你。
对于所有读这篇文章的聪明人：是的，我知道即使像这样的小问题也有更聪明的方法可能会更快，我只是将OP指向一个初始的工作解决方案。 其他人可以用更智能的解决方案来回答问题。
那么，回答你的问题：
- 我从一个算法开始，我认为这将引导我快速找到一个有效的解决方案。 在这种情况下，明显的（对我而言）选择是详尽的枚举和测试所有可能的计算。
- 如果显而易见的算法由于性能原因看起来没有吸引力，我会开始更深入地思考它，回想一下我所知道的其他可能提供更好性能的算法。 我可能会先开始编写其中一个。
- 如果我坚持使用详尽的算法并发现运行时间实际上太长了，那么我可能会回到上一步并重新编码。 但它值得我花时间，需要进行成本/收益评估 – 只要我的代码能超越Rachel Riley，我就会感到满意。
- 重要的考虑因素包括我的时间与计算机时间，我的成本更高。
下面的c ++ 11中的工作解决方案。
基本思想是使用基于堆栈的评估（请参阅RPN ）并将可行解决方案转换为中缀表示法仅用于显示目的。
如果我们有N输入数字，我们将使用(N-1)运算符，因为每个运算符都是二进制的。
首先，我们创建操作数和运算符的有效排列 （ selector_数组）。 有效排列是可以在没有堆栈下溢的情况下进行评估并且在堆栈上以恰好一个值（结果）结束的排列。 因此1 1 +是有效的，但1 + 1不是。
我们用操作数的每个排列（ values_数组）和每个运算符组合（ ops_数组）测试每个这样的操作数 – 运算符置换。 匹配的结果很漂亮。
参数从命令行获取为[-s] 。 -s开关可防止穷举搜索，仅打印第一个匹配结果。
（使用./mathpuzzle 348 1 3 7 6 8 3获得原始问题的答案）
此解决方案不允许将输入数字连接到表单编号。 这可以作为额外的外部循环添加。
工作代码可以从这里下载。 （注意：我更新了该代码，支持连接输入数字以形成解决方案）
有关其他说明，请参阅代码注释
#include #include #include #include #include #include namespace { enum class Op { Add, Sub, Mul, Div, }; const std::size_t NumOps = static_cast(Op::Div) + 1; const Op FirstOp = Op::Add; using Number = int; class Evaluator { std::vector values_; // stores our digits/number we can use std::vector ops_; // stores the operators std::vector selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector, but that's broken template using Stack = std::stack>; // 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 &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 ::max(); } Number res = stack.top() / top; if (res * top != stack.top()) { return std::numeric_limits ::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(*i) + 1; if (next < NumOps) { *i = static_cast(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 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& 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 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] [ ]...\n"; std::exit(1); } Number target = std::stoi(argv[i]); std::vector 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 = {+， – ，*，/}。 最直接的算法是powershell求解器，它列举了这些集合的所有可能组合。 可以根据需要经常使用集合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操作。 这意味着这可能是您对暴力算法的限制。
一旦你有蛮力并且你知道它有效，你可以用某种A *算法开始改进你的算法，这需要你定义启发式函数。
在我看来，考虑它的最佳方式是搜索问题。 主要的困难是寻找良好的启发式方法，或者减少问题空间的方法（如果你的数字没有达到答案，你至少需要一次乘法等）。 从小处开始，以此为基础，并在获得一些代码后询问后续问题。
很久以前，我从牛津大学的计算机科学文献 （使用Java源代码）中找到了很好的算法。 每次读这个解决方案时我都很佩服。 我相信它会有所帮助。
这个确切的问题在Graham Hutton的“Haskell编程”第9章中有所介绍。 如果他们对问题的function语言方法感兴趣，可以看一下。