PROLOG：总结系列程序

Question

我一直在努力解决我在一本书中发现的这个问题，但我无法在脑海中理解它。问题要求我对这个过程使用 series(N, Total)； 1 + 1/2 + 1/3 + 1/4 + ... + 1/(N-1)。任何帮助我理解这个问题的帮助将不胜感激！非常感谢！

Answer 1

我不明白你遇到了什么问题。

解决这个问题的一个简单方法是定义一个递归谓词。

您可以使用 is/2 and rdiv/2 处理小数。

这将从 1/1 到 1/(B-1):

series(B, B, 0).
series(A, B, Total) :-
    A < B,
    succ(A, A1),
    series(A1, B, Total1),
    Total is rdiv(1, A) + Total1.

阅读方式：

从B到B（排除）的总和（1/i）为0
从 A 到 B 的总和（1/i），其中 A < B，是 1/A 加上 从 A+1 到 B 的总和（递归）。请注意谓词的顺序，它们稍微重新排列，因为 is/2 要求所有参数都是基础的。

示例：我们使用它共同计算总和 1/i for i=1,...,3 = 1/1 + 1/2 + 1/3 = 11/6:

?- series(1,4,X).
X = 11 rdiv 6 .

Answer 2

据我了解，您需要一个计算此函数的谓词：

在过程语言中，您会编写如下迭代解决方案：

static double iterative_harmonic_number( int n )
{
  if ( n < 1 ) throw new ArgumentOutOfRangeException("n");

  double r = 0.0 ;

  while ( n > 0 )
  {
    r += 1.0 / n-- ;
  }

  return r ;
}

或者这个递归解：

static double recursive_harmonic_number( int n )
{
  if ( n < 1 ) throw new ArgumentOutOfRangeException("n");

  double h = (1.0 / n) ;
  if ( n > 1 ) { h += recursive_harmonic_number(n-1) ; } ;

  return h ;

}

对于 n in 1..10，两者都产生相同的结果：

         iterative       recursive
         --------------- ---
f(  1 ): 1                1
f(  2 ): 1.5              1.5
f(  3 ): 1.83333333333333 1.83333333333333
f(  4 ): 2.08333333333333 2.08333333333333
f(  5 ): 2.28333333333333 2.28333333333333
f(  6 ): 2.45             2.45
f(  7 ): 2.59285714285714 2.59285714285714
f(  8 ): 2.71785714285714 2.71785714285714
f(  9 ): 2.82896825396825 2.82896825396825
f( 10 ): 2.92896825396825 2.92896825396825

Prolog 非常适合递归解决方案，让我们来看看。你有

1 个终止递归的特例 (n=1)，并且
一般情况 (n > 1)。

我们可以在 Prolog 中直接表达：

f( 1 , 1.0 ) .     % the terminating special case
f( N , R   ) :-    % the general case:
  N > 1 ,          % - N must be positive (and greater than 1),
  N1 is N-1 ,      % - compute N-1
  f(N1,T) ,        % - recursively evaluate it
  R is T + 1.0 / N % - add that result to the current N's reciprocal
  .                % Easy!

Answer 3

目前给出的答案可以用meta-predicatefoldl/4.

来模仿

喜欢 I will not use floats, but arbitrary-precision rational numbers。与浮点数不同，有理数的加法是可交换和结合的。所以在对有理数求和时，任意顺序的加法都会得到相同的结果。

我建议使用 lambdas together with the two meta-predicates init1/3 and reduce/3，像这样：

seriesR(N,Val) :-
   init1(\I^E^(E is rdiv(1,I)),N-1,Rs),
   reduce(\X^Y^XY^(XY is X+Y),Rs,Val).

示例查询：

?- seriesR(4,Val).
Val = 11 rdiv 6.

为了证明 reduce/3 可以帮助加快求和速度---即使它有一些自己的内部开销---让我们运行 seriesR/2 和 series/3 面对面的一些 BIG N:

?- time((series(10000,_),false)).
% 40,001 inferences, 2.805 CPU in 2.804 seconds (100% CPU, 14259 Lips)
false.

?- time((seriesR(10000,_),false)).
% 180,019 inferences, 0.060 CPU in 0.060 seconds (100% CPU, 3014245 Lips)
false.

编辑

让我们再深入一点！

我们使用的 implementation of lambda expressions 会产生可衡量的性能成本。一旦完成适当的优化，这些成本将来可能会消失。

暂时，让我们量化这些成本...

num_num_sum(X,Y,Sum) :-
   Sum is X+Y.

r_reciprocal(X,Y) :-
   Y is rdiv(1,X).

seriesR2(N,Val) :-
   init1(r_reciprocal,N-1,Rs),
   reduce(num_num_sum,Rs,Val).

运行 seriesR/2 和 seriesR2/2 对决我们得到：

?- time((between(1,10000,_),seriesR(10,V),false)).
% 1,750,001 inferences, 0.389 CPU in 0.389 seconds (100% CPU, 4500790 Lips)
false.

?- time((between(1,10000,_),seriesR2(10,V),false)).
% 820,001 inferences, 0.137 CPU in 0.137 seconds (100% CPU, 5999216 Lips)
false.

在此示例中，使用 lambda 表达式会导致最坏情况下的开销大约为 3 倍。重要吗？也许......但比使用 foldl 而不是 reduce!

少几个数量级

PROLOG：总结系列程序

PROLOG: Summing up the series procedure

prolog

编辑