0

Q. 给定 Prolog 中的 [1,2,3] 通过反向累加得到 [6,5,3]

我有起始代码：

accumalate([H],[H]).
accumalate([H1 | H2], [Hnew, H2]),
       Hnew is H1 + H2.

……

我正在寻找基本的 Prolog 解决方案。

4

4 回答 4

3

我们不是来帮你做作业的。所以我们能做的最好的就是为您提供一些提示。所以问自己这些问题：

  1. 这里的基本情况是什么（哪些输入是立即输出）？
    • 你有accumulate([N], [N]).，但是空列表呢？
  2. 必须按什么顺序执行添加？
  3. 更具体地说，必须首先添加哪些元素？

除此之外，我可以告诉你，你可以使用三个子句来解决这个问题。不需要其他谓词。祝你好运！

奖励：您可能希望定义递归子句的头部，如下所示：

accumulate([N|T], [N1,N2|T2]).
于 2009-11-17T22:51:58.773 回答
1

这是我的看法：

accumulate([],[]).
accumulate([H|T], [H1|T1]):-
    sum([H|T],H1),
    accumulate(T,T1).
sum([],0).
sum([H|T],Y):-
    sum(T,Y1),
    Y is H + Y1.

如果您愿意，当然可以使用内置sumlist/2代替手工制作。sum/2

于 2009-12-24T23:51:42.033 回答
0

完成基本实现后，尝试在 O(n) 时间内解决此问题。这个想法是从第一个元素开始并继续将其添加到辅助列表中，直到您的原始列表为空。二级列表是您需要的反向列表。

如果您在递归步骤中附加这两个列表，您最终将获得 O(N^2) 复杂度。

于 2009-11-29T09:25:30.960 回答
0 
    ac([], 0, []).

    ac([H|T], ST, [ST|Res]) :-
        ac(T, X, Res),
        ST is H + X.

    accum(List, Res) :-
        ac(List, _, Res).

[trace]  ?- accum([1,2,3], X).
   Call: (6) accum([1, 2, 3], _G376) ? creep
   Call: (7) ac([1, 2, 3], _G458, _G376) ? creep
   Call: (8) ac([2, 3], _G461, _G454) ? creep
   Call: (9) ac([3], _G464, _G457) ? creep
   Call: (10) ac([], _G467, _G460) ? creep
   Exit: (10) ac([], 0, []) ? creep
   Call: (10) _G459 is 3+0 ? creep
   Exit: (10) 3 is 3+0 ? creep
   Exit: (9) ac([3], 3, [3]) ? creep
   Call: (9) _G456 is 2+3 ? creep
   Exit: (9) 5 is 2+3 ? creep
   Exit: (8) ac([2, 3], 5, [5, 3]) ? creep
   Call: (8) _G453 is 1+5 ? creep
   Exit: (8) 6 is 1+5 ? creep
   Exit: (7) ac([1, 2, 3], 6, [6, 5, 3]) ? creep
   Exit: (6) accum([1, 2, 3], [6, 5, 3]) ? creep
X = [6, 5, 3].
于 2012-02-11T21:39:57.487 回答