找出四个 10 的所有表达式 [英] Find all expressions of four 10s

问题描述

我遇到了一个 CS 问题.

I was challenged with a CS problem.

问题在于递归地找出 ((10+10)/(10+10)) 形式的哪些表达式产生一个数字.例如，((10+10)/(10+10)) 产生 1.使用运算符 +、-、*、/，以及 4 个 10 和括号的所有组合来查找所有其他表达式以强制执行顺序操作.

The problem consists of recursively finding which expressions of the form ((10+10)/(10+10)) produces a number. For example, ((10+10)/(10+10)) produces 1. Find all the other expressions using the operators +, -, *, /, with 4 numbers of 10, and all the combinations of parentheses to enforce orders of operations.

我被提到了反向波兰表示法，但它依赖于后缀表示法，这不是解决这个问题所必需的.

I was referred to the Reverse Polish Notation, but that relies on postfix notation, which isn’t required to solve this problem.

我有一些伪代码是这样的.我知道使用递归是解决这个问题的最简单方法.但不知道如何确保我得到所有组合.

Some pseudocode I have is this. I know using recursion is the easiest way to solve this problem. But don't know how to make sure I get all combinations.

build([10,10,10,10], Expression) :-
      Operator
     /       
   [10]     [10,10,10]
             Operator
              /     
           [10]     [10,10]
                    Operator
                     /    
                   [10]   [10]

这是我试图在 Prolog 中解决的问题，但 C++ 也很好.

This is a problem I am trying to solve in Prolog but C++ is good as well.

推荐答案

我有一个部分解决方案，我将在这里概述，希望它能让你感动，你可以找到完整的解决方案.

I have a partial solution which I will outline here and hopefully it will get you moving and you can find the complete solution.

您需要的第一个工具是能够做出一些表达:

The first tool you need is the ability to make some expressions:

build_expr(X, Y, X+Y).
build_expr(X, Y, X*Y).
build_expr(X, Y, X-Y).
build_expr(X, Y, X/Y).

这定义了build_expr/3，它接受两个变量或表达式并产生一个新的表达式.这就是我们将如何排列运算符.现在我们需要一种方法来处理列表，所以让我们定义一次对列表进行操作的 build_expr/2:

This defines build_expr/3, which takes two variables or expressions and produces a new expression. This is how we are going to permute the operators. Now we need a way to handle the lists, so let's define build_expr/2 that operates on a list at once:

% base case: we are down to two variables and call build_expr/3
build_expr([X,Y], Expr) :- build_expr(X, Y, Expr).

% inductive case: make the expression on the rest of the list and combine
% with the leading variable here
build_expr([X|Rest], Expr) :-
    build_expr(Rest, Expr0),
    build_expr(X, Expr0, Expr).

让我们获得一些解决方案，以便我们了解它正在做的事情:

Let's get a few solutions so we get the flavor of what it's doing:

3 ?- build_expr([10,10,10,10],X).
X = 10+(10+(10+10)) ;
X = 10*(10+(10+10)) ;
X = 10-(10+(10+10)) ;
X = 10/(10+(10+10)) ;
X = 10+10*(10+10) ;
X = 10*(10*(10+10)) ;
X = 10-10*(10+10) ;
X = 10/(10*(10+10)) ;
X = 10+(10-(10+10)) ;
X = 10*(10-(10+10)) ;
X = 10-(10-(10+10)) ;
X = 10/(10-(10+10)) ;

这对我来说看起来不错.但就像我说的，我只生成右倾树.您将不得不修改或替换 build_expr/2 以生成其他形状，如果它们真的很重要(我不相信它们会这样做).

This looks pretty good to me. But like I said, I'm only generating the right-leaning tree. You will have to modify or replace build_expr/2 to produce the other shapes, if they actually matter (which I'm not convinced they do).

现在让我们通过在评估中捆绑来简化下一步:

Now let's make the next step simpler by bundling in evaluation:

build_eval(L, Value) :- build_expr(L, Expr), Value is Expr.

现在我们应该能够使用 setof/3 找到所有独特的解决方案:

Now we should be able to find all the unique solutions using setof/3:

