피보나치 숫자가 음수

동적 프로그래밍 기술을 사용하여 다음 코드를 작성했지만 피보나치 숫자 220을 실행할 때 음수가 표시됩니다.이 프로그램에서 실수가 있습니까?피보나치 숫자가 음수

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 

public class Fibonaci { 

    public static void main(String[] args) { 
     System.out.println(" number "); 
     long startTime = System.currentTimeMillis(); 
     HashMap<Integer, Integer> memoized = new HashMap<Integer, Integer>(); 
     int fib = fibonanci(220, memoized); 
     System.out.println(" Total Time " 
       + (System.currentTimeMillis() - startTime)); 

    } 

    private static int fibonanci(int n, HashMap<Integer, Integer> memoized) { 
     System.out.println(" n " + n); 
     if (memoized.containsKey(n)) { 
      return memoized.get(n); 
     } 

     if (n <= 0) { 
      return 0; 
     } 
     if (n <= 2) { 
      return 1; 
     } else { 
      int febonani = fibonanci(n - 1, memoized) 
        + fibonanci(n - 2, memoized); 
      System.out.println(" febonani " + febonani); 
      if (!memoized.containsKey(n)) { 
       memoized.put(n, febonani); 
      } 
      return febonani; 
     } 
    } 


}

출처

2014-07-21 sumedha

정말 'HashMap'의 오버 헤드가 아닌'List' (예 :'ArrayList')를 사용하는 것이 좋습니다. –

'''if (! memoized.containsKey (n))'''줄은 불필요한 것으로 보인다. n이 함수의 시작 부분에 memoized 된 데이터 구조에 없다면, 그 시점에서 그 안에 존재하지 않을 것이다. (구조를 변경하는 스레드가 여러 개있는 경우는 제외). –

사용 BigInteger 대신 int/Integer는 Ivaylo 지적 (자바의 int 및 Integer 이상 2^63 비트의 부호없는 정수를 나타낼 수 없습니다). BigInteger supports arbitrary precision (JVM에 사용 가능한 메모리 양에 의해서만 제한됨).

private static BigInteger fib(int n, HashMap<Integer, BigInteger> memoized) { 
    System.out.println(" n = " + n); 
    if (memoized.containsKey(n)) { 
     return memoized.get(n); 
    } else if (n <= 0) { 
     return BigInteger.ZERO; 
    } else if (n <= 2) { 
     return BigInteger.ONE; 
    } else { 
     BigInteger sum = fib(n - 1, memoized).add(fib(n - 2, memoized)); 
     System.out.println(" fib(" + n + ") = " + sum; 
     memoized.put(n, sum); 
     return sum; 
    } 
}

출처

2014-07-21 14:18:06 tucuxi

+1 정확한 해결책을 쓰는 방법을 언급하는 것이 중요하며 이는 내 대답이 빠져있는 것입니다. –

Fibonnacci 번호는 매우 빠르게 성장하고 자바의 정수 -2^31에서 2^31 - 1 만 값을 맞는다. 220 번째 피보나치 수는이 범위 밖에있는 4244200115309993198876969489421897548446236915 (약 2^151)이며 따라서 integer overflow이됩니다.

출처

2014-07-21 14:08:05

답변에 approximation ([''~ phi^n'] (http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio))을 추가하는 것이 좋습니다. –

정확한 숫자를 추가했습니다. –

나는 그것이 속도를 매우 분명하게 보여줄 것이라는 것을 의미했습니다. –

내 첫 번째 추측은 정수 오버플로입니다. 정확히 기억한다면 첫 번째 오버플로가 47이나 48에서 발생해야합니다.

아마도 이런 식으로 BigInteger 클래스를 사용해 볼 수 있습니다. 정밀도 문제를 방지하기 위해

출처

2014-07-21 14:12:42 Alex

1836311903는 32 비트 정수의 범위에 맞는 가장 큰 피보나치 수 (나는 가정 46) 일 :처럼

코드는 보일 것이다. BigInteger를 사용하여 매우 큰 피보나치 숫자를 찾는 동안 오버플로를 방지해야합니다. 그리고 다른 메모에서, 어쨌든 Hashmap 키가 일련 번호라면 배열 기반 목록을 사용할 수 있습니다.

출처

2014-07-21 14:19:05 Swapnil

피보나치 숫자가 음수

답변

관련 문제