English 中文(简体)
Given [1,2,3] in prolog get back [6,5,3] by reverse accumalation
原标题:
  • 时间:2009-11-17 22:38:33
  •  标签:
  • prolog

Q. Given [1,2,3] in Prolog get back [6,5,3] by reverse accumulation

I have the start code:

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

....

I am looking for basic Prolog solution.

最佳回答

We are not here to do you homework for you. So the best we can do is provide you with some tips. So ask yourself these questions:

  1. What are the base cases here (for which inputs is the output immediate)?
    • You have accumulate([N], [N])., but what about empty lists?
  2. In what order must the additions be performed?
  3. More specifically, which elements must be added first?

Other than that, I can tell you that you can solve this using three clauses. No other predicates required. Good luck!

Bonus: you may want to define the head of the recursive clause as follows:

accumulate([N|T], [N1,N2|T2]).
问题回答

Here is my take:

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.

You can of course use a built-in sumlist/2 in place of the hand-crafted sum/2 if you prefer that.

Once you are done with the basic implementation , Try solving this problem in O(n) time. The idea is to start from the first element and keep on adding it to a secondary list till your original list is empty. The secondary list is the reverse list which you need.

If you append the two lists in your recursive step, you will end up having a O(N^2) complexity.

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




相关问题
Prolog : Learning by example

I am trying to learn a little bit about swi-prolog (beyond the basic, useless programs). Can anyone explain (perhaps in pseudocode) what this sudoku solver and the related functions are doing? If ...

Working with lists in Prolog

First off let me state that this is part of a class exercise given as homework. But, the entire assignment is much more involved than the subject of this question. So.. I am searching through two ...

SWI-Prolog conditional statements

I m trying to write a function that will test to see if the word hello is contained in a list. If it is contained, i don t want it to say "true", i want it to say : "yes, the word hello is contained ...

prolog cut off in method

I have a question I would like to ask you something about a code snippet: insert_pq(State, [], [State]) :- !. insert_pq(State, [H|Tail], [State, H|Tail]) :- precedes(State, H). insert_pq(State, [...

Max out of values defined by prolog clauses

I know how to iterate over lists in Prolog to find the maximum, but what if each thing is a separate clause? For example if I had a bunch of felines and their ages, how would I find the oldest kitty? ...

热门标签