不使用递归的阶乘计算

Question

我试图在不使用递归的情况下实现阶乘计算 (n!) 的解决方案，仅使用序言的追溯。例如：

factorial(0, 1).
factorial(1, 1).
factorial(2, 2).

retroaction(X, Y) :-
factorial(K, Y),
not(K = X),
fail.

retroaction(K, Y) :- factorial(K, Y).

对于固定事实 factorial，如果我调用谓词 retroaction 来发现 2 的阶乘，例如，我将收到正确答案：

?- retroaction(2, X).
X = 2.

我尝试实施的解决方案是：

factorial_ret(Number, _) :-
    retractall(factorial(_, _)),
    assertz(factorial(0,1)),
    factorial(X, Y),
    not(X = Number),
    NewNumber is X + 1,
    Factorial is Y * NewNumber,
    retractall(factorial(_, _)),
    assertz(factorial(NewNumber, Factorial)),
    fail.

factorial_ret(Number, Y) :- 
    factorial(Number, Y).

如果我尝试获取大于 1 的数字的阶乘，那是行不通的。有人知道为什么吗？

Answer 1

您的 not 子句中有一个小写的 k。

Answer 2

正如@lurker 所指出的，您将 'storage predicate' 与 'definition predicate' 混淆了。您需要 factorial/2 定义，因此 retractall(factorial(_,_)).

毫无意义

下面，我使用 retract(mem(N, F)) 检索临时值并为最终更新准备数据库。应该总是只有 mem/2.

的一个实例

% replace recursion with a failure driven loop
:- dynamic mem/2.
factorial(X, Y) :-
    assert(mem(0, 1)),
    repeat,
    retract(mem(N, F)),
    (  X == N % done ?
    -> Y = F, % yes, succeed
       !      % but be sure to avoid 'external' backtracking...
    ;  N1 is N + 1,
       F1 is N1 * F,
       assert(mem(N1, F1)),
       fail   % loop: 'goto repeat'
    ).

请注意 repeat,...,fail 之间的分支中的所有内置函数都是不可回溯的（好吧，retract/1 除外）。

另请注意，这样的代码在递归定义中会慢得多（并且在多线程 SWI-Prolog 中不起作用）。

我认为 assert/retract 是根据处理 'knowledge bases' 的需要提供给 Prolog 程序员的，而不是用作全局变量。几个 Prologs 有专门的库谓词用于全局变量，因为它们有合法的用途：例如，参见 memoization.

PS: 'retroactive' 是线性系统稳定性理论中使用的术语，我从未见过它用于编程

edit 看看如何解决@repeat 报告的错误可能具有指导意义：只需交换统一和剪切。那么，我们还需要测试 X 是否为正整数。真诚地，我认为这实际上与手头的问题无关。

...
    (  X == N % done ?
    -> !,     % yes, be sure to avoid further backtracking
       Y = F  % unify with the computed factorial
    ;  N1 is N + 1,
...

Answer 3

假设 "retroaction" 实际上是指 "memoization"，一种解决方法是：

As long as you don't find the factorial you need, find the largest one so far, calculate the next, rinse and repeat.

我写这个答案是因为它比正确的.

少了一些不必要的代码

为此你只需要一个起始事实，即 0 的阶乘：

然后您可以使用 repeat 循环来执行 "as long as"。然后，如果你总是将新的阶乘添加到预先计算的阶乘堆栈的顶部并且你总是只看一次，那么你可以确定你找到了迄今为止最大的阶乘：

:- dynamic factorial/2.
factorial(0, 1).

factorial_memoize(N, F) :-
    repeat,
        (   factorial(N, F0)
        ->  !, F = F0
        ;   once(factorial(N0, F0)),
            succ(N0, N1),
            F1 is N1 * F0,
            asserta(factorial(N1, F1)),
            fail
        ).

程序的运行方式如下：

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(0, 1).

true.

?- factorial_memoize(0, F).
F = 1.

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(0, 1).

true.

?- factorial_memoize(5, F).
F = 120.

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(5, 120).
factorial(4, 24).
factorial(3, 6).
factorial(2, 2).
factorial(1, 1).
factorial(0, 1).

true.

Answer 4

无!良心逼着我un-ask your question.

你寻求的是no-no—even in imperative-programming——在Prolog中更是如此。

prolog-assert 在某些情况下肯定非常有用；我通常将其视为 "weapon of last resort"，而不是 "first weapon of choice"。 IMO 使用它的可能后果包括：

declarative-programming落后了。
logical-purity容易丢失
debugging 变得更难了。
code-complexity上涨。
performance滴.
闻起来像 global-variables。

举个例子？取答案 and 。引用 @Boris:

I am writing this answer because it has a bit less unnecessary code than the otherwise correct answer by @CapelliC.

让我们运行提出一些问题并将评估付诸实践！

?- factorialBoris(0,0).
**LOOPS**

?- factorialBoris(0,2).
**LOOPS**

?- factorialBoris(1,2).
**LOOPS**

?- factorialCapelliC(0,0).
**LOOPS**

?- factorialCapelliC(0,2).
**LOOPS**

нет!

请不要误会我的意思！我不想以任何方式、形式或形式在 SO 上放下 and 、两个 Prolog 顶级用户的工作和努力.

底线：

在 Prolog 中编码时使用 imperative-programming 风格很容易适得其反！

使用 prolog-assert 严格测试代码比测试逻辑纯代码要难得多——甚至也可以很多，相信我！

在不确定的情况下，选择明智的道路：只做正确的事:)

尽可能保留 logical-purity——不要在 return.
中白白换掉它

不使用递归的阶乘计算

Factorial calculation without using recursion

prolog

factorial

prolog-assert