我有一个编程问题
(https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions 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。
我用Python解决了这个问题11 个答案:
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 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 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 个):
?- sum([1,2,3,4,5,6,7,8,9],X,100).
X = [+, +, -,+, +, +,'',+] ;
X = [+, +,'',-, + '', -,+] ;
X = [+,'', -,+, +, +,'',-] ;
X = [+,'', -,+ '', +, +,+] ;
false.
这是因为''
不显示为第一个列表项。所以解决方案[12,...]
and [123,...]
被跳过。
我尝试添加sum(First,[Second|Tail],[''|Signs],Result) :- Head is First*10 + Second, sum(Head,Tail,Signs,Result).
,
但这样做会返回15 种解决方案,不是 11。
解释说,错误的解释1+23
to ((1)+2)*10+3
.
?- sum([1,2,3], [+,''], Result).
Result = 33.
那么,在Prolog中如何解决这个问题呢?如何教授 Prolog1 + 23
is 24
在这个例子中?