Сумма подмножества Пролог

Определите подмножество предикатов (L, Sum, Subl), которое принимает список L чисел, число Sum и объединяет SubL с подпоследовательностью L, так что сумма чисел в SubL равна Sum.

Например

   ?- subsetsum([1,2,5,3,2], 5, SubSet);

   SubSet = [1,2,2];
   SubSet = [2,3]; 
   SubSet = [5]; 
   SubSet = [3,2];

No.

у нас есть

 sum([H1 | [H2 | Tail]], S):-
   sum([[H1+H2]|Tail], S):-
 sum([X], X).

и

  subset([],[]).
  subset([H1|T1], [H1|T2]) :-  // heads are the same
    subset(T1, T2).
  subset([_|Rest], X):
    subset(Rest, X).

list sum subset prolog subset-sum
person Musa Jamal    schedule 17.12.2015    source источник
comment
переменные должны быть в верхнем регистре   -  person CapelliC    schedule 17.12.2015
comment
я знаю, у меня проблемы с определением функции susbsetsum, спасибо   -  person Musa Jamal    schedule 17.12.2015
comment
У меня экзамен через 2 часа .. Пожалуйста, помогите мне   -  person Musa Jamal    schedule 17.12.2015
comment
В представленном вами коде есть несколько синтаксических ошибок. Повысьте качество своих вопросов, исправив их перед экзаменом ... это хороший способ закрепить накопленные вами знания! (И это тоже успокаивает!)   -  person repeat    schedule 17.12.2015

Ответы (3)


arrow_upward
2
arrow_downward

Следующие пункты должны делать то, что вам нужно ...

subsetsum(SET, SUM, ANSWER) :-
    % Find a subset
    subset(SET, ANSWER),
    % Check elements of the subset add up to SUM
    sum(ANSWER, SUM).

% sum(LIST, SUM) - sums all numbers in the list
sum([], 0).
sum([X | T], SUM) :-
    sum(T, TAILSUM),
    SUM is TAILSUM + X.

% subset - finds subsets
subset([], []).
subset([E|Tail], [E|NTail]) :-
    subset(Tail, NTail).
subset([_|Tail], NTail) :-
    subset(Tail, NTail).
person BretC    schedule 17.12.2015

arrow_upward
2
arrow_downward

Если все используемые числа являются целыми и ваш процессор Prolog поддерживает clpfd действуйте вот так!

:- use_module(library(clpfd)).

z_z_product(A,B,AB) :-
   AB#=A*B.

subsetsum_(Zs, Sum, Bs, [Sum|Vs]) :-
   same_length(Zs, Bs),
   append(Zs, Bs, Vs),
   Bsins0..1,
   maplist(z_z_product, Zs, Bs, Xs),
   sum(Xs, #=, Sum).

Пример запроса:

?- subsetsum_([1,2,5,3,2], 5, Sel, Vs), labeling([], Vs).
   Sel = [0,0,0,1,1], Vs = [5,1,2,5,3,2,0,0,0,1,1]
;  Sel = [0,0,1,0,0], Vs = [5,1,2,5,3,2,0,0,1,0,0]
;  Sel = [0,1,0,1,0], Vs = [5,1,2,5,3,2,0,1,0,1,0]
;  Sel = [1,1,0,0,1], Vs = [5,1,2,5,3,2,1,1,0,0,1]
;  false.
person repeat    schedule 18.12.2015

arrow_upward
1
arrow_downward

С помощью swi-prolog мы можем использовать предикат библиотеки sum_list/2 вместе с тем subset/2, который у вас уже есть! Обратите внимание, что я дал subset/2 более подходящее имя list_subsequence/2:

list_subsequence([], []).
list_subsequence([X|Xs], [X|Ys]) :-
   list_subsequence(Xs, Ys).
list_subsequence([_|Xs], Ys) :-
   list_subsequence(Xs, Ys).

subsetsum(List, Sum, Sub) :-
   list_subsequence(List, Sub),
   sum_list(Sub, Sum).

Вот пример запроса, который вы дали:

?- subsetsum([1,2,5,3,2], 5, Xs).
   Xs = [1,2,2]
;  Xs = [2,3]
;  Xs = [5]
;  Xs = [3,2]
;  false.

ОК! Давайте запустим еще один запрос с целыми числами и числами с плавающей запятой ... это тоже работает?

?- subsetsum([1,2.1,5,3,2], 5.1, Xs).
   Xs = [1,2.1,2]
;  Xs = [2.1,3]
;  false.

Мне нравится!

person repeat    schedule 17.12.2015