我需要枚举将给定数字 n 划分为一个或多个不同素数之和的所有方法,Prolog 中的 a + b + ... + m
例如:
给定一个整数 n,程序应将适当的总和写入标准输出。例如,如果 n = 20,程序可能会打印
2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13
n可以是任意数字,并且运行时间没有限制。
这是我所拥有的:
partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.
partition(N, [IH|IT], [OH|OT]) :-
N =< 0, fail;
N >= IH, M is N-IH, OH = IH,
partition(M, [IH|IT], OT).
partition(N, [_|IT], Output) :-
N =< 0, fail;
partition(N, IT, Output).
partition(N, Output) :-
generatePrime(N,L),
partition(N, L, Output).
generatePrime(1, []) :- !.
generatePrime(N, X) :-
not(isPrime(N)), !,
Z is N-1,
generatePrime(Z,X).
generatePrime(N, [N | X]) :-
Z is N-1,
generatePrime(Z,X).
isPrime(2).
isPrime(P) :-
P > 2,
isDivisible(P, P-1).
isDivisible(P,X) :-
X > 1,
P mod X =\= 0,
isDivisible(P, X-1).
isDivisible(_, X) :-
1 is X.
目前,我尝试运行这样的东西:
[?- 分区(5, X)。
我得到了重复的[5]和[3,2]提示。当我使用更大的数字(例如 n = 20)时,还有另一种类型的问题,因为我收到重复素数的提示,例如 [2,2,2,2,2,2,2,2,2,2]。
我对序言非常陌生,我确信甚至可能有一种更简单的方法来解决这个问题,但我不确定我在代码中遇到了什么问题。
最佳答案
你还没有...
更大的问题是你调用partition/3
的方式
partition(5, generatePrime(5,Y), X)
partition/3
需要第二项的列表,而不是 generatePrime(5, Y)
。
我建议您添加一个partition/2
,如下所示
partition(N, Output) :-
generatePrime(N, L),
partition(N, L, Output).
并调用此版本的分区
partition(5, X)
还有其他问题,因为此调用返回相同响应的时间更多(在 X
中返回,[5]
四次,[3,2 ]
两次)。
我会看一下是否发现问题
--- 编辑 ---
抱歉,我在理解带有剪切 (!
)、fail
和 or (;
) 的 Prolog 代码时遇到了很大的问题。
我想这是我的问题。
我已按以下方式修改了您的 partition/3
partition(0, _, []).
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
partition(N, [_ | It], O) :-
N > 0,
partition(N, It, O).
这应该避免列表重复
如果您想避免同一列表中出现重复的素数(如果您不接受 [3, 3, 2]
或 [2, 2, 2, 2]
对于 8,因为素数重复),您应该避免在以下对 partition/3
的调用中重复使用 H
(原始代码中的 IH
) >.
我的意思是下面的子句
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
应该变成
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, It, Ot).
关于prolog - Prolog 中的不同素数分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39547491/