drl*_*obo 25 c++ java algorithm combinatorics
我一直想这样做但每次我开始思考这个问题时都会因为其指数性而引起我的注意.
我希望能够理解和编码的问题解决方案是倒计时数学问题:
给定数字X1到X5的集合计算如何使用数学运算来组合Y.您可以应用乘法,除法,加法和减法.
那怎么1,3,7,6,8,3做348？
答案:(((8 * 7) + 3) -1) *6 = 348.
如何编写可以解决这个问题的算法？在尝试解决这样的问题时你从哪里开始？在设计这样的算法时,您需要考虑哪些重要的考虑因素？
当然它是指数但它很小,所以一个好的(足够)天真的实现将是一个良好的开端.我建议你删除通常的中缀符号括号,并使用postfix,它更容易编程.您总是可以将输出美化为一个单独的阶段.
首先列出并评估所有(有效)数字和运算符序列.例如(在后缀中):
1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26
我的Java是可笑的,我不是来这里被嘲笑所以我会把这个编码留给你.
对于所有读这篇文章的聪明人:是的,我知道即使像这样的小问题也有更聪明的方法可能更快,我只是将OP指向最初的工作解决方案.其他人可以用更智能的解决方案来回答问题.
那么,回答你的问题:
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
它基本上只是具有指数复杂性的简单蛮力算法.但是,您可以通过利用一些启发式函数来获得一些改进,这将有助于您订购数字序列或(和)您将在每个getOperatiosn()函数递归级别处理的操作.
这种启发式函数的示例例如是中间结果和总目标结果之间的差异.
然而,这种方式只能改善最佳情况和平均情况的复杂性.最糟糕的案件复杂性仍未受到影响.
通过某种分支切割可以改善最坏情况的复杂性.在这种情况下,我不确定是否可能.
下面的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;
}
输入显然是一组数字和运算符: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的答案.
| 归档时间： |
|
| 查看次数： |
13317 次 |
| 最近记录： |