Сумма первых n чисел в прологе

Question

Здравствуйте, кто-нибудь может помочь мне вычислить сумму первых n чисел. Например п = 4 => сумма = 10. До сих пор я писал

predicates 
    sum(integer,integer) 
clauses 

    sum(0,0). 
    sum(N,R):- 
     N1=N-1, 
     sum(N1,R1), 
     R=R1+N. 

Это один работает, но мне нужно другой вариант осуществления. У меня нет никаких идей, как я мог бы это сделать. Пожалуйста, помогите

Answer 1

Это «сердце» вашей программы:

sum(N,R):- 
    R=R+N, 
    N=N-1, 
    sum(N,R). 

=/2 сказуемое (обратите внимание на /2 означает, что она принимает 2 аргумента) является конкретизации предикат, а не назначение, или логический равен , Он пытается объединить свои аргументы, чтобы сделать их одинаковыми. Так что если N ничего, кроме 0, то R=R+N всегда будет терпеть неудачу, потому что R никогда не может быть таким же, как R+N. Аналогично для N=N-1: он всегда будет терпеть неудачу, потому что N и N-1 никогда не могут быть одинаковыми.

В случае =/2 (унификация), выражения не оценены. Это просто условия. Так, если Y = 1, то X = Y + 1 объединяет X с 1+1 как термин (эквивалентно написанный +(1,1)).

Из-за вышеуказанных проблем sum всегда будет терпеть неудачу.

Численное назначение арифметического выражения выполняется в Prolog с предикатом is/2. Как это:

X is Y + 1. 

Этот оператор объединяет значение X, чтобы быть таким же, как значение вычисленного выражения Y+1. В этом случае вы также не можете иметь X is X+1 по той же причине, что указаны выше: X не может быть таким же, как X+1, и Prolog не разрешает «повторное создание» переменной внутри предложения. Поэтому вам понадобится что-то вроде: X1 is X + 1. Также обратите внимание, что для работы is/2 все в выражении справа должно быть предварительно создано. Если какие-либо переменные в выражении справа не имеют значения, вы получите сообщение об ошибке или, в случае Turbo Prolog, Свободная переменная в выражении ....

Так что вам нужно использовать разные переменные для результатов выражения и организовать код так, чтобы при использовании is/2 переменные в выражении были созданы.

---

EDIT

Я понимаю, от Сергея Дымченко, что Турбо Пролог, в отличие от GNU или SWI, вычисляет выражения для =/2. Таким образом, = будет работать в данной задаче. Однако ошибка в отношении создания экземпляра (или «свободной переменной») по-прежнему вызвана той же проблемой, о которой я упоминал выше.

Answer 2

Что сказал @mbratch.

Что вы делаете, это triangular number. Если домашнее задание о треугольных чисел, а не об обучении рекурсивного мышления, вы можете просто вычислить его таким образом:

triangular_number(N,R) :- R is N * (N+1)/2 . 

Если, как это, скорее всего, вы изучаете рекурсивную мысль, попробуйте это:

sum(N,R) :- % to compute the triangular number n, 
    sum(N,1,0,R) % - invoke the worker predicate with its counter and accumulator properly seeded 
    . 

sum(0,_,R,R).  % when the count gets decremented to zero, we're done. Unify the accumulator with the result. 
sum(C,X,T,R) :- % otherwise, 
    C > 0 ,   % - assuming the count is greater than zero 
    T1 is T+X ,  % - increment the accumulator 
    X1 is X+1 ,  % - increment the current number 
    C1 is C-1 ,  % - decrement the count 
    sum(C1,X1,T1,R) % - recurse down 
    .    % Easy! 

Отредактировано добавить:

Или, если вы предпочитаете Отсчет подход:

sum(N,R) :- sum(N,0,R). 

sum(0,R,R).  % when the count gets decremented to zero, we're done. Unify the accumulator with the result. 
sum(N,T,R) :-  % otherwise, 
    N > 0 ,   % - assuming the count is greater than zero 
    T1 is T+N ,  % - increment the accumulator 
    N1 is N-1 ,  % - decrement the count 
    sum(N1,T1,R) % - recurse down 
    .    % Easy! 

Оба они: tail-recursive, что означает, что компилятор пролога может превратить их в итерацию (оптимизация хвостовой рекурсии Google).

Если вы хотите избавиться от аккумулятора, что вам нужно сделать что-то вроде этого:

sum(0,0). 
sum(N,R) :- 
    N > 0 , 
    N1 is N-1 , 
    sum(N1,R1) , 
    R is R1+N 
    . 

Немного проще, но каждый рекурсии потребляет еще один кадр стека: при достаточно большое значение для N, выполнение будет сбой при переполнении стека.

Answer 3

sum(N, Sum) :- 
    Sum is (N + 1) * N/2 . 

Answer 4

Поскольку у вас уже есть много советов о вашем коде, позвольте мне добавить фрагмент (немного не по теме).

Подсчет и, в более общем плане, агрегация, это область, где Пролог не светит по сравнению с другими реляционными, декларативными языками (читать SQL). Но некоторым конкретным поставщикам library становится намного приятнее:

?- aggregate(sum(N),between(1,4,N),S). 
S = 10.