时间戳

首页 > 解决方案 > 不使用列表的 Prolog 谓词

recursion - 不使用列表的 Prolog 谓词

问题描述

我需要在count(X,Y,D,N)不使用列表的情况下编写序言谓词，该列表应该计算两个整数之间的元素数，包括两个X整数Y。但是，它应该只计算那些可以被 整除的值D。

例如，count(3,6,2,N)应该返回N = 2，因为 4 和 6 可以被 2 整除，但 3 和 5 不能。

标签： recursionprolog

解决方案

递归是你的朋友（就像大多数 Prolog 的情况一样）。

一个辅助谓词接受一个作为累加器的附加参数在这里很有用：

这样的事情应该做你：

count( X, Y, D, N ) :- count( X, Y, D, 0, N ) .

count( X , Y , D , T , N ) :- X =< Y,     % If X <= Y ...
  ( X rem D =:= 0                         % - and X is divisible by D
    -> T1 is T+1                          %   - then increment T
    ;  T1 = T                             %   - otherwise don't
  ),                                      % and
  X1 is X+1,                              % - increment X
  count( X1, Y, D, T1, N ).               % - recurse down
count( X , Y , _ , N , N ) :- X > Y.      % IF X > Y, we're done: unify the accumulator with the result.

以上是尾递归的，并且出于所有意图和目的而优化为迭代。更经典的递归解决方案是这样的：

count( X, Y, _, 0 ) :- X >  Y .
count( X, Y, D, N ) :- X =< Y ,
    X1 is X+1,
    count( X1, Y, D, T ),
    ( 0 =:= X rem D ->  N is T+1 ; N = T )
    .

推荐阅读