피보나치, 정수 오버플로, 메모이제이션 e um exagero

운동을 해보자.
아래에는 피보나치 수열의 n 위치에 있는 숫자를 반환하는 코드를 남겨둡니다.

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

2147483647보다 작은 피보나치 수열의 모든 숫자를 터미널에 표시해 보는 것은 어떨까요?

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

문제

코드를 실행하면 두 가지 주요 문제를 발견하게 됩니다.

• 우리의 루프는 끝나지 않고, 이상하게도 콘솔에 음수가 나타나기 시작합니다.
  

• 시간이 지날수록 코드가 점점 느려지네요.

문제 1: 음수

이 모든 피보나치 항목을 잠시 무시하고 이 코드를 살펴보세요.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

이번 결과는 얼마나 될 것 같나요? 20억 20억 = 40억 맞죠? 따라서 우리 코드에서 결과는 40억이 될 것입니다... 그렇죠?

틀렸어요!

실제로 탈출구는 다음과 같았습니다.

이 결과의 이유는 Overflow입니다. int 유형의 최대 제한은 2147483647(또는 2^31 - 1)입니다. 이 제한을 초과하면 값은 int 유형의 가능한 가장 낮은 값인 -2147483648로 "반환"됩니다.

왜 루프가 멈추지 않았나요?

우리의 루프는 2147483647보다 크거나 같은 숫자에 도달하면 중지되어야 했지만 피보나치 값이 int 제한을 초과함에 따라 음수가 생성되기 시작했습니다. 2147483647보다 큰 숫자에 도달한 적이 없기 때문에 루프는 멈추지 않았습니다.

문제 1에 대한 해결책

간단하게 하기 위해 fib 함수의 반환 유형을 int에서 훨씬 더 큰 제한이 있는 long으로 변경하겠습니다. 코드는 다음과 같습니다.

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

이제 긴 유형을 사용하면 2147483647보다 작은 가장 큰 수까지 피보나치 수를 올바르게 인쇄할 수 있습니다.

문제 2 해결: 속도 저하

아직 눈치 채지 못하셨나요? 루프가 반복될 때마다 fib 함수는 시퀀스의 이전 숫자를 모두 다시 계산합니다. 즉, 불필요한 계산을 반복하고 있는 것입니다.

불필요한 재계산을 피하는 방법은 무엇인가요? 나는 당신에게 선물합니다: 메모. 메모이제이션 기법은 이미 계산된 결과를 저장하여 다시 계산 과정을 거치지 않도록 하는 방법입니다.

이미 찾은 값을 저장하는 HashMap을 구현해 보겠습니다. 여기서 키는 위치이고 값은 숫자 자체입니다.

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

아름답다! 이제 코드가 훨씬 더 빠르게 실행되고 문제가 해결되었습니다.

과장

사실 여기는 메모가 필요없었어요. 나는 단지 이 개념을 가르치고 싶었습니다. 다음과 같이 조건이 완료될 때까지 각 피보나치 수를 간단히 계산할 수 있습니다.

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

이제 재미는 끝났겠죠? 죄송합니다! 하지만 적어도 새로운 것을 배웠습니다.

---

기사 표지: Pixabay의 Gerd Altmann

위 내용은 피보나치, 정수 오버플로, 메모이제이션 e um exagero의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!