-1

我正在尝试在不使用递归的情况下实现阶乘计算（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，如果我调用谓词追溯来发现 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 的数字的阶乘，则不起作用。有人知道为什么吗？

4

4 回答 4

2

无！我的良心迫使我不问你的问题。

因为你所寻求的是一个禁忌——即使在中——在 Prolog 中更是如此。

在某些情况下肯定会非常有用；我通常将其视为“最后的武器”，而不是“首选武器”。IMO 使用它的可能后果包括：

举个例子？接受@CapelliC和@Boris的答案。引用@Boris：

我正在写这个答案，因为它比@CapelliC的正确答案少了一些不必要的代码。

让我们运行一些查询并对该评估进行测试！

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

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

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

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

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

нет！

请不要误会我的意思！我不想以任何方式、形式或形式放弃@CapelliC和@Boris这两个Prolog 顶级用户SO的工作和努力。

底线：

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

对代码进行严格的测试比测试逻辑上的纯代码要困难得多——相信我，即使这样也可能很多！

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

尽可能保持——不要以任何代价换取它。

于 2015-09-26T12:53:08.993 回答
1

正如@lurker 指出的那样，您将“存储谓词”与“定义谓词”混淆了。您需要 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 中不起作用）。

我认为，Prolog 程序员很早就可以使用断言/撤回来处理“知识库”，而不是用作全局变量。一些 Prolog 为全局变量提供了专门的库谓词，因为它们有合法的用途：例如，参见memoization。

PS：“追溯”是线性系统稳定性理论中使用的术语，我从未见过它用于编程

编辑看看@repeat 报告的错误如何解决可能很有启发性：只需交换统一和剪切。好吧，我们还需要测试 X 是否为正整数。真诚地，我认为这实际上与手头的问题无关。

...
    (  X == N % done ?
    -> !,     % yes, be sure to avoid further backtracking
       Y = F  % unify with the computed factorial
    ;  N1 is N + 1,
...
于 2015-09-26T04:30:49.463 回答
0

假设“追溯”实际上是指“记忆”，解决此问题的一种方法是：

只要你没有找到你需要的阶乘，找到迄今为止最大的一个，计算下一个，冲洗并重复。

我写这个答案是因为它比@CapelliC 的正确答案少了一些不必要的代码。

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

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

:- 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.
于 2015-09-26T07:08:31.270 回答
-1

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

于 2015-09-26T01:41:11.297 回答