Prolog 中的算术，使用 2 的幂表示一个数字 [英] Arithmetics in Prolog, represent a number using powers of 2

问题描述

我有两个数字，让我们把它们命名为N和K，我想用KN> 2 的幂.

I have two numbers, let's name them N and K, and I want to write N using K powers of 2.

例如如果 N = 9 和 K = 4，则 N 可以是 N = 1 + 2 + 2 +4 (2^0 + 2^1 + 2^1 + 2^2).

For example if N = 9 and K = 4, then N could be N = 1 + 2 + 2 + 4 (2^0 + 2^1 + 2^1 + 2^2).

我的程序应该输出类似 N = [1,2,2,4] 的内容.

My program should output something like N = [1,2,2,4].

我习惯了 C++.我在 Prolog 中找不到解决这个问题的方法.任何帮助将不胜感激！

I am used to C++. I can't find a way to solve this problem in Prolog. Any help will be appreciated!

推荐答案

这是一个使用 CLP(FD) 的方案.一般来说，在 Prolog 的整数域中进行推理时，CLP(FD) 是一个很好的方法.这个特定问题的想法是递归思考(就像在许多 Prolog 问题中一样)并使用分叉"方法.

Here's a scheme that uses CLP(FD). In general, when reasoning in the domain of integers in Prolog, CLP(FD) is a good way to go. The idea for this particular problem is to think recursively (as in many Prolog problems) and use a "bifurcation" approach.

正如大卫在他的回答中所说的，像这样的问题的解决方案不会在第一次尝试时就流出.有初步的概念、试验实施、测试、观察和修改来提出问题的解决方案.即使是这个也可以使用更多的工作.:)

As David said in his answer, solutions to problems like this don't just flow out on the first attempt. There are preliminary notions, trial implementations, tests, observations, and revisions that go into coming up with the solution to a problem. Even this one could use more work. :)

:- 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).

这将提供正确的结果，但也会产生多余的解决方案:

This will provide correct results, but it also generates redundant solutions:

2 ?- binary_partition(9,4,L).
L = [1, 2, 2, 4] ;
L = [1, 2, 2, 4] ;
false.

作为练习，您可以弄清楚如何修改它，使其只生成唯一的解决方案.:)

As an exercise, you can figure out how to modify it so it only generates unique solutions. :)

这篇关于Prolog 中的算术，使用 2 的幂表示一个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！