피보나치 수열의 두 가지 문제 풀이 사고방식: 귀속 VS 교체

문제 설명
정수 n을 입력하십시오. 피보나치 수열의 n항을 출력하십시오
2. 알고리즘 분석
일련의 피폴라치 수열을 제시한다. 0 1 1 3 5 8 13 21.
관찰을 통해 쉽게 발견할 수 있다.
         1     n=0,1
f(n)   =         f(n-1)+f(n-2)  n>1
3. 알고리즘 설계
귀속법: 귀속 공식에 따라 귀속 함수를 실현한다
단점: 귀속 과정 중 중복된 연산이 많이 포함되기 때문에 효율이 높지 않다
교체법: 교체의 사상은 변수의 옛 값으로 끊임없이 새로운 값을 추출하는 과정이다.반복법은 반복 계산을 절약했기 때문에 귀속 효율이 높다
4. 인코딩 실현
(1) 귀속법

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

(2) 교체법

 public int Fibonacci1(int n){
		int f0 = 0;
		int f1 = 1;
		int currentNum=0;
		if(n<=1){
			return n; 
		}
		for(int i=2; i<=n;i++){
			currentNum = f0 + f1;
			f0 = f1;
			f1 = currentNum;
		}
		return currentNum;
	 }