피 보 나치 수열(fabcci)자바 실현

피 보 나치 수열 정의:위 키 백과,우리 모두의 백과사전.
http://en.wikipedia.org/wiki/Fibonacci_number
In  mathematics , the Fibonacci numbers or Fibonacci sequence are the numbers in the following  integer sequence : [2] [3]
or (often, in modern usage):
 (sequence 
A000045  in  OEIS ).
By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the  recurrence relation
with seed values [2] [3]
or [4]
이 예 이후 의 하 나 는 다음 과 같다.
가장 간단 한 것 중 하나:2 층 재 귀

     public static long fibonacci(int n){

           if(n==0) return 0;

           else if(n==1) return 1;

           else 

           return fibonacci(n-1)+fibonacci(n-2);

           } 

문 제 는 n 의 수치 가 점점 증가 함 에 따라 시간 과 공간 소모 가 너무 커서 독자 가 스스로 실험 할 수 있다 는 것 이다.내 기계 에서 n=50 시 는 참 을 수 없다.
최적화 고려:1 층 재 귀

    public static void main(String[] args) {

        long tmp=0;

        // TODO Auto-generated method stub

        int n=10;

        Long start=System.currentTimeMillis();

        for(int i=0;i<n;i++){

            System.out.print(fibonacci(i)+" ");

        }

        System.out.println("-------------------------");

        System.out.println("  ："+(System.currentTimeMillis()-start));

    }    



public static long fibonacci(int n) {

        long result = 0;

        if (n == 0) {

            result = 0;

        } else if (n == 1) {

            result = 1;

            tmp=result;

        } else {

            result = tmp+fibonacci(n - 2);

            tmp=result;

        }

        return result;

    }

재 귀 시간 이 50%미 만으로 줄 었 다.
가장 좋 은 방법 은 재 귀적 인 방식 으로 하지 않 는 다.

    public static long fibonacci(int n){

        long before=0,behind=0;

        long result=0;

        for(int i=0;i<n;i++){

            if(i==0){

                result=0;

                before=0;

                behind=0;

            }

            else if(i==1){

                result=1;

                before=0;

                behind=result;

            }else{

                result=before+behind;

                before=behind;

                behind=result;

                

            }

        }

        return result;

    }