Начинающий - добавьте кратные 3 и 5

Question

Я пытаюсь найти сумму всех положительных кратных 3 и 5 ниже 1000. После добавления части, которая должна удалить кратные 3 из суммы кратных 5 , 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. 

в чем проблема с моим кодом?

Answer 1

Пролог никогда не был популярен для его арифметических возможностей.

Это связано с необходимостью представлять «конструкторы терминов» для символической обработки без неоправданной оценки, поэтому, когда требуется действительная арифметика, мы должны явно выделить «пространство» (переменную) для результата, вместо этого «передать» вниз ". Это приводит к довольно подробному и неприятному коду.

Однако, используя некоторые популярные расширения, такие как CLP (FD), доступные в GProlog, а также SWI-Prolog, мы получаем гораздо лучшие результаты, недоступные на других языках: закрытие целочисленного домена по сравнению с обычным арифметические операции. Например, от CLP SWI-Prolog (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 . 

Answer 2

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. 

это менее эффективно, конечно, но вход слишком мал, чтобы сделать заметную разницу

Answer 3

В качестве целых чисел рассмотрим использование finite domain constraints. Например, с помощью 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. 

Answer 4

Все это кажется очень сложным для меня.

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 ; 
}