0

于是就有了一个谜题：

这个等式是不完整的：1 2 3 4 5 6 7 8 9 = 100。使其准确的一种方法是添加七个加号和减号，如下所示：1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100。你怎么能只用 3 个加号或减号呢？

我对 Prolog 很陌生，解决了这个难题，但我想知道如何优化它

makeInt(S,F,FinInt):-
    getInt(S,F,0,FinInt).

getInt(Start, Finish, Acc, FinInt):-
    0 =< Finish - Start,
    NewAcc is Acc*10 + Start,
    NewStart is Start +1,
    getInt(NewStart, Finish, NewAcc, FinInt).
getInt(Start, Finish, A, A):- 
    0 > Finish - Start.

itCounts(X,Y,Z,Q):-
    member(XLastDigit,[1,2,3,4,5,6]),
    FromY is XLastDigit+1,
    numlist(FromY, 7, ListYLastDigit),
    member(YLastDigit, ListYLastDigit),
    FromZ is YLastDigit+1,
    numlist(FromZ, 8, ListZLastDigit),
    member(ZLastDigit,ListZLastDigit),
    FromQ is ZLastDigit+1, 
    member(YSign,[-1,1]),
    member(ZSign,[-1,1]),
    member(QSign,[-1,1]),
    0 is XLastDigit + YSign*YLastDigit + ZSign*ZLastDigit + QSign*9,
    makeInt(1, XLastDigit, FirstNumber),
    makeInt(FromY, YLastDigit, SecondNumber),
    makeInt(FromZ, ZLastDigit, ThirdNumber),
    makeInt(FromQ, 9, FourthNumber),
    X is FirstNumber,
    Y is YSign*SecondNumber,
    Z is ZSign*ThirdNumber,
    Q is QSign*FourthNumber,
    100 =:= X + Y + Z + Q.
4

2 回答 2

1

不确定这是否代表优化。代码更短：

sum_123456789_eq_100_with_3_sum_or_sub(L) :-
    append([G1,G2,G3,G4], [0'1,0'2,0'3,0'4,0'5,0'6,0'7,0'8,0'9]),
    maplist([X]>>(length(X,N), N>0), [G1,G2,G3,G4]),
    maplist([G,F]>>(member(Op, [0'+,0'-]),F=[Op|G]), [G2,G3,G4], [F2,F3,F4]),
    append([G1,F2,F3,F4], L),
    read_term_from_codes(L, T, []),
    100 is T.
于 2017-04-07T13:56:48.423 回答
0

我花了一段时间，但我知道你的代码在做什么。是这样的：

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc.
  generate X as a list of digits
  do the same for Y, Z, and Q
  pick the signs for Y, Z, and Q
  convert all those lists of digits into numbers
  verify that, with the signs, they add to 100.

这里的低效率是测试都是在最后一刻完成的。如果您在选择一个数字时可以立即抛出一些可能的解决方案，即提前测试，您可以提高效率。

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc.
  generate X as a list of digits, and convert it to a number
  if it's so big or small the rest can't possibly bring the sum back to 100, fail
  generate Y as a list of digits, convert to number, and pick it sign
  if it's so big or so small the rest can't possibly bring the sum to 100, fail
  do the same for Z
  do the same for Q

即使我搜索所有可能的解决方案，您的功能已经运行得非常快。它只选择 6 个 X；42 岁；224个Z；和 15 个 Q。我认为优化不值得您花时间。

但如果你真的想：我通过在选择 X 后立即放置一个测试函数来测试它。它将 6 个 X 减少到 3 个（都是在找到解决方案之前）；42岁到30岁；224 Z 到 184；和 15 Q 到 11。我相信我们可以通过在选择 Y 后立即测试来进一步减少它，看看 X YSign Y 是否已经如此大或小，无法解决。

在计算密集度更高的 PROLOG 程序中，将部分“测试”放在“生成和测试”算法的早期会有很大帮助。

于 2017-04-09T20:18:36.093 回答