Berechnen einer Liste von unterschiedlichen ungeraden Zahlen (falls vorhanden), so daß ihre Summe gleich einer gegebenen Anzahl

Question

:- use_module(library(clpfd)). % load constraint library

% [constraint] Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number.

odd(Num) :- Num mod 2 #= 1.

sumOfList([],N,N) :- !.
sumOfList([H|T],Counter,N) :-
  NewN #= H + Counter,
  sumOfList(T,NewN,N).

buildOddList(N,InputList,L) :-
  %return list when sum of list is N
  V in 1..N,
  odd(V),
  append(InputList,[V],TempL),
  sumOfList(TempL,0,N)->
    L = TempL;
    buildOddList(N,TempL,L).

computeOddList(N) :-
  buildOddList(N,[],L),
  label(L).

Das ist mein Code, kann ich nicht scheinen, um die richtige Ausgabe, alle Codes Kritiker zu bekommen? :)

Answer 1

Können Sie diese Lösung vorschlagen:

:- use_module(library(clpfd)).

all_odd([]) :-!.
all_odd([H | T]) :-
 H mod 2 #= 1,
 all_odd(T).

solve(N,L) :-
 N2 is floor(sqrt(N)),
 Len in 1..N2,
 label([Len]),

 length(L, Len),

 L ins 1..N,

 all_different(L),
 all_odd(L),

 sum(L,#=,N),

 label(L),

 % only show sorted sets
 sort(L,L).

Beispiel:

?- solve(17,L).
L = [17] ;
L = [1, 3, 13] ;
L = [1, 5, 11] ;
L = [1, 7, 9] ;
L = [3, 5, 9] ;
false.

Answer 2

Hier mein nehmen auf diese Frage durch ein Prädikat nonNegInt_oddPosSummands/2 und einem Hilfs Prädikat list_n_sum/3 realisiert:

:- use_module(library(clpfd)).

list_n_sum([],_,0).
list_n_sum([Z|Zs],N,Sum) :-
    Z #>= 1,
    Z #=< N,
    Z mod 2 #= 1,
    Sum  #=  Z + Sum0,
    Sum0 #>= 0,
    list_n_sum(Zs,N,Sum0).

nonNegInt_oddPosSummands(N,List) :-
    length(_,N),
    list_n_sum(List,N,N),
    chain(List,#<),
    labeling([],List).

Nun zu einigen Abfragen!

Erste "die Listen können 19 in zerlegt werden?":

?- nonNegInt_oddPosSummands(19,Zs).
Zs = [19] ;
Zs = [1, 3, 15] ;
Zs = [1, 5, 13] ;
Zs = [1, 7, 11] ;
Zs = [3, 5, 11] ;
Zs = [3, 7, 9] ;
false.

Als nächstes wird eine allgemeinere Abfrage, die nicht beendet, als die Lösungsmenge unendlich ist. „Welche positiven ganzen Zahlen N kann in Zs zerlegt werden, wenn Zs eine Länge von 2 hat?“

?- Zs=[_,_], nonNegInt_oddPosSummands(N,Zs).
N = 4,  Zs = [1,3] ;
N = 6,  Zs = [1,5] ;
N = 8,  Zs = [1,7] ;
N = 8,  Zs = [3,5] ;
N = 10, Zs = [1,9] ...

Schließlich ist die allgemeinste Abfrage. Wie die oben es nicht beendet, da die Lösungsmenge unendlich ist. Allerdings ist es ziemlich aufzählt alle Zersetzungen und entsprechende positive ganze Zahlen sind.

?- nonNegInt_oddPosSummands(N,Zs).
N = 0,  Zs = []      ;
N = 1,  Zs = [1]     ;
N = 3,  Zs = [3]     ;
N = 4,  Zs = [1,3]   ;
N = 5,  Zs = [5]     ;
N = 6,  Zs = [1,5]   ;
N = 7,  Zs = [7]     ;
N = 8,  Zs = [1,7]   ;
N = 8,  Zs = [3,5]   ;
N = 9,  Zs = [9]     ;
N = 9,  Zs = [1,3,5] ;
N = 10, Zs = [1,9] ...

Answer 3

Ich sehe andere Komplettlösungen bereits gebucht haben. Dennoch können Sie Ihr Code mit nur zwei geringfügigen Änderungen Wok vorgenommen werden:

1. computeOddList nur Tests , ob eine solche Liste existiert. Um zu wissen, die Liste die Einschränkungen passt, schicken Sie es einfach. Also:

   computeOddList(N, L) :-
       ...
   

2. Die Liste TempL derzeit Duplikate enthalten. Nur Platz all_different(TempL) nach append zu beheben, dass.

Jetzt computeOddList kehrt zumindest eine Liste von verschiedenen ungeraden Zahlen, wenn es vorhanden ist. Noch für z.B. computeOddList(17, L) es wird nicht alle Listen zurück. Ich weiß nicht, clpFD mich, so anders als was darauf hindeutet, Sie vergleichen Ihren Code Xonix‘Code ich nicht wirklich kann Ihnen helfen.

Answer 4

:- use_module(library(clpfd)). % load constraint library

% [constraint] Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number.

odd(Num) :- Num mod 2 #= 1.

sumOfList([],N,N) :- !.
sumOfList([H|T],Counter,N) :-
  NewN #= H + Counter,
  sumOfList(T,NewN,N).

oddList([]) :- !.
oddList([H|T]) :-
  odd(H),
  oddList(T).

computeOddList(N,L) :-
  (L = [];L=[_|_]),
  length(L,V),
  V in 1..N,
  L ins 1..N,
  all_different(L),
  oddList(L),
  sumOfList(L,0,N).

Ich schaffte es irgendwie gelöst es, aber es ist nicht richtig, nachdem er von Fällen ausläuft endet. Hmm.