13

有人可以帮我找到一种在 Prolog 中获得反阶乘的方法...

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

我已经为此工作了很多时间。

我目前有阶乘，但我必须让它可逆。请帮我。

4

4 回答 4

7

Prolog 的谓词是关系，所以一旦你定义了阶乘，你也隐含地定义了逆。然而，正则算术是在 Prolog 中建模的，也就是说，整个表达式在(is)/2或(>)/2必须在运行时知道，如果不是，就会发生错误。约束克服了这个缺点：

:- 使用模块（库（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 ;
错误的。

?- n_factorial(3,F)。
F = 6;
错误的。

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

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

有关更多信息，请参阅手册。

于 2013-09-26T11:28:12.770 回答
3

factorial作为参考，这是我能想到的声明性谓词的最佳实现。

有两个要点与@false 的回答不同：

  • 它使用累加器参数，递归调用增加我们乘以阶乘的因子，而不是基本情况为的标准递归实现0。当阶乘已知且初始数未知时，这使得谓词更快。

  • 它使用if_/3并(=)/3广泛地从模块reif中删除不必要的选择点。它还使用(#>)/3和具体化(===)/6，这是(=)/3我们有两对可用于if -> then部分的情况的变体if_。

factorial/2

factorial(N, F) :-
    factorial(N, 0, 1, F).

factorial(N, I, N0, F) :-
    F #> 0,
    N #>= 0,
    I #>= 0,
    I #=< N,
    N0 #> 0,
    N0 #=< F,
    if_(I #> 2,
        (   F #> N,
            if_(===(N, I, N0, F, T1),
                if_(T1 = true,
                    N0 = F,
                    N = I
                ),
                (   J #= I + 1,
                    N1 #= N0*J,
                    factorial(N, J, N1, F)
                )
            )
        ),
        if_(N = I,
            N0 = F,
            (   J #= I + 1,
                N1 #= N0*J,
                factorial(N, J, N1, F)
            )
        )
    ).

(#>)/3

#>(X, Y, T) :-
    zcompare(C, X, Y),
    greater_true(C, T).

greater_true(>, true).
greater_true(<, false).
greater_true(=, false).

(===)/6

===(X1, Y1, X2, Y2, T1, T) :-
    (   T1 == true -> =(X1, Y1, T)
    ;   T1 == false -> =(X2, Y2, T)    
    ;   X1 == Y1 -> T1 = true, T = true
    ;   X1 \= Y1 -> T1 = true, T = false
    ;   X2 == Y2 -> T1 = false, T = true
    ;   X2 \= Y2 -> T1 = false, T = false
    ;   T1 = true, T = true, X1 = Y1
    ;   T1 = true, T = false, dif(X1, Y1)
    ).

一些查询

?- factorial(N, N).
N = 1 ;
N = 2 ;
false.          % One could probably get rid of the choice point at the cost of readability


?- factorial(N, 1).
N = 0 ;
N = 1 ;
false.          % Same


?- factorial(10, N).
N = 3628800.    % No choice point


?- time(factorial(N, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000)).
% 79,283 inferences, 0.031 CPU in 0.027 seconds (116% CPU, 2541106 Lips)
N = 100.        % No choice point


?- time(factorial(N, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518284253697920827223758251185210916864000000000000000000000000)).
% 78,907 inferences, 0.031 CPU in 0.025 seconds (125% CPU, 2529054 Lips)
false.


?- F #> 10^100, factorial(N, F).
F = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000,
N = 70 ;
F = 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000,
N = 71 ;
F = 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000,
N = 72 ;
...
于 2016-11-18T09:57:44.237 回答
0

一种简单的“低技术”方式：枚举整数直到

  • 您找到所寻求的阶乘，然后“取回”该数字
  • 正在构建的阶乘大于目标。那你可能会失败...

实际上，您只需将 2 个参数添加到现有的阶乘实现、目标和找到的逆。

于 2013-09-26T12:00:52.960 回答
-3

只需实现 factorial(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).
于 2013-09-26T11:12:13.920 回答