Сумма первых n чисел в прологе
Здравствуйте, кто-нибудь может помочь мне вычислить сумму первых n чисел. Например, n=4 => sum = 10. Пока я написал это
predicates
sum(integer,integer)
clauses
sum(0,0).
sum(N,R):-
N1=N-1,
sum(N1,R1),
R=R1+N.
Это работает, но мне нужна другая реализация. У меня нет никаких идей, как я могу сделать это иначе. Пожалуйста помоги
5 ответов
Что сказал @mbratch.
То, что вы вычисляете, является треугольным числом. Если ваша домашняя работа посвящена треугольным числам, а не изучению рекурсивного мышления, вы можете просто вычислить ее следующим образом:
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!
Оба из них являются хвостово-рекурсивными, это означает, что компилятор пролога может превратить их в итерацию (подробности в Google "Оптимизация хвостовой рекурсии")
Если вы хотите уничтожить аккумулятор, вам нужно сделать что-то вроде этого:
sum(0,0).
sum(N,R) :-
N > 0 ,
N1 is N-1 ,
sum(N1,R1) ,
R is R1+N
.
Немного проще, но каждая рекурсия использует другой кадр стека: при достаточно большом значении для N выполнение завершится неудачно с переполнением стека.
Поскольку у вас уже есть много советов по поводу вашего кода, позвольте мне добавить фрагмент (немного не по теме).
Считая и, в более общем смысле, агрегируя, это область, в которой Пролог не сияет по сравнению с другими реляционными декларативными языками (читай SQL). Но некоторые библиотеки от конкретного производителя делают это намного приятнее:
?- aggregate(sum(N),between(1,4,N),S).
S = 10.
Это "сердце" вашей программы:
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 всегда потерпит неудачу
Числовое присвоение арифметического выражения выполняется в Прологе с помощью 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 переменные в выражении создаются.
РЕДАКТИРОВАТЬ
Я понимаю от Сергея Дымченко, что Turbo Prolog, в отличие от GNU или SWI, оценивает выражения для =/2, Итак = будет работать в данной проблеме. Однако ошибка, связанная с созданием экземпляра (или "свободной переменной"), все еще вызвана той же проблемой, о которой я упоминал выше.
sum(N, N, N).
sum(M, N, S):-
N>M,
X is M+1,
sum(X, N, T),
S is M+T.
?- sum(1,5,N).
N = 15 .