我一直想这样做，但每次我开始思考这个问题时，它都会让我大吃一惊，因为它是指数级的。
我希望能够理解和编码的问题解决者是倒计时数学问题：
给定一组数字 X1 到 X5，计算如何使用数学运算将它们组合成 Y。您可以应用乘法、除法、加法和减法。
那么如何1,3,7,6,8,3制作348呢？
答案：(((8 * 7) + 3) -1) *6 = 348。
如何编写一个可以解决这个问题的算法？当你试图解决这样的问题时，你从哪里开始？在设计这样的算法时，你必须考虑哪些重要的考虑因素？
问问题
19204 次
9 回答
7
Very quick and dirty solution in Java:
public class JavaApplication1
{
public static void main(String[] args)
{
List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3);
for (Integer integer : list) {
List<Integer> 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<Integer> numbers, int midNumber, int target)
{
Result midResult = new Result();
if (midNumber == target) {
midResult.success = true;
midResult.output = "";
return midResult;
}
for (Integer number : numbers) {
List<Integer> newList = new ArrayList<Integer>(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
It's basically just simple brute force algorithm with exponential complexity.
However you can gain some improvemens by leveraging some heuristic function which will help you to order sequence of numbers or(and) operations you will process in each level of getOperatiosn() function recursion.
Example of such heuristic function is for example difference between mid result and total target result.
This way however only best-case and average-case complexities get improved. Worst case complexity remains untouched.
Worst case complexity can be improved by some kind of branch cutting. I'm not sure if it's possible in this case.
于 2013-03-08T13:02:35.320 回答
7
当然它是指数级的，但它很小，所以一个好的（足够）天真的实现将是一个好的开始。我建议你放弃通常的带括号的中缀符号，并使用后缀，它更容易编程。您始终可以将输出美化为单独的阶段。
首先列出并评估所有（有效的）数字和运算符序列。例如（在后缀中）：
1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26
我的 Java 很可笑，我来这里不是为了被嘲笑，所以我将把这个代码留给你。
对于所有阅读本文的聪明人：是的，我知道即使是像这样的小问题也有可能更快的更聪明的方法，我只是将 OP 指向一个初始的工作解决方案。其他人可以用更聪明的解决方案写出答案。
所以，回答你的问题：
- 我从一个算法开始，我认为它会很快引导我找到一个可行的解决方案。在这种情况下，（对我而言）显而易见的选择是对所有可能的计算进行详尽的枚举和测试。
- 如果显而易见的算法由于性能原因看起来没有吸引力，我将开始更深入地思考它，回想我知道的其他可能提供更好性能的算法。我可能会先开始编写其中的一个。
- 如果我坚持使用穷举算法并发现运行时间实际上太长，那么我可能会回到上一步并再次编码。但这必须是值得我花时间的，需要进行成本/收益评估——只要我的代码能够胜过 Rachel Riley，我就会感到满意。
- 重要的考虑因素包括我的时间与计算机时间，我的成本要高得多。
于 2013-03-08T11:53:46.953 回答
7
下面的 c++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;
}
于 2013-03-12T08:52:02.157 回答
5
输入显然是一组数字和运算符：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 的答案。
于 2013-03-08T11:57:05.300 回答
1
到目前为止，最简单的方法是智能地暴力破解它。您只能用 6 个数字和 4 个运算符构建有限数量的表达式，只需遍历所有表达式即可。
多少？由于您不必使用所有数字并且可以多次使用相同的运算符，因此此问题相当于“您最多可以使用 6 个叶子和四个可能的标签制作多少个严格标记的二叉树（又名完整二叉树）对于每个非叶节点？”。
具有 n 个叶子的完整二叉树的数量等于 catalan(n-1)。你可以看到如下：
每个具有 n 个叶子的完整二叉树都有 n-1 个内部节点，并且以独特的方式对应于具有 n-1 个节点的非完整二叉树（只需从完整的叶子中删除所有叶子即可获得它）。恰好有 catalan(n) 可能的二叉树有 n 个节点，所以我们可以说一棵有 n 个叶子的严格二叉树有 catalan(n-1) 可能的不同结构。
每个非叶子节点有 4 种可能的运算符： 4^(n-1) 种可能性叶子可以在 n 中编号！* (6 选择 (n-1)) 不同的方式。（除以 k！对于出现 k 次的每个数字，或者只是确保所有数字都不同）
因此，对于 6 个不同的数字和 4 个可能的运算符，您会得到 Sum(n=1...6) [ Catalan(n-1) * 6!/(6-n)! * 4^(n-1) ] 总共 33,665,406 个可能的表达式。不是很多。
你如何列举这些树？
给定具有 n-1 个或更少节点的所有树的集合，您可以通过将所有 n-1 树与空树、所有 n-2 树与 1 个节点树、所有 n -3棵树，所有2个节点树等，并将它们用作新形成的树的左右子树。
因此，从一个空集开始，您首先生成只有一个根节点的树，然后从一个新的根节点开始，您可以将其用作左子树或右子树，生成两棵树，如下所示： / 和 . 等等。
您可以即时将它们转换为一组表达式（只需遍历运算符和数字）并随时评估它们，直到产生目标数字。
于 2019-03-18T16:04:46.350 回答
1
我用 Python 编写了自己的倒计时求解器。
这是代码；它也可以在GitHub上找到：
#!/usr/bin/env python3
import sys
from itertools import combinations, product, zip_longest
from functools import lru_cache
assert sys.version_info >= (3, 6)
class Solutions:
def __init__(self, numbers):
self.all_numbers = numbers
self.size = len(numbers)
self.all_groups = self.unique_groups()
def unique_groups(self):
all_groups = {}
all_numbers, size = self.all_numbers, self.size
for m in range(1, size+1):
for numbers in combinations(all_numbers, m):
if numbers in all_groups:
continue
all_groups[numbers] = Group(numbers, all_groups)
return all_groups
def walk(self):
for group in self.all_groups.values():
yield from group.calculations
class Group:
def __init__(self, numbers, all_groups):
self.numbers = numbers
self.size = len(numbers)
self.partitions = list(self.partition_into_unique_pairs(all_groups))
self.calculations = list(self.perform_calculations())
def __repr__(self):
return str(self.numbers)
def partition_into_unique_pairs(self, all_groups):
# The pairs are unordered: a pair (a, b) is equivalent to (b, a).
# Therefore, for pairs of equal length only half of all combinations
# need to be generated to obtain all pairs; this is set by the limit.
if self.size == 1:
return
numbers, size = self.numbers, self.size
limits = (self.halfbinom(size, size//2), )
unique_numbers = set()
for m, limit in zip_longest(range((size+1)//2, size), limits):
for numbers1, numbers2 in self.paired_combinations(numbers, m, limit):
if numbers1 in unique_numbers:
continue
unique_numbers.add(numbers1)
group1, group2 = all_groups[numbers1], all_groups[numbers2]
yield (group1, group2)
def perform_calculations(self):
if self.size == 1:
yield Calculation.singleton(self.numbers[0])
return
for group1, group2 in self.partitions:
for calc1, calc2 in product(group1.calculations, group2.calculations):
yield from Calculation.generate(calc1, calc2)
@classmethod
def paired_combinations(cls, numbers, m, limit):
for cnt, numbers1 in enumerate(combinations(numbers, m), 1):
numbers2 = tuple(cls.filtering(numbers, numbers1))
yield (numbers1, numbers2)
if cnt == limit:
return
@staticmethod
def filtering(iterable, elements):
# filter elements out of an iterable, return the remaining elements
elems = iter(elements)
k = next(elems, None)
for n in iterable:
if n == k:
k = next(elems, None)
else:
yield n
@staticmethod
@lru_cache()
def halfbinom(n, k):
if n % 2 == 1:
return None
prod = 1
for m, l in zip(reversed(range(n+1-k, n+1)), range(1, k+1)):
prod = (prod*m)//l
return prod//2
class Calculation:
def __init__(self, expression, result, is_singleton=False):
self.expr = expression
self.result = result
self.is_singleton = is_singleton
def __repr__(self):
return self.expr
@classmethod
def singleton(cls, n):
return cls(f"{n}", n, is_singleton=True)
@classmethod
def generate(cls, calca, calcb):
if calca.result < calcb.result:
calca, calcb = calcb, calca
for result, op in cls.operations(calca.result, calcb.result):
expr1 = f"{calca.expr}" if calca.is_singleton else f"({calca.expr})"
expr2 = f"{calcb.expr}" if calcb.is_singleton else f"({calcb.expr})"
yield cls(f"{expr1} {op} {expr2}", result)
@staticmethod
def operations(x, y):
yield (x + y, '+')
if x > y: # exclude non-positive results
yield (x - y, '-')
if y > 1 and x > 1: # exclude trivial results
yield (x * y, 'x')
if y > 1 and x % y == 0: # exclude trivial and non-integer results
yield (x // y, '/')
def countdown_solver():
# input: target and numbers. If you want to play with more or less than
# 6 numbers, use the second version of 'unsorted_numbers'.
try:
target = int(sys.argv[1])
unsorted_numbers = (int(sys.argv[n+2]) for n in range(6)) # for 6 numbers
# unsorted_numbers = (int(n) for n in sys.argv[2:]) # for any numbers
numbers = tuple(sorted(unsorted_numbers, reverse=True))
except (IndexError, ValueError):
print("You must provide a target and numbers!")
return
solutions = Solutions(numbers)
smallest_difference = target
bestresults = []
for calculation in solutions.walk():
diff = abs(calculation.result - target)
if diff <= smallest_difference:
if diff < smallest_difference:
bestresults = [calculation]
smallest_difference = diff
else:
bestresults.append(calculation)
output(target, smallest_difference, bestresults)
def output(target, diff, results):
print(f"\nThe closest results differ from {target} by {diff}. They are:\n")
for calculation in results:
print(f"{calculation.result} = {calculation.expr}")
if __name__ == "__main__":
countdown_solver()
该算法的工作原理如下：
这些数字按降序放入长度为 6 的元组中。然后，创建长度为 1 到 6 的所有唯一子组，首先创建最小的组。
示例：(75, 50, 5, 9, 1, 1) -> {(75), (50), (9), (5), (1), (75, 50), (75, 9), (75, 5), ..., (75, 50, 9, 5, 1, 1)}。
接下来，这些组被组织成一个层次树：每个组都被划分为其非空子组的所有唯一无序对。
示例：(9, 5, 1, 1) -> [(9, 5, 1) + (1), (9, 1, 1) + (5), (5, 1, 1) + (9), (9, 5) + (1, 1), (9, 1) + (5, 1)]。
在每组数字中，都会执行计算并存储结果。对于长度为 1 的组，结果只是数字本身。对于较大的组，对每对子组进行计算：在每对子组中，使用 +、-、x 和 / 将第一个子组的所有结果与第二个子组的所有结果组合，并存储有效结果。
示例：(75, 5) 由对 ((75), (5)) 组成。(75)的结果是75；(5)的结果是5；(75, 5) 的结果是 [75+5=80, 75-5=70, 75*5=375, 75/5=15]。
以这种方式，从最小的组到最大的组都生成了所有结果。最后，算法遍历所有结果并选择与目标数最接近的结果。
对于一组 m 个数，最大算术计算次数为
comps[m] = 4*sum(binom(m, k)*comps[k]*comps[m-k]//(1 + (2*k)//m) for k in range(1, m//2+1))
对于长度为 1 到 6 的所有组，最大总计算次数为
total = sum(binom(n, m)*comps[m] for m in range(1, n+1))
即 1144386。实际上，它会少得多，因为该算法重用了重复组的结果，忽略了琐碎的操作（加 0、乘以 1 等），并且因为游戏规则规定中间结果必须是正整数（这限制了除法运算符的使用）。
于 2019-10-19T20:37:29.157 回答
0
我认为，您需要先严格定义问题。你被允许做什么，你不能做什么。你可以从简单开始，只允许乘法、除法、减法和加法。
现在你知道了你的问题空间——输入集、可用操作集和所需输入。如果您只有 4 个操作和 x 个输入，则组合数小于：
您可以执行操作的顺序数（x！）乘以每一步操作的可能选择：4^x。正如你所看到的 6 个数字，它给出了合理的 2949120 操作。这意味着这可能是您对蛮力算法的限制。
一旦你有了蛮力并且知道它有效，你就可以开始使用某种A* 算法来改进你的算法，这需要你定义启发式函数。
在我看来，考虑它的最佳方式是搜索问题。主要困难将是找到好的启发式方法，或减少问题空间的方法（如果您的数字与答案相加，则至少需要一个乘法等）。从小处着手，在此基础上构建，并在获得一些代码后提出后续问题。
于 2013-03-08T11:54:19.167 回答
0
我写了一个稍微简单的版本：
- 对于列表中 2 个（不同）元素的每个组合，并使用 +、-、*、/ 组合它们（请注意，由于 a>b，因此只需要 ab，如果 a%b=0，则只需要 a/b）
- 如果组合是目标，则记录解决方案
- 递归调用简化列表
import sys
def driver():
try:
target = int(sys.argv[1])
nums = list((int(sys.argv[i+2]) for i in range(6)))
except (IndexError, ValueError):
print("Provide a list of 7 numbers")
return
solutions = list()
solve(target, nums, list(), solutions)
unique = set()
final = list()
for s in solutions:
a = '-'.join(sorted(s))
if not a in unique:
unique.add(a)
final.append(s)
for s in final: #print them out
print(s)
def solve(target, nums, path, solutions):
if len(nums) == 1:
return
distinct = sorted(list(set(nums)), reverse = True)
rem1 = list(distinct)
for n1 in distinct: #reduce list by combining a pair
rem1.remove(n1)
for n2 in rem1:
rem2 = list(nums) # in case of duplicates we need to start with full list and take out the n1,n2 pair of elements
rem2.remove(n1)
rem2.remove(n2)
combine(target, solutions, path, rem2, n1, n2, '+')
combine(target, solutions, path, rem2, n1, n2, '-')
if n2 > 1:
combine(target, solutions, path, rem2, n1, n2, '*')
if not n1 % n2:
combine(target, solutions, path, rem2, n1, n2, '//')
def combine(target, solutions, path, rem2, n1, n2, symb):
lst = list(rem2)
ans = eval("{0}{2}{1}".format(n1, n2, symb))
newpath = path + ["{0}{3}{1}={2}".format(n1, n2, ans, symb[0])]
if ans == target:
solutions += [newpath]
else:
lst.append(ans)
solve(target, lst, newpath, solutions)
if __name__ == "__main__":
driver()
于 2020-03-02T21:24:25.780 回答
0
我写了一个终端应用程序来做到这一点： https ://github.com/pg328/CountdownNumbersGame/tree/main
在里面，我包含了一个解空间大小的计算说明（它是 n*((n-1)!^2)*(2^n-1)，所以：n=6 -> 2,764,800。我知道，恶心），更重要的是为什么会这样。如果您想检查一下，我的实现就在那里，但如果您不这样做，我会在这里解释。
从本质上讲，最坏的情况是蛮力，因为据我所知，如果没有明确检查，就不可能确定任何特定分支是否会产生有效答案。话虽如此，平均情况只是其中的一小部分。它是 {那个数字} 除以有效解决方案的数量（我倾向于在我的程序中看到大约 1000 个，其中 10 个左右是唯一的，其余的是这 10 个的排列）。如果我用手挥动一个数字，我会说大约有 2,765 个分支来检查哪个不需要时间。（是的，即使在 Python 中也是如此。）
TL;DR：尽管解决方案空间很大，并且需要数百万次操作才能找到所有解决方案，但只需要一个答案。最好的方法是蛮力，直到你找到一个并吐出来。
于 2020-11-16T23:07:20.963 回答