Обратный факториал в Prolog

Ответ 1

Предикаты Пролога - это отношения, поэтому, как только вы определили факториал, вы также неявно определили инверсию. Тем не менее, регулярная арифметика модифицируется в Prolog, то есть все выражение в (is)/2 или (>)/2 должно быть известно во время выполнения, а если это не так, возникает ошибка. Ограничения преодолевают этот недостаток:

Это определение теперь работает в обоих направлениях.

?- 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.

Подробнее см. руководство.

Ответ 2

Для справки, вот лучшая реализация декларативного предиката factorial, который я мог бы придумать.

Две основные точки отличаются от @false ответа:

• Он использует аргумент аккумулятора, а рекурсивные вызовы увеличивают коэффициент умножения факториала с вместо стандартной рекурсивной реализации, где базовый случай равен 0. Это делает предикат намного быстрее, когда факториал известен, а начальное число - нет.

• Он использует if_/3 и (=)/3 экстенсивно, из модуля reif, чтобы избавиться от ненужных точек выбора когда возможно. Он также использует (#>)/3 и reified (===)/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 ;
...

Ответ 3

простой "низкотехнологичный" способ: перечислять целые числа до

• вы найдете искомый факториал, затем верните номер
• построенный факториал больше цели. Затем вы можете выйти из строя...

Практически вы можете просто добавить 2 аргумента в свою существующую факториальную реализацию, цель и найденную обратную.

Ответ 4

Просто выполните факториал (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).