Prolog中的反因子

Question

有人可以帮助我找到一种方法来获得Prolog中的反因子...

例如inverse_factorial(6,X) ===> X = 3.

我一直在努力工作.

我目前有阶乘,但我必须让它可逆.请帮我.

Answer 1

Prolog的谓词是关系,所以一旦你定义了阶乘,你也隐含地定义了逆.但是,常规算术在Prolog中进行模式化,即在运行时(is)/2或(>)/2必须在运行时知道整个表达式,如果不是,则会发生错误.限制克服了这个缺点:

:- use_module(library(clpfd)).

n_factorial(0, 1).
n_factorial(N, F) :-
   N #> 0, N1 #= N - 1, F #= N * F1,
   n_factorial(N1, F1).

这个定义现在适用于两个方向.

?- n_factorial(N,6).
N = 3 ;
false.

?- n_factorial(3,F).
F = 6 ;
false.

由于SICStus 4.3.4和SWI 7.1.25也终止了以下内容:

?- n_factorial(N,N).
   N = 1
;  N = 2
;  false.

有关更多信息,请参阅手册

这个定义在两个方向都有效,并且是实现它的最自然和可读的方式,但是在搜索反因子时它非常慢,例如`n_factorial(Y,1000000000)`需要大约20秒才能回答`false `在我的机器上. (2认同)

Answer 2

只需实现阶乘（X，XFact），然后交换参数

factorial(X, XFact) :- f(X, 1, 1, XFact).

f(N, N, F, F) :- !.
f(N, N0, F0, F) :- succ(N0, N1), F1 is F0 * N1, f(N, N1, F1, F).