我一直想做这件事，但每次开始思考这个问题时，由于其成倍增长的本质让我感到很困惑。
我想要理解和编写的问题的解决方案是倒计时数学问题：
给定数字X1到X5的集合，计算它们如何使用数学运算符组合以得出Y。可以应用乘法，除法，加法和减法。
那么，如何使用1,3,7,6,8,3得出348？
答案：(((8 * 7) + 3) -1) *6 = 348。
如何编写一个能够解决这个问题的算法？当尝试解决这样的问题时，从哪里开始？在设计这样的算法时，需要考虑哪些重要因素？
如何设计算法来计算倒数风格的数学数字谜题
28
- drlobo
4
6暴力破解？即尝试所有可能的组合，直到得出正确答案。 - Some programmer dude
2真的很酷的问题。最困难的运算符是组合运算，其中您将2个或更多数字放在一起创建双位数（或三位数等），因为该运算符只能用于“原始”数字而不是计算数字。例如：368-17-3 = 348。 - Klas Lindbäck
1这个回答似乎很相关：http://stackoverflow.com/questions/14309515/all-possible-numerical-expressions/14309855#14309855 - rici
暴力破解。只要任何部分结果不是整数，您就可以跳过其余部分（至少对于我所知道的电视节目来说，这是一种限制）。 - MrSmith42
9个回答
7
下面是c++11的可行解决方案。
基本思路是使用基于堆栈的计算（参见RPN）并将可行解决方案转换为中缀表示法，仅用于显示目的。
如果我们有
首先，我们创建操作数和运算符的有效排列（
我们使用每个操作数的排列（
参数从命令行中获取，格式为
基本思路是使用基于堆栈的计算（参见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;
}
- mitchnull
7
当然，这是指数级的，但非常小，因此一个足够好的天真实现将是一个很好的开始。我建议您放弃使用带括号的通常中缀符号表示法，而使用后缀表示法，这样更容易编程。您始终可以将输出美化为单独的阶段。
首先列出并评估所有（有效的）数字和运算符序列。例如（以后缀表示法）：
1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26
我的Java水平有限，我不想被嘲笑，所以我将这个编码工作留给你。
对于所有聪明的读者：是的，我知道即使像这样的小问题也有更聪明的方法，这些方法很可能更快，我只是为了指导OP找到一个初始的工作解决方案。其他人可以使用更聪明的解决方案编写答案。
所以，回答您的问题：
- 我从我认为会快速带我到一个工作解决方案的算法开始。在这种情况下，显而易见的（对我来说）选择是枚举和测试所有可能的计算。
- 如果显而易见的算法看起来因性能原因不吸引人，那么我将开始更深入地思考它，回想起其他我所知道的可能提供更好性能的算法。我可能首先开始编写其中之一。
- 如果我坚持采用详尽的算法，并发现实际运行时间太长，则我可能会返回到上一个步骤并再次编码。但必须值得我的付出，需要进行成本效益评估-只要我的代码能够胜过 Rachel Riley，我就会满意。
- 重要考虑因素包括我的时间与电脑时间，我的时间成本高得多。
- High Performance Mark
7
这绝对是要做的事情。问题的顺序是4^5个运算符组合*（9选4）个运算符位置。（字符串中的第一个元素必须是数字，最后一个必须是运算符）。其他序列可能会产生非法树。这大约有1亿种组合？ - Aki Suihkonen
此外，方程式表示法的选择是正确的——后缀或逆波兰表示法可以表示方程式中所有括号的组合，尽管可能会导致重复表示。组合分析仍然表明这个任务是可行的。 - Aki Suihkonen
1我有一种感觉，按照6！数字与4^5运算符的顺序连接起来，不能处理带有括号的情况——因为这种顺序只能产生左或右结合表达式。我认为无法使用“N N N N op op op”计算(1+2)/(3+4)。 - Aki Suihkonen
1我能想到的最简单的反例是(1-3)-7，这不能通过对1、3、7进行排列并跟随'--'来计算。 - Aki Suihkonen
1我可能不太理解你们这里的意思。我不推荐后缀表达式。我建议的是简单的数字列表和要应用的操作列表。这可以解决大多数问题，但像“(a+b)/(c+d)”这样的技巧需要在内存中占用2个位置。 - bjedrzejewski
显示剩余2条评论
7
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;
}
}
更新
这基本上只是一种具有指数复杂度的简单暴力算法。但是，您可以通过利用一些启发式函数来改进算法，该函数将帮助您按顺序处理每个getOperatiosn()函数递归级别中的数字或(和)运算。
这样的启发式函数的一个例子是中间结果与目标总结果之间的差异。
然而，这只能改善最好情况和平均情况下的复杂度。最坏情况复杂度保持不变。
可以通过某种分支剪枝来改善最坏情况的复杂性。我不确定在这种情况下是否可能。
- Ondrej Bozek
5
那份源代码在我的机器上无法编译（javac 1.6.0_41）。 - Arne
3是的，有一个钻石符号表示法 -
List<Integer> runList = new ArrayList<>(list); 你需要使用Java 7 或者用经典的Java语法替换钻石符号。 - Ondrej Bozek1我认为这个解决方案并不全面。对于原始问题，它只返回5个结果，而我的版本返回了500个结果。如果它似乎错过了一些有效的匹配项，我不确定它是否能够找到每个可能问题的有效解决方案。 - mitchnull
1我进行了一些测试，发现这确实无法找到“382 1,3,7,6,8,3”的匹配项。例如，一个有效的匹配是
382 = ((7 * ((3 + 8) * (6 - 1))) - 3)。 - mitchnull我认为应该有隐式括号，就像例子中描述的那样 -
(((8 * 7) + 3) -1) *6 = 348，对吗？你能确认我们也可以使用括号吗？如果是这样，我可以扩展我的解决方案。 - Ondrej Bozek5
输入显然是数字和运算符的集合：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的回答。
- Arne
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。不多。
有多少种可能性？由于您不必使用所有数字并且可以多次使用相同的运算符，因此这个问题等价于“您可以制作带有最多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个节点树等等，以此作为新形成的树的左右子树来创建所有具有n个节点的树。
因此，从一个空集开始，首先生成只有根节点的树，然后从新根开始，您可以将其用作左侧或右侧子树，从而产生两个看起来像这样的树：/ 和 . 以此类推。
您可以即时将它们转换为一组表达式（只需循环运算符和数字），并在进行计算时进行评估，直到其中一个产生目标数字。
- Angelo Wentzler
1
我已经用Python编写了自己的倒计时求解器。
以下是代码；它也可以在GitHub上找到：
对于长度为1到6的所有组，最大总计算次数为
以下是代码；它也可以在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]。
以这种方式生成所有结果，从最小的组到最大的组。最后，算法遍历所有结果，并选择与目标数字最接近的结果。
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等），而且游戏规则要求中间结果必须是正整数（这限制了除法运算的使用）。
- Pulsar
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中也是如此。）
基本上，最坏情况下它是暴力破解，因为据我所知，不可能确定任何特定分支是否会产生有效答案，除非明确检查。话虽如此，平均情况下是其中的一部分；它是{那个数字}除以有效解决方案的数量（我倾向于在我的程序中看到大约1000个解决方案，其中有10个左右是唯一的，其余是这些10个的排列组合）。如果我估算一个数字，我会说大约有2,765个分支需要检查，这需要很短的时间。（是的，即使在Python中也是如此。）
简而言之：尽管解决方案空间很大，需要执行数百万次操作才能找到所有解，但只需要一个答案。最好的方法是暴力搜索，直到找到一个解并输出。
- PG328
0
我认为，你需要先严格定义问题。你可以从简单的开始，只允许乘法、除法、减法和加法。
现在你知道了你的问题空间-输入集合、可用操作集合和所需输入。如果你只有4个操作和x个输入，组合数就少于：
你可以执行操作的顺序数量（x！）乘以每一步可能的操作选择：4^x。正如你所看到的，对于6个数字，它给出了合理的2949120个操作。这意味着这可能是你暴力算法的极限。
一旦你有了暴力算法并且知道它有效，你可以开始改进你的算法，使用某种A*算法，这将要求你定义启发式函数。
在我看来，最好的思考方式是将其视为搜索问题。主要困难将是找到良好的启发式方法，或者减少问题空间的方法（如果你有不能相加得到答案的数字，你将需要至少一个乘法等）。从小处开始，逐步构建，并在你有一些代码后提出跟进问题。
- bjedrzejewski
0
我写了一个稍微简化的版本：
- 对于列表中的每个2个（不同）元素的组合，使用+、-、*、/将它们组合起来（请注意，由于a>b，则只需要a-b，而如果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()
- Alan Swindells
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 5 组合数学实现和谜题
- 3 选择唯一的数字集合来表示数独谜题
- 30 寻找解决谜题的算法
- 6 创建十六进制洪水谜题的算法
- 10 需要设计一个数字计算算法。
- 44 高效的数学算法用于计算交点
- 12 一个快速创建谜题的算法
- 9 网格算法谜题
- 7 如何计算实数的阶乘倒数？
- 47 算法谜题面试