如何在Prolog中解决这个算术表达式难题? [英] How to solve this arithmetic expression puzzle in Prolog?
问题描述
我遇到了编程问题( https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions ):
I have a programming problem (https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions):
编写一个程序，该程序输出所有在+或-或不加或不加之间的可能性数字1、2，...，9(按此顺序)，使得结果为始终为100.例如:1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. E.g.: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
我用Python解决了这个问题，得到了 11个答案:
I solved this problem with Python to get 11 answers:
import itertools
for operator in [p for p in itertools.product(['+','-',''], repeat=8)]:
values = zip([str(x) for x in range(1, length+1)], operator) + ['9']
code = ''.join(itertools.chain(*values))
if 100 == eval(code):
print "%s = %d" % (code, eval(code))
这是我的第二个更长的Python代码( https://gist.github.com/prosseek/41201d6508f01cf1643e ):
This is my second Python code that is longer (https://gist.github.com/prosseek/41201d6508f01cf1643e):
[1, 2, 34, -5, 67, -8, 9]
[1, 23, -4, 56, 7, 8, 9]
[12, 3, -4, 5, 67, 8, 9]
[123, -4, -5, -6, -7, 8, -9]
[1, 23, -4, 5, 6, 78, -9]
[12, 3, 4, 5, -6, -7, 89]
[12, -3, -4, 5, -6, 7, 89]
[123, -45, -67, 89]
[123, 45, -67, 8, -9]
[1, 2, 3, -4, 5, 6, 78, 9]
[123, 4, -5, 67, -89]
我还在Prolog中找到了一个建议的解决方案( http://www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/cr2dvsz ):
I also found a proposed solution in Prolog (http://www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/cr2dvsz):
sum([Head|Tail],Signs,Result) :-
sum(Head,Tail,Signs,Result).
sum(X,[],[],X).
sum(First,[Second|Tail],['+'|Signs],Result) :-
Head is First + Second,
sum(Head,Tail,Signs,Result).
sum(First,[Second|Tail],['-'|Signs],Result) :-
Head is First - Second,
sum(Head,Tail,Signs,Result).
sum(First,[Second|[Third|Tail]],['+'|[''|Signs]],Result) :-
C is Second*10+Third,
Head is First + C,
sum(Head,Tail,Signs,Result).
sum(First,[Second|[Third|Tail]],['-'|[''|Signs]],Result) :-
C is Second*10+Third,
Head is First - C,
sum(Head,Tail,Signs,Result).
但是，这仅提供 4个解决方案(并非预期的11个):
However, this gives only 4 solutions (not 11, as expected):
?- sum([1,2,3,4,5,6,7,8,9],X,100).
X = [+, +, -,+, +, +,'',+] ;
X = [+, +,'',-, + '', -,+] ;
X = [+,'', -,+, +, +,'',-] ;
X = [+,'', -,+ '', +, +,+] ;
false.
这是因为''没有出现在第一个列表项中.因此，跳过了 [12，...] 和 [123，...] 的解决方案.
This is because the '' does not appear as the first list item. So the solutions [12,...] and [123,...] are skipped.
我尝试添加 sum(First，[Second | Tail]，[''| Signs]，Result):-Head为First * 10 + Second，sum(Head，Tail，Signs，Result)./code>，但这样做会返回 15个解决方案，而不是11.
I tried adding sum(First,[Second|Tail],[''|Signs],Result) :- Head is First*10 + Second, sum(Head,Tail,Signs,Result).,
but doing so it returns 15 solutions, not 11.
解释说，用错误的解释 1 + 23 到((1)+2)* 10 + 3 .
The explanation says that with the wrong interpretation 1+23 to ((1)+2)*10+3.
?- sum([1,2,3], [+,''], Result).
Result = 33.
然后，如何在Prolog中解决此问题?在此示例中，如何教Prolog 1 + 23 是 24 ?
Then, how to solve this issue in Prolog? How to teach Prolog 1 + 23 is 24 in this example?
推荐答案
Python eval的对应版本可以通过 read_term/3 和 is/2 或
the counterpart to Python eval could be implemented with read_term/3 and is/2, or
give_100(A) :-
generate(1, S),
atomic_list_concat(S, A),
read_term_from_atom(A, T, []),
T =:= 100.
generate(9, [9]).
generate(N, [N|Ns]) :-
N < 9, sep(N, Ns).
sep(N, L) :-
( L = [+|Ns] ; L = [-|Ns] ; L = Ns ),
M is N+1,
generate(M, Ns).
示例查询:
?- give_100(X).
X = '1+2+3-4+5+6+78+9' ;
X = '1+2+34-5+67-8+9' ;
X = '1+23-4+5+6+78-9' ;
X = '1+23-4+56+7+8+9' ;
X = '12+3+4+5-6-7+89' ;
X = '12+3-4+5+67+8+9' ;
X = '12-3-4+5-6+7+89' ;
X = '123+4-5+67-89' ;
X = '123+45-67+8-9' ;
X = '123-4-5-6-7+8-9' ;
X = '123-45-67+89' ;
false.
这篇关于如何在Prolog中解决这个算术表达式难题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
