我有两个数字，分别命名为N和K，我想用2的K次幂写N，例如，如果N = 9和K = 4，则N可以是，N = 1 + 2 + 2 + 4（2 ^ 0 + 2 ^ 1 + 2 ^ 1 + 2 ^ 2）。我的程序应该输出类似N=[1,2,2,4]的内容。我已经习惯了C ++，所以我找不到在序言中解决问题的方法，我们将不胜感激！
我以为使用CLP（FD）可能会少一些，但没有骰子。可以简化吗？
所以这是完整的解决方案。
不要以为我尝试过一次，那里有一些迭代和死胡同。
:- use_module(library(debug)).
% ---
% powersum(+N,+Target,?Solution)
% ---
% Entry point. Relate a list "Solution" of "N" integers to the integer
% "Target", which is the sum of 2^Solution[i].
% This works only in the "functional" direction
% "Compute Solution as powersum(N,Target)"
% or the "verification" direction
% "is Solution a solution of powersum(N,Target)"?
%
% An extension of some interest would be to NOT have a fixed "N".
% Let powersum/2 find appropriate N.
%
% The search is subject to exponential slowdown as the list length
% increases, so one gets bogged down quickly.
% ---
powersum(N,Target,Solution) :-
((integer(N),N>0,integer(Target),Target>=1) -> true ; throw("Bad args!")),
length(RS,N), % create a list RN of N fresh variables
MaxPower is floor(log(Target)/log(2)), % that's the largest power we will find in the solution
propose(RS,MaxPower,Target,0), % generate & test a solution into RS
reverse(RS,Solution), % if we are here, we found something! Reverse RS so that it is increasing
my_write(Solution,String,Value), % prettyprinting
format("~s = ~d\n",[String,Value]).
% ---
% propose(ListForSolution,MaxPowerHere,Target,SumSoFar)
% ---
% This is an integrate "generate-and-test". It is integrated
% to "fail fast" during proposal - we don't want to propose a
% complete solution, then compute the value for that solution
% and find out that we overshot the target. If we overshoot, we
% want to find ozut immediately!
%
% So: Propose a new value for the leftmost position L of the
% solution list. We are allowed to propose any integer for L
% from the sequence [MaxPowerHere,...,0]. "Target" is the target
% value we must not overshoot (indeed, we which must meet
% exactly at the end of recursion). "SumSoFar" is the sum of
% powers "to our left" in the solution list, to which we already
% committed.
propose([L|Ls],MaxPowerHere,Target,SumSoFar) :-
assertion(SumSoFar=<Target),
(SumSoFar=Target -> false ; true), % a slight optimization, no solution if we already reached Target!
propose_value(L,MaxPowerHere), % Generate: L is now (backtrackably) some value from [MaxPowerHere,...,0]
NewSum is (SumSoFar + 2**L),
NewSum =< Target, % Test; if this fails, we backtrack to propose_value/2 and will be back with a next L
NewMaxPowerHere = L, % Test passed; the next power in the sequence should be no larger than the current, i.e. L
propose(Ls,NewMaxPowerHere,Target,NewSum). % Recurse over rest-of-list.
propose([],_,Target,Target). % Terminal test: Only succeed if all values set and the Sum is the Target!
% ---
% propose_value(?X,+Max).
% ---
% Give me a new value X between [Max,0].
% Backtracks over monotonically decreasing integers.
% See the test code for examples.
%
% One could also construct a list of integers [Max,...,0], then
% use "member/2" for backtracking. This would "concretize" the predicate's
% behaviour with an explicit list structure.
%
% "between/3" sadly only generates increasing sequences otherwise one
% could use that. Maybe there is a "between/4" taking a step value somewhere?
% ---
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max=X.
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max>0, succ(NewMax,Max),
propose_value(X,NewMax).
% ---
% I like some nice output, so generate a string representing the solution.
% Also, recompute the value to make doubly sure!
% ---
my_write([L|Ls],String,Value) :-
my_write(Ls,StringOnTheRight,ValueOnTheRight),
Value is ValueOnTheRight + 2**L,
with_output_to(string(String),format("2^~d + ~s",[L,StringOnTheRight])).
my_write([L],String,Value) :-
with_output_to(string(String),format("2^~d",[L])),
Value is 2**L.
:- begin_tests(powersum).
% powersum(N,Target,Solution)
test(pv1) :- bagof(X,propose_value(X,3),Bag), Bag = [3,2,1,0].
test(pv2) :- bagof(X,propose_value(X,2),Bag), Bag = [2,1,0].
test(pv2) :- bagof(X,propose_value(X,1),Bag), Bag = [1,0].
test(pv3) :- bagof(X,propose_value(X,0),Bag), Bag = [0].
test(one) :- bagof(S,powersum(1,1,S),Bag), Bag = [[0]].
test(two) :- bagof(S,powersum(3,10,S),Bag), Bag = [[0,0,3],[1,2,2]].
test(three) :- bagof(S,powersum(3,145,S),Bag), Bag = [[0,4,7]].
test(four,fail) :- powersum(3,8457894,_).
test(five) :- bagof(S,powersum(9,8457894,S), Bag), Bag = [[1, 2, 5, 7, 9, 10, 11, 16, 23]]. %% VERY SLOW
:- end_tests(powersum).
rt :- run_tests(powersum).
由于最后一条单元测试行，所以正在运行2分钟的测试...
?- time(rt).
% PL-Unit: powersum ....2^0 = 1
.2^0 + 2^0 + 2^3 = 10
2^1 + 2^2 + 2^2 = 10
.2^0 + 2^4 + 2^7 = 145
..2^1 + 2^2 + 2^5 + 2^7 + 2^9 + 2^10 + 2^11 + 2^16 + 2^23 = 8457894
. done
% All 9 tests passed
% 455,205,628 inferences, 114.614 CPU in 115.470 seconds (99% CPU, 3971641 Lips)
true.
这里是使用CLP（FD）的方案。这里的想法是递归思考并使用“分叉”方法。
:- use_module(library(clpfd)).
% Predicate that succeeds for power of 2
power_of_2(1).
power_of_2(N) :-
N #> 1,
NH #= N // 2,
N #= NH * 2,
power_of_2(NH).
% Predicate that succeeds for a list that is monotonically ascending
ascending([_]).
ascending([X1,X2|Xs]) :-
X1 #=< X2,
ascending([X2|Xs]).
% Predicate that succeeds if Partition is a K-part partition of N
% where the parts are powers of 2
binary_partition(N, K, Partition) :-
binary_partition_(N, K, Partition),
ascending(Partition). % Only allow ascending lists as solutions
binary_partition_(N, 1, [N]) :- % base case
power_of_2(N).
binary_partition_(N, K, P) :-
N #> 1, % constraints on N, K
K #> 1,
length(P, K), % constraint on P
append(LL, LR, P), % conditions on left/right bifurcation
NL #> 0,
NR #> 0,
KL #> 0,
KR #> 0,
NL #=< NR, % don't count symmetrical cases
KL #=< KR,
N #= NL + NR,
K #= KL + KR,
binary_partition_(NL, KL, LL),
binary_partition_(NR, KR, LR).
这将提供正确的结果，但也会产生多余的解决方案：
2 ?- binary_partition(9,4,L).
L = [1, 2, 2, 4] ;
L = [1, 2, 2, 4] ;
false.
作为练习，您可以弄清楚如何对其进行修改，以便仅生成独特的解决方案。 ：）