6 ?- setof(X, build_eval([10,10,10,10],X), Results).
ERROR: Arithmetic: evaluation error: `zero_divisor'
ERROR: In:
ERROR:   [15] _582 is 10/(10* ...)
ERROR:   [14] build_eval([10,10|...],_622) at /Users/dlyons/fourtens.pl:11
ERROR:   [13] '$bags':findall_loop(_664,user:build_eval(...,_682),_668,[]) at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/bags.pl:97
ERROR:   [12] setup_call_catcher_cleanup('$bags':'$new_findall_bag','$bags':findall_loop(_728,...,_732,[]),_710,'$bags':'$destroy_findall_bag') at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/init.pl:443
ERROR:    [8] '$bags':setof(_770,user:build_eval(...,_786),_774) at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/bags.pl:240
ERROR:    [7] <user>
ERROR:
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
ERROR:   [13] '$bags':findall_loop(_664,user:build_eval(...,_682),_668,[]) aabort
% Execution Aborted

哎呀.除以零误差.没问题，让我们抓住它并在这些情况下失败:

Oops. Division by zero error. No problem, let's catch that and fail in those cases instead:

9 ?- setof(X, catch(build_eval([10,10,10,10],X), E, fail), Results), writeln(Results).
[-990,-900,-190,-100,-80,-20,-1,-0.1111111111111111,
 0,0.01,0.05,0.09090909090909091,0.3333333333333333,1.0,1,
 5.0,9.5,9.9,10,10.1,10.5,20.0,20,40,100.0,100,
 120,210,300,1010,1100,2000,10000]

我稍微修改了那里的格式，但我认为这是一个很好的解决方案，但我已经看到一个缺失的解决方案:(10+10)*(10+10)=400.因此，您必须通过 build_expr/2 获得更多创意，以使其生成其他形状的树.

I fiddled with the formatting there a little, but I think that's a pretty good solution, but I can already see one missing solution: (10+10)*(10+10)=400. So you will have to get more creative with build_expr/2 to make it produce other shapes of tree.

我发现 @gusbro 的答案 提供了一种枚举树的方法.我无法让它与我在那里做的递归技巧一起工作(也许其他人会向我展示一个非常简单的技巧)，但我能够根据你的问题调整他的答案，即:

I found an answer by @gusbro that gives a way to enumerate the trees. I wasn't able to get it to work with the recursive trickery I was doing there (maybe someone else will show me a very easy trick) but I was able to adapt his answer to your problem, to wit:

build_tree([I1,I2|Items], Expr) :-
    append([L0|LR], [R0|RR], [I1,I2|Items]),
    build_tree([L0|LR], Left),
    build_tree([R0|RR], Right),
    build_expr(Left, Right, Expr).
build_tree([E], E).

为什么我使用 [L0|LR] 和 [R0|RR] 而不是 LeftList 和 RightList 或者类似的?这就是我将@gusbro 的数字约束转换为列表长度约束并确保我在左右列表中始终至少有一个元素的方式，因此我对 build_tree/2 的递归调用将成功.

Why am I using [L0|LR] and [R0|RR] instead of LeftList and RightList or some such? This is how I'm turning @gusbro's numeric constraints into list length constraints and ensuring that I always have at least one element in both the left and right lists, so my recursive calls to build_tree/2 will succeed.

将 build_expr/3 从上到下简化为单个运算符，您可以看到这会生成您所期望的所有各种风格:

Simplifying build_expr/3 from above down to a single operator you can see this generates all the various flavors you'd expect:

?- build_tree([10,10,10,10],X).
X = 10+(10+(10+10)) ;
X = 10+(10+10+10) ;
X = 10+10+(10+10) ;
X = 10+(10+10)+10 ;
X = 10+10+10+10 ;
false.

将其切换回来，因为我们仍在使用前面示例中的 build_expr/3 函数.我使用这个 build_eval/2 谓词简化了评估:

Switch it back, because we're still using the build_expr/3 function from the earlier example. I have simplified the evaluation somewhat using this build_eval/2 predicate:

build_eval(L, Value) :- 
    build_tree(L, Expr), catch(Value is Expr, _, fail).

这是最终解决方案的样子:

Here's what the final solution looks like:

 ?- setof(X, build_eval([10,10,10,10], X), Res), writeln(Res).
[-990,-900,-190,-100,-99,-90,-80,-20,-19,-10,-9.9,-9.5,-9,
 -8,-1.1111111111111112,-1,-0.9,-0.1111111111111111,
 0,0.01,0.05,0.09090909090909091,0.1111111111111111,
 0.2,0.3333333333333333,0.9,0.9090909090909091,1.0,1,
 1.1,1.1111111111111112,2,3,5.0,5,8,9,9.5,9.9,10,10.1,10.5,11,
 12,19,20.0,20,21,40,80,90,99,100.0,100,101,110,120,190,
 200,210,300,400,900,990,1010,1100,2000,10000]

哇，有很多替代品，确切地说是 68 个！

Wow, quite a few alternatives, 68 to be exact!

这篇关于找出四个 10 的所有表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！