2

作业是接受两个变量，一个介于 0 和 10,000 之间的数字，以及在 1 和该数字之间有多少个圆素数。

我在通过递归传递变量时遇到了麻烦（我认为回溯就是所谓的。）我得到了正确的数字，我很确定我已经把这个概念记下来了，我遇到的问题是它抛出了一个当我尝试重新分配变量时出错（？！）

这是代码：

circPrimeCompare(Below, NumCirc):-
    RealNum is 0,
    circPrimeCompare(1, Below, RealNum, []),
    print('R: '),
    print(RealNum),
    nl,
    (NumCirc =:= RealNum).

circPrimeCompare(_, 0, _, _).     
circPrimeCompare(N, 1, _, _):- prime(N), print('aaa').
circPrimeCompare(X, Below, RealNum, L):-
    ( prime(X), X<Below ->
        print(X),
        nl,
        numDigits(X, Y),
        rotate(X, Y, N2),
        (   prime(N2) 
            ->  RealNum2 is RealNum + 1 
            ;   RealNum2 is RealNum
            ),
        X2 is X + 1,
        (   not(circPrimeCompare(X2, Below, RealNum2, L)) 
            ->  RealNum = RealNum2, print(RealNum), nl 
            ;   RealNum = RealNum2, print(RealNum), nl
            ),
        print('RealNum2: '),
        print(RealNum),
        nl
    ;
    ( X<Below ->
        X2 is X + 1,
        RealNumPass is RealNum,
        (   not(circPrimeCompare(X2, Below, RealNumPass, L)) 
            ->  RealNum = RealNumPass, print(RealNum), nl 
            ;   RealNum = RealNumPass, print(RealNum), nl
            ),
        print('RealNum: '),
        print(RealNum),
        nl
        )
    ).

这是跟踪：

   Fail: (26) circPrimeCompare(10, 10, 4, []) ? creep
^  Exit: (25) not(user:circPrimeCompare(10, 10, 4, [])) ? creep
   Call: (25) 4=4 ? creep
   Exit: (25) 4=4 ? creep
...
   Exit: (24) circPrimeCompare(9, 10, 4, []) ? creep
^  Fail: (23) not(user:circPrimeCompare(9, 10, 4, [])) ? creep
   Call: (23) 4=4 ? creep
   Exit: (23) 4=4 ? creep
...
   Exit: (22) circPrimeCompare(8, 10, 4, []) ? creep
^  Fail: (21) not(user:circPrimeCompare(8, 10, 4, [])) ? creep
   **Call: (21) 3=4 ? creep
   Fail: (21) 3=4 ? creep**
   Redo: (21) numDigits(7, _G589) ? creep

粗体部分是让我失望的部分。我真的不明白为什么它会这样。是因为变量本质上只是一种用途吗？关于如何解决它的任何想法？

（是的，我意识到这是非常非常糟糕的代码。在这个任务之前我从来没有在 Prolog 中写过任何东西。）

4

3 回答 3

4

您没有以“Prolog”的方式考虑问题。特别是试图“重新分配”一个变量不是 Prolog 的方式。变量在满足目标和子目标的过程中被绑定，而不是重新分配一个值，我们经常安排代码携带一个“累加器”变量，只是在计算的最后阶段将其值传递给另一个“最终”变量.

回溯和递归是不同的东西。回溯发生在目标（或子目标）失败时，Prolog“引擎”试图以不同的方式满足该目标。如果我们用尽了不同的规则等来满足目标，那么它就会失败。（这可能会导致 Prolog 引擎回溯到先前的子目标并尝试以不同的方式满足它。）

递归是当谓词根据自身定义时，即如果调用谓词会导致同一个谓词作为子目标再次被调用。

要在 Prolog 中完成许多任务，我们必须根据递归而不是迭代来考虑它们，这在过程语言中是很自然的。这就是我们求助于“累加器”变量的原因，在不习惯的人看来，这些变量在谓词中似乎是额外的，可能是不必要的参数。

然而，一旦你看到这个想法在行动，你可能会因为能够以新的方式应用这个概念而获得某种程度的满足感。

让我们将给定列表中的数字相加作为模型问题。天真的方法是这样写：

sum(List,Sum).

其中List是一个数字列表，Sum应该是我们的输出，在列表中保存规定的值总和。

基本思想很自然，你考虑列表的Headand Tail，如果列表（还）不是空的，你想“重新分配” Sum = Sum + Head，然后递归处理Tail（直到列表为空并且我们有Sum我们通缉）。

但这在 Prolog 中没有意义，因为您无法Sum以过程语言允许的相同方式更改 的值。这是将累加器参数添加到我们的谓词并执行相同工作的地方，但以 Prolog 喜欢的方式。

sumAux([ ],Sum,Sum).
sumAux([H|T],Accum,Sum) :-
    NewAccum is Accum + H,
    sumAux(T,NewAccum,Sum).

sum(List,Sum) :- sumAux(List,0,Sum).

在这里，我们引入了一个sumAux/3带有额外参数的“辅助”谓词，并且我们sum/2通过将“累加器”中间参数设置为零来定义该谓词，但同时传递List和Sum参数。

