0

我正在尝试为我的考试学习并遇到以下问题：

“编写一个 Prolog 程序来查找数字 a1,....a14 以便 a1^4+....+a14^4=2013

?-solve([A1,A2,...A13]).

它不仅仅是“我需要有人为我解决的随机家庭作业”。而是为考试而学习的作业

你将如何解决这个问题？

4

4 回答 4

1

如果所有数字都必须是整数，请考虑使用有限域约束。例如，使用 SWI-Prolog：

:- use_module(library(clpfd)).

solution(Vs) :-
        length(Vs, 14),
        Vs ins 0..sup,
        chain(Vs, #=<),
        maplist(pow4, Vs, Ps),
        sum(Ps, #=, 2013).

pow4(X, Y) :- Y #= X^4.

事实证明，该解决方案对于订购是唯一的：

?- solution(Vs), label(Vs).
Vs = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 6] ;
false.
于 2013-10-09T12:00:31.743 回答
0

您的问题在解释方面留下了一些自由度。

假设您可以使用上限限制您的数字集。

那么一个天真的“生成和测试”很容易编写，但效率低下却无可救药。

find_4th_power_sum(CountNumbers, Target, Numbers) :-
    U is floor(Target^(1/4)), % upper bound
    length(Numbers, CountNumbers),
    maplist(gen_4th_power(U), Numbers, Powers),
    sum_list(Powers, Target).

gen_4th_power(U, N, Pow4th) :-
    between(0, U, N),
    Pow4th is N^4.

唉，即使floor(Target^(1/4))只有 6，完整的搜索空间也是

?- X is 7^13.
X = 96889010407.

问题是冗余：解决方案的任何排列都将是解决方案本身。

我会坚持一种不那么 Prolog-ish 的方式：从 Target 中减去 floor(Target^(1/4)) 的循环，并使其成为新目标，直到 Target 为 1。保持数字列表在路上。

当然，这就是我在任何命令式程序中解决问题的方式......

这是代码：

list_4th_power_sum(CountNumbers, Target, [N|Numbers]) :-
    (   Target > 1
    ->  N is floor(Target^(1/4)),
        Target1 is Target-N^4,
        CountNumbers1 is CountNumbers-1,
        list_4th_power_sum(CountNumbers1, Target1, Numbers)
    ;   N = 1,
        findall(0, between(1,CountNumbers,_), Numbers)
    ).

令我惊讶的是，填充为0，即findall(0, between(1,CountNumbers,_), Numbers)结果是无用的......

于 2013-10-09T11:35:58.557 回答
0

我会接受句子并对其进行转换，直到序言出现：

Write a Prolog program that finds numbers a1,....a14 so that a1^4+....+a14^4=2013

=

finds numbers a1,....a14 all >= 0 and < 2013
so that a1^4+....+a14^4=2013

=

between(0, 2013, A1), and so on
 A1^4+....+A14^4 = 2013

像这样的东西。

于 2013-10-09T11:05:59.530 回答
0

一般来说，这种模式是一个“生成和测试”的问题。您需要将其分解为可管理的部分：

  • 生成 N 个数字的列表（例如，在您的情况下 N = 14）
  • 测试这些数字的四次方之和是否与目标 M 相加（在您的情况下，这是 2013 年）
  • 使用回溯找到所有解决方案

对于生成情况，由于您要提高到四次方，因此您知道所有项都是正数，因此生成这样的数字 A 是没有意义的A^4 > 2013。因此，每个As 都将介于 0 和 2013 的四次根的底之间。

对于测试用例，我将其分解为两个步骤：编写一个映射谓词将As 的列表映射到 的列表A^4，然后编写一个谓词来对列表求和并测试它是否是目标值。

于 2013-10-09T11:10:08.943 回答