3

我试图找到低于 1000 的所有 3 和 5 的正倍数之和。在添加应该从 5 的倍数之和中删除 3 的倍数的部分后，gprolog 将继续为询问?- sigma(1000,N).

问题显然在于 sigma5，但我不能完全发现它：

sigma(Num, Result) :- sigma3(Num, 3, Result3),
                      sigma5(Num, 5, Result5),
                      Result is Result3 + Result5.

sigma3(Num, A, Result) :- A < Num,
                          Ax is A+3,
                          sigma3(Num, Ax, ResultX),
                          Result is ResultX + A.
sigma3(Num, A, Result) :- A >= Num,
                          Result is 0.

sigma5(Num, A, Result) :- A < Num,
                          mod3 is A mod 3,
                          0 \= mod3,
                          Ax is A+5,
                          sigma5(Num, Ax, ResultX),
                          Result is ResultX + A.
sigma5(Num, A, Result) :- A < Num,
                          mod3 is A mod 3,
                          0 == mod3,
                          Ax is A+5,
                          sigma5(Num, Ax, ResultX),
                          Result is ResultX.
sigma5(Num, A, Result) :- A >= Num,
                          Result is 0.

我的代码有什么问题？

4

4 回答 4

4

由于涉及整数，请考虑使用有限域约束。例如，使用 SWI-Prolog：

?- use_module(library(clpfd)).
true.

?- findall(N, (N mod 3 #= 0 #\/ N mod 5 #= 0, N in 0..999, indomain(N)), Ns),
   sum(Ns, #=, Sum).
Ns = [0, 3, 5, 6, 9, 10, 12, 15, 18|...],
Sum = 233168.
于 2012-02-07T18:33:03.160 回答
2

Prolog 从未因其算术能力而流行。

这是由于需要表示符号处理的“术语构造函数”，而不需要过度评估，因此当需要实际算术时，我们必须为结果显式分配“空间”（变量），而不是“传递”表达式. 这导致了相当冗长和令人不快的代码。

但是使用一些流行的扩展，如 GProlog 和 SWI-Prolog 中可用的 CLP(FD)，我们得到了更好的结果，这是其他语言中不容易获得的：即，在通常的算术运算上封闭整数域。例如，来自 SWI-Prolog CLP(FD) 库的“双向”阶乘

n_factorial(0, 1).
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).

?- n_factorial(X, 3628800).
X = 10 .

无论如何，这是对原始问题的简单解决方案，与您尝试的类似，但使用累加器来计算结果。这个简单的技巧允许编写一个尾递归过程，结果效率更高。

sigma(Num, Result) :-
    sigma(1, Num, 0, Result).

sigma(N, M, Acc, Tot) :-
    (   N < M, !,
        (   (0 is N mod 3 ; 0 is N mod 5)
        ->  Sum is Acc + N
        ;   Sum is Acc
        ),
        N1 is N + 1,
        sigma(N1, M, Sum, Tot)
    ;   Tot is Acc
    ).

测试：

?- sigma(1000, X).
X = 233168 .
于 2012-02-08T08:20:13.797 回答
1 
mod3 is A mod 3,

（以及所有其他出现的 mod3）应该是 Mod3，因为它是一个变量。通过该修复，程序可以正确运行（至少对于 N=1000）

顺便说一句，这是我的解决方案（使用高阶谓词）：

sum(S):-
    findall(X,between(1,999,X),L),       % create a list with all numbers between 1 and 999
    include(div(3),L,L3),                % get the numbers of list L which are divisible by 3
    include(div(5),L,L5),                % get the numbers of list L which are divisible by 5
    append(L3,L5,LF),                    % merge the two lists
    list_to_set(LF,SF),                  % eliminate double elements
    sumlist(SF,S).                       % find the sum of the members of the list

div(N,M):-
    0 is M mod N.

当然效率较低，但是输入太小而无法产生明显的差异

于 2012-02-07T18:19:47.483 回答
0

这一切对我来说似乎很复杂。

sum_of( L , S ) :-
  L > 0 ,
  sum_of( 0 , L , 0 , S )
  .

sum_of( X , X , S , S ) .    % if we hit the upper bound, we're done.
sum_of( X , L , T , S ) :-   % if not, look at it.
  X < L ,                    % - backtracking once we succeeded.
  add_mult35( X , T , T1 ) , % - add any multiple of 3 or 5 to the accumulator
  X1 is X + 1 ,              % - next X
  sum_of( X1 , L , T1 , S )  % - recurse
  . 

add_mult35( X , T , T ) :-  % no-op if X is
  X mod 3 =\= 0 ,           % - not a multiple of 3, and
  X mod 5 =\= 0 ,           % - not a multiple of 5
  !.                        %
add_mult35( X , T , T1 ) :- % otherwise,
  T1 is T + X               % increment the accumulator by X
  .

这可能比现在更简洁。

除了我的代码可能非常糟糕（它实际上比我的 C 解决方案长，这本身就是一项壮举），

ANSI C：

int sum_multiples_of_three_and_five( int lower_bound , int upper_bound )
{
  int sum = 0 ;

  for ( int i = lower_bound ; i <= upper_bound ; ++i )
  {
    if ( 0 == i % 3 || 0 == i % 5 )
    {
      sum += i ;
    }
  }

  return sum ;
}
于 2012-02-08T18:27:58.550 回答