프롤로그, 삼각 숫자, 누적 기 및 꼬리 재귀

Question

나는 두 부분으로 구성된 숙제를하고 있습니다. 첫 번째는 특정 쌍 X, Y가 http://en.wikipedia.org/wiki/Triangular_number에 속하는지 확인하는 프롤로그 프로그램을 작성하는 것입니다. 예 : (2, 3) = true; (4, 10) = true et cetera.

제 용액 '통상'재귀를 사용하며,이 같은이 해결했습니다

triangle(0, 0). 
triangle(X, Y) :- X > 0, Y > 0, A is X - 1, B is Y - X, triangle(A, B). 

번째 부분은 삼각형/3 술어를 사용하여,이 사용 꼬리 재귀/누산기를 해결하는 것이다. 비록 내가 사용법이 아주 명확한 다른 어시 젼트에서 어큐뮬레이터를 사용해 봤지만 어큐뮬레이터를 사용하는 방법에 대한 일반적인 생각이 있었기 때문에 이것을 사용하는 방법에 관해서는 아주 의아해했습니다.

그래서 알고리즘을 찾고있는 것이 아니라 훨씬 더 나 자신을 해결할 것이지만이 맥락에서 누산기를 적용하는 방법에 대한 실질적인 조언을 더 많이합니다.

Answer 1

시작은 항상 동일합니다. 즉, 처음 세 줄은 기본적으로 각 꼬리 재귀 조건 자 (목록 조건 자에 대해 0 대신 [])로 작성하는 내용입니다.

거기에서 당신은 많은 변화없이 갈 수 있습니다 : 자신의 조건은 기본적으로 재귀 이미 꼬리 동안 때문에 (

64 ?- time(triangle(1000000,500000500000)). 
% 4,000,000 inferences, 0.50 CPU in 0.52 seconds (96% CPU, 8012769 Lips) 
true. 

65 ?- time(triangle_t(1000000,500000500000)). 
% 3,000,001 inferences, 0.41 CPU in 0.44 seconds (92% CPU, 7396405 Lips) 
true. 

그래서 다음은

triangle_t(X, Y) :- triangle_t(X, 0, Y). 
triangle_t(0, Y, Y). 
triangle_t(X, Acc, Y) :- 
      X > 0, 
      A is X - 1, 
      AccX is Acc + X, 
      triangle_t(A, AccX, Y). 

큰 X에 대한 통계입니다 재귀 호출이 마지막으로 수행해야 함) accumulator가있는 버전은 Y > 0에 대한 확인이 필요하지 않으므로 시간이 절약됩니다. 당신이 triangle_t 조건에서이 라인을 소개하면, 그들은 정확히 동일한 런타임 특성을 다시 가지고

67 ?- time(triangle_t(1000000,500000500000)). 
% 4,000,001 inferences, 0.53 CPU in 0.53 seconds (100% CPU, 7541432 Lips) 
true. 

은 또한 당신이 지금 n 번째 삼각수를 생성하는 술어를 사용할 수 있습니다.