순환 프롤로그 피보나치 수식이 잘못된 결과를 생성합니다.

Question

왜 이러한 프롤로그 코드 행에서 fib (2,1)이 false를 반환합니까? 우선

fib(1,F) :- 
    F is 1. 
fib(N,F) :- 
    N > 1, 
    fib((N-1),F1), 
    F is F1. 

Answer 1

는 (N-1)는 N이 2 때 1을 전달하는 잘못된 모드입니다. 당신은

fib(N,F) :- 
    N > 1, 
    NM1 is N-1, 
    fib(NM1,F). 

두 번째로 같은 것을 수행해야합니다 모든 N에 대한 1와 F를 통합해야 알고리즘. Fibonacci 공식은 정말 다릅니다. 더

fib(0, 0). 
fib(1, 1). 
fib(N, F) :- 
    N > 1, 
    NM1 is N-1, 
    NM2 is N-2, 
    fib(NM1, FM1), 
    fib(NM2, FM2), 
    F is FM1+FM2. 

셋째

처럼되어 재귀 호출의 지수 폭발의 문제를 피하기 위해, 나는 피보나치

fibH(0, 0, 0). 
fibH(1, 1, 0). 
fibH(N, F, FM1) :- 
    N > 1, 
    NM1 is N-1, 
    fibH(NM1, FM1, FM2), 
    F is FM1+FM2. 
fib(N, F) :- 
    fibH(N, F, _). 

Answer 2

당신의 프롤로그가 테이블 화 큰 정수 경우,

을 계산하기 위해 다른 모드를 제안

:- table fib/2. 

fib(1, 1). 
fib(2, 1). 
fib(N, F) :- 
    N > 2, 
    N1 is N-1, fib(N1, F1), 
    N2 is N-2, fib(N2, F2), 
    F is F1+F2. 

바로 지수 실행 시간이 증가 볼 수있는 테이블/1 지시어를 제거 ...