프롤로그의 피보나치 - 오류 일 경우

Question

나는 fib (X, Y) 프로그램을 가지고 있습니다. Y가 X 번째 피보나치 수이면 True을 반환하고 그렇지 않으면 False을 반환해야합니다. 내 프로그램은 거짓 인 입력 문을 언제든지 중단합니다.

fib(R,V) :- fib(0,1,R,V). 
fib(X, Y, 0, V) :- Y == V. 
fib(X, Y, R, V) :- Z is X + Y, C is R - 1, fib(Y, Z, C, V). 

fib(0,1) -> True 
fib(1,1) -> True 
fib(2,2) -> True 
fib(3,3) -> True 
fib(4,5) -> True 

fib(3,5) -> Won't finish. 

내가 뭘 잘못 했니? 내 프로그램 쿼리를 실행하려면 https://swish.swi-prolog.org/을 사용하고 있습니다.

Answer 1

여기서 문제는 두 개의 절인 fib(X, Y, 0, V) :-과 fib(X, Y, R, V) :-을 쓰는 것입니다. Prolog는 역 추적을 사용합니다. : 하나의 절이 시도 된 경우 성공 또는 실패 여부와 상관없이 나중에 다음 절을 다시 시도합니다 (이를 변경할 수있는 once/1과 같은 일부 메타 조건어가 있음).

따라서 R이 0 이하인 경우에도 Prolog는 두 번째 절을 시도합니다.

이 문제를 해결하는 빠른 방법이 두 번째 조항에 대한 경비를 사용하는 것입니다 :

은 또한 코드가 당신이 반대의 방법으로 관계를 사용할 수없는 점에서 매우 우아하지

fib(_, Y, 0, V) :- 
    Y == V. 
fib(X, Y, R, V) :- 
    R > 0, 
    Z is X + Y, 
    C is R - 1, 
    fib(Y, Z, C, V).

도 X 번째 요소를 쿼리 할 수 ​​있습니다.

당신이 Y == V를 사용하는 예를 들어

하지만,이 블록의 통일 : 우리가 X 번째 피보나치 수를 알고 싶다면, 우리는 다시 그 결과를 전파 할 수있는 방법을 원한다.

fib(_, V, 0, V). 
fib(X, Y, R, V) :- 
    R > 0, 
    Z is X + Y, 
    C is R - 1, 
    fib(Y, Z, C, V).

을하지만 지금 우리는 여전히 양방향 관계가없는 : 그래서 우리는 대신에 통일을 사용할 수 있습니다 우리가 주어진 값 V의 X를 얻을 수 없습니다. 이것은 더 복잡합니다. 이제

:- use_module(library(clpfd)). 

fib(_, V, 0, V). 
fib(X, Y, R, V) :- 
    R #> 0, 
    V #>= Y, 
    Z is X + Y, 
    C#= R - 1, 
    fib(Y, Z, C, V).

우리는 할 수 있습니다 : 가장 쉬운 방법은 아마 이것에 대한 clpfd을 사용

1. 열거 모든 인덱스와 해당 피보나치 번호 :

   ?- fib(A,B). 
   A = 0, 
   B = 1 ; 
   A = B, B = 2 ; 
   A = B, B = 3 ; 
   A = 4, 
   B = 5 ; 
   A = 5, 
   B = 8 ; 
   A = 6, 
   B = 13 ; 
   A = 7, 
   B = 21 
   ... 
   

2. 는 내가 받기 피보나치 번호 :

   ,363,210

   ?- fib(2,B). 
   B = 2 ; 
   false. 
   
   ?- fib(10,B). 
   B = 89 ; 
   false. 
   

3. 대응 피보나치 수는 일정 값 인 대한 I 얻었다 :

   ?- fib(A,1). 
   A = 0 ; 
   A = 1 ; 
   false. 
   
   ?- fib(A,2). 
   A = 2 ; 
   false. 
   
   ?- fib(A,3). 
   A = 3 ; 
   false. 
   
   ?- fib(A,4). 
   false. 
   
   ?- fib(A,5). 
   A = 4 ; 
   false. 
   

4. 체크를 만약 피보나치 수 번째 주어진 값이다

   ?- fib(4,5). 
   true ; 
   false. 
   
   ?- fib(4,6). 
   false. 
   
   ?- fib(4,10). 
   false. 
   
   ?- fib(5,8). 
   true ; 
   false. 
   

은