如何在Prolog中解決這個算術表達式難題？

我有一個規劃問題（https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions）：如何在Prolog中解決這個算術表達式難題？

編寫一個程序，輸出所有可能放+或 - 或之間沒有任何的數字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）：

[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]

我還發現了一個建議的解決方案在序言（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解決方案（不是如預期的那樣）：

?- sum([1,2,3,4,5,6,7,8,9],X,100). 
X = [+, +, -,+, +, +,'',+] ; 
X = [+, +,'',-, + '', -,+] ; 
X = [+,'', -,+, +, +,'',-] ; 
X = [+,'', -,+ '', +, +,+] ; 
false.

這是因爲''未顯示爲第一個列表項目。因此跳過解決方案[12,...]和[123,...]。

我嘗試添加sum(First,[Second|Tail],[''|Signs],Result) :- Head is First*10 + Second, sum(Head,Tail,Signs,Result).，但這樣做將返回15解決方案，而不是11

的解釋是，與錯誤的解釋1+23到((1)+2)*10+3。

?- sum([1,2,3], [+,''], Result). 
Result = 33.

那麼，如何在Prolog中解決這個問題呢？在這個例子中如何教Prolog 1 + 23是24？

來源

2015-05-08 prosseek

對方到Python的eval可以用read_term/3和is/2，或

實現

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.

來源

2015-05-09 06:28:15 CapelliC

完全一樣CapelliC的解決方案，但與SWI-Prolog的和模塊的工作原理lambda：

:- use_module(library(lambda)). 

sum_100(Atom) :- 
    L = [1,2,3,4,5,6,7,8,9], 
    O = [_A,_B,_C,_D,_E,_F,_G,_H,' '], 
    maplist(\X^member(X, [+,-,' ']), O), 
    foldl(\X^Y^Z^T^(Y = ' ' 
        -> append(Z,[X], T) 
        ; append(Z,[X,Y], T)), L, O, [], Expr), 
    atomic_list_concat(Expr, Atom), 
    term_to_atom(Term, Atom), 
    Term =:= 100.

樣品查詢：

?- sum_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.

來源

2015-05-09 12:33:10 joel76

使用dcg，我們首先定義nonterminalsep//0：

sep --> "+" | "-" | "".

然後，我們運行下面的查詢（使用phrase/2，sep//0，read_from_codes/2和(=:=)/2）：

?- set_prolog_flag(double_quotes,chars). 
true. 

?- phrase(("1",sep,"2",sep,"3",sep,"4",sep,"5",sep,"6",sep,"7",sep,"8",sep,"9"),Cs), 
    read_from_codes(Cs,Expr), 
    Expr =:= 100. 
    Cs = [1,+,2,+,3,-,4,+,5,+,6,+,7,8,+,9], Expr = 1+2+3-4+5+6+78+9 
; Cs = [1,+,2,+,3,4,-,5,+,6,7,-,8,+,9], Expr = 1+2+34-5+67-8+9 
; Cs = [1,+,2,3,-,4,+,5,+,6,+,7,8,-,9], Expr = 1+23-4+5+6+78-9 
; Cs = [1,+,2,3,-,4,+,5,6,+,7,+,8,+,9], Expr = 1+23-4+56+7+8+9 
; Cs = [1,2,+,3,+,4,+,5,-,6,-,7,+,8,9], Expr = 12+3+4+5-6-7+89 
; Cs = [1,2,+,3,-,4,+,5,+,6,7,+,8,+,9], Expr = 12+3-4+5+67+8+9 
; Cs = [1,2,-,3,-,4,+,5,-,6,+,7,+,8,9], Expr = 12-3-4+5-6+7+89 
; Cs = [1,2,3,+,4,-,5,+,6,7,-,8,9],  Expr = 123+4-5+67-89 
; Cs = [1,2,3,+,4,5,-,6,7,+,8,-,9],  Expr = 123+45-67+8-9 
; Cs = [1,2,3,-,4,-,5,-,6,-,7,+,8,-,9], Expr = 123-4-5-6-7+8-9 
; Cs = [1,2,3,-,4,5,-,6,7,+,8,9],   Expr = 123-45-67+89 
; false.

來源

2015-08-14 10:30:47 repeat

使用' ： - set_prolog_flag（double_quotes，chars）.'使答案更具可讀性。 – false

@false。謝謝！現在好多了。 – repeat

如何在Prolog中解決這個算術表達式難題？

回答

相關問題