稍微思考一下它是如何工作的，你的努力就会得到回报，很快我希望你会以各种新颖的方式应用这个范式（比如计算循环素数）。

于 2013-04-29T16:25:50.637 回答
1

如前所述，一个常见的 prolog 习惯用法是使用以累加器为种子的“辅助”谓词来完成工作。此外，它有助于将问题分解为更小、更简单的部分。通常你会拥有我称之为“公共谓词”的东西，它除了强制约束和调用完成所有工作的“私有”辅助谓词之外没有多大作用。通常，该辅助谓词将与具有不同数量的公共谓词具有相同的名称（foo/3例如，与公共谓词相反foo/2）。像这样的东西：

%
% count the number of circular primes below the specified
% upper limit.
%    
count_circular_primes( Max , Cnt ) :-
  integer(Max) ,
  Max >=     1 ,
  Max =< 10000 ,
  count_circular_primes( Max , 0 , Cnt )
  .

此处的辅助谓词count_circular_primes/3使用作为 0 种子的累加器值。它看起来像：

count_circular_primes( 0 , Cnt , Cnt ) .
count_circular_primes( N , T , Cnt ) :-
  N > 0 ,
  is_circular_prime(N) ,
  T1 is T + 1 ,
  N1 is N - 1 ,
  count_circular_primes(N1,T1,Cnt)
  .

你会注意到这是所有计数发生的地方。真正剩下要做的就是确定一个特定的整数是否是圆素数。简单的！

您还会注意到，Cnt在整个递归操作完成之前，结果变量并没有与任何东西统一。当N达到零时，累加器T与结果统一。

现在框架已经到位，让我们考虑如何确定单个整数是否是圆素数。这应该很容易：

  1. 数是素数吗？
  2. 将其视为循环缓冲区并将数字向左旋转 1 位
  3. 重复直到你回到起点。

这是我将如何进行列表轮换的方法。回溯将产生整个列表旋转集：

rotate(Xs,Ys) :-
  append(A,[B|C],Xs) , % get the prefix (A) , suffix (C) and current item (B) from Xs
  append(C,A,D)      , % append the suffic (C) to the prefix (A) to get the leftmost bit (B)
  append([B],D,Ys)     % append the current item (B) to the leftmost bit (D) to get the rotation
  .

它是这样工作的：append/3可用于为指定列表生成所有可能的前缀/后缀组合。如果我说append(Prefix,Suffix,[1,2,3,4])通过回溯返回的完整解决方案集是

Prefix    Suffix
========= =========
[]        [1,2,3,4]
[1]         [2,3,4]
[1,2]         [3,4]
[1,2,3]         [4]
[1,2,3,4]        []

一旦可以生成旋转，findall/3就可以在给定特定输入的情况下将整个解决方案集作为列表。因此，鉴于上述rotate/2谓词，我可以这样说：

findall( X , rotate( [1,2,3,4] , X ) , Rotations ).

Rotations将与此列表列表统一：

[ [1,2,3,4] , [2,3,4,1] , [3,4,1,2] , [4,1,2,3] ]

一旦你有了一组旋转，你所要做的就是评估它是否代表一个质​​数。您可以通过forall/2以下方式执行此操作：

forall( member(Rotation,Rotations), is_prime(Rotation) )

如果您不允许使用findall/3and forall/2，事情会变得有点棘手，但我认为这应该会让您继续前进。

于 2013-04-29T21:01:26.333 回答
1

“回溯”是概念的名称；这意味着背靠自己，如果事实证明是不幸的，就背弃自己的决定。在 Prolog 程序中，我们有规则，显示必须证明哪些子目标，以便认为主要目标（规则头）被证明。当有多个规则时，我们可以尝试第一个；如果后来证明无法证明，我们回溯到最新的决策点，并尝试证明下一条规则（如果可用）。

展望未来，我们实例化我们的变量，给它们赋值。一旦确定了变量的值，就无法更改它，而我们仍在继续朝着证明我们的目标前进。当我们这么说时X=2，我们承诺做出这个选择。我们现在不能这么说，X=5那时我们会是骗子，我们的“证据”将变得毫无价值。

Prolog 的本质是，当我们继续证明我们的目标，并就什么是什么做出各种决定时，我们将这些值收集到所谓的替代中，即变量与其值之间的映射，这并不自相矛盾；当我们达到最终目标时，这组变量的值就是我们的答案。

但是当我们失败并且必须回溯时，我们到目前为止所做的所有实例化都以相反的顺序撤消。

具体来说，NumCirc =:= RealNum不是作业。这是一个数值比较，可能为真或假。如果它是真的，我们说目标NumCirc =:= RealNum 成功（被证明）。如果它是假的，我们说目标失败，因此我们回溯。

另一个关键概念是统一：当我们说 时X = Y，我们声称它们都是相同的。当然4=4成功了，也3=4失败了。

是的，Prolog 本质上是一种设置一次的语言（没有回溯，它撤消分配，而不是更改它，使变量再次未分配）。

于 2013-04-29T16:04:07.500 回答