prolog - 反阶乘函数 (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 中的 Inverse factorial 以获得干净的关系解决方案，但如果我们使用它：

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

Answer 2

这个怎么样？我们只是在使用您的谓词 fact/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 是未知数，但 fact/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
    ).