[검지offer] [피보나치 수열] 귀환이냐 순환이냐.

제목 설명:

모두 피보나치 수열을 알고 있습니다. 지금 정수 n을 입력해야 합니다. 피보나치 수열의 n항을 출력해 주십시오.n<=39

반복 구현:

/**
 *  
 * @author HeMing
 */
public class Fibonacci {
    /* */
    private int[] fibonacciArr = new int[39];
    private int notZeroSize = 0;

    public int Fibonacci(int n) {
        if (n<=0) {
            return 0;
            //throw new RuntimeException("\"n\" should not lower 1!");
        }

        if (nreturn fibonacciArr[n-1];
        }
        if (n<3) {
            fibonacciArr[0] = 1;
            fibonacciArr[1] = 1;
            notZeroSize = 2;
            return 1;
        }
        fibonacciArr[n-1] = Fibonacci(n-2) + Fibonacci(n-1);
        notZeroSize = n;
        return fibonacciArr[n-1];
    }
}

반복 구현:

/**
 *  
 * @author HeMing
 */
public class Fibonacci {
    /* */
    public int Fibonacci2(int n) {
        if (n<1) {return 0;}
        if (n==1) {return 1;}

        int x = 0;
        int y = 1;
        int result = 0;
        for (int i=2; i<=n; i++) {
            result = x + y;
            x = y;
            y = result;
        }
        return result;
    }
}

참고:

4

이 귀속 방법은 확장성이 비교적 떨어지기 때문에 귀속할 때 귀속 트리의 의존 관계에 주의하고 중복 계산이 매우 많으며 n이 커지면서 성장 속도가 매우 빠르기 때문에 이 귀속이 이미 계산되었는지 먼저 판정해야 한다. 만약에 계산이 있으면 기존의 계산 결과를 직접 귀환해야 한다

4

순환 실현이 비교적 간단하고 중복 계산이 존재하지 않는다