逆阶乘函数(Prolog)

Question

我必须编写一个Prolog程序来计算机乘乘函数的逆运算，而无需使用除法。我还得到了注释："函数的逆函数不一定是函数"。我把它作为一个正常的阶乘谓词。

fact(0,1).
fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N * F1.

我在其他一些帖子中读到，您应该能够切换参数，但这个版本似乎并非如此。谁能帮我弄清楚为什么？

Answer 1

请参阅 Prolog 中的逆阶乘以获得干净的关系解决方案，但如果我们正在这样做：

inv_fact(RF, N) :-
   (  between(0,RF,N),
      fact(N,F),
      F >= RF
   -> F = RF
   ;  false
   ).
inv_fact(1, 1).

Answer 2

这个怎么样？我们只是在使用谓词事实/2 时生成阶乘，如果我们到达一个匹配的阶乘点，我们就停止，否则我们生成下一个阶乘。

fact(0,1).
fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N * F1.
inv_fact(1,0).
inv_fact(Value,Number) :- inv_fact(Value,1,Number).

inv_fact(Value,Num,Num) :- fact(Num,Value).
inv_fact(Value,Num,Number) :- fact(Num,V), Value < V,!,false.
inv_fact(Value,Num,Number) :- fact(Num,V),
                              not(Value=V),
                              NumNew is Num+1,
                              inv_fact(Value,NumNew,Number).

Answer 3

我认为您需要更改逻辑，反转评估"流程"。N 是未知数，但事实/2 假设是有界的。

如果你使fact/2尾递归，添加一个累加器，你将能够更好地解决这个问题，因为你还可以添加已知的阶乘（比如K）和未知的（比如U），然后测试：

 if F1 equals K (we have found the solution), unify U to N
 if F1 > K, there is no solution... let Prolog fail...

否则，有点作弊...

?- between(1,inf,X), fact(X,F), F >= 120.
X = 5,
F = 120 

编辑当然，该片段不仅是作弊，而且效率极低。

一个有效的，实现我上面给出的提示

factinv(1, 0). % conventional
factinv(K, U) :- factinv(1, K, 1, U).
factinv(C, K, N, U) :-
    F is C * N,
    (   F < K
    ->  M is N+1,
        factinv(F, K, M, U)
    ;   F == K
    ->  N = U
    ).