검지offer의 면접문제 9: 피보나치 수열

2628 단어
제목 설명
모두들 피보나치 수열을 알고 있습니다. 지금 정수 n을 입력해 주십시오. 피보나치 수열의 n항을 출력해 주십시오.
사고방식: 귀속 해법은 매우 간단하다
public class Solution {
    public static int Fibonacci(int n) {
        return n<=1?n:(Fibonacci(n-1)+Fibonacci(n-2));
    }
    public static void main(String[] args){
        int n=10;
        System.out.println(Fibonacci(n));
    }
}

우객망 제출회에서 운행 시간을 초과하여 효율에 귀속되는 것은 바람직하지 않으며 그 안에는 많은 중복 계산이 포함되어 있다.
순환 방식을 통해 해결하다.f1, f2를 구하고 f3=f1+f2에 따라 f3를 얻은 다음에 f2의 값을 f1에게 부여하고 f3의 값을 f2에게 부여하며..., fn, 우객망이 성공한 코드를 제출할 때까지 순환할 수 있다.
public class Solution {
    public static int Fibonacci(int n) {
        //return n<=1?n:(Fibonacci(n-1)+Fibonacci(n-2));
        if(n<=1)return n;
        int fibOne=0;
        int fibTwo=1;
        int result=0;
        for(int i=2;i<=n;i++){
            result=fibOne+fibTwo;
            fibOne=fibTwo;
            fibTwo=result;
        }
        return result;
    }

    public static void main(String[] args){
        int n=10;
        System.out.println(Fibonacci(n));
    }
}

좋은 웹페이지 즐겨찾기