Calcular una lista de los distintos números impares (si existe), de tal forma que su suma es igual a un número dado
-
21-09-2019 - |
Pregunta
:- 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).
Este es mi código, me parece que no puede obtener el derecho de salida, cualquier código de los críticos?:)
Solución
Puede sugerir esta solución:
:- 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).
Ejemplo:
?- solve(17,L).
L = [17] ;
L = [1, 3, 13] ;
L = [1, 5, 11] ;
L = [1, 7, 9] ;
L = [3, 5, 9] ;
false.
Otros consejos
Aquí mi opinión sobre esta cuestión, realizado por un nonNegInt_oddPosSummands/2
predicado y un predicado list_n_sum/3
auxiliar:
:- 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).
Ahora a algunas consultas!
En primer lugar, "que las listas pueden 19 pueden descomponer en?":
?- 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.
A continuación, una consulta más general de que no pongan fin como el conjunto solución es infinita. "¿Qué N
enteros positivos se pueden descomponer en Zs
si Zs
tiene una longitud de 2?"
?- 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] ...
Por último, la consulta más general. Como la de arriba no termina, ya que el conjunto solución es infinita. Sin embargo, bastante enumera todas las descomposiciones y números enteros positivos correspondiente.
?- 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] ...
Veo que otros han publicado soluciones completas ya.Aún así, el código puede ser hecho al wok con sólo dos ligeras modificaciones:
computeOddList
sólo pruebas si esa lista existe.A saber que lista coincide con las limitaciones, sólo tiene que volver.Por lo tanto:computeOddList(N, L) :- ...
La lista
TempL
en la actualidad puede contener duplicados.Sólo tiene que colocarall_different(TempL)
después deappend
para arreglar eso.
Ahora computeOddList
regresará al menos una lista de los distintos números impares, si es que existe.Todavía, por ejemplo, computeOddList(17, L)
no va a devolver todas las listas.No sé clpFD a mí, así que aparte de lo que sugiere comparar el código Xonix' código Realmente no puedo ayudarte.
:- 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).
Me consiguió un poco resuelto que, sin embargo, no termina correctamente después de que se agote de los casos. Hmm.