간단한 것 - 피보나치 함수 실현

CSDN 첫 페이지의 극객 톱기사에서 피보나치 함수를 실현하고 n이 100과 같은 함수 값을 계산하는 문제를 보았다.간단하게 생각해 보니 귀속 완성을 사용하는 것이 생각난다.역귀환으로 실현한 결과 역귀환 효율이 매우 낮은 것을 발견했다. 특히 계산된 N이 조금 크면 N=100의 차이를 계산하는 데 3000초가 걸리지 않는다.그리고 길이를 고려해야 하기 때문에 반환값은 int를 사용할 수 없고 넘쳐흐르는 임계는 N=50이다.
무심결에 CSDN의 퀴즈 채널을 둘러보니 마침 피보나치 함수의 문제도 보였다. 게다가 귀속이 아니라 임시 중간 변수로 매번 계산된 중간 값을 저장했다. 테스트 결과 이것은 귀속보다 훨씬 빠르다. N=100을 계산하면 순식간에 결과가 나온다.
세 가지 구현 방법은 다음과 같습니다.
4

public class FaciaLine {
	public static int fabonacci0(int n){
		if(n<1){
			throw new IllegalArgumentException("cant be zero.");
		}
		
		if(n==1){
			return 0;
		}
		
		if(n==2){
			return 1;
		}
		
		return fabonacci0(n-1)+fabonacci0(n-2);
	}
	
	public static long fabonacci1(int n){
		if(n<1){
			throw new IllegalArgumentException("cant be zero.");
		}
		
		if(n==1){
			return 0;
		}
		
		if(n==2){
			return 1;
		}
		
		return fabonacci1(n-1)+fabonacci1(n-2);
	}
	
	public static long fabonacci(int n){
		long f1 = 0;
		long f2 = 1;
		if(n<1){
			throw new IllegalArgumentException("cant be zero.");
		}
		
		if(n<3){
			return n==1?f1:f2;
		}
		
		for (int i = 3; i <= n; i++) {
	        long f3;
	        f3 = f2;
	        f2 = f1 + f2;
	        f1 = f3;
	        System.out.println(" " + i + " ：" + f2);
	    }

		return f2;
	}
	
	public static void main(String[] args) {
		int i = 100;
		long start = System.currentTimeMillis();
		long result = fabonacci(i); 
		long end = System.currentTimeMillis();
		System.out.println("fabonacci( "+i+"  ),"+result+",takes:"+(end-start)/1000);
	}
}

귀속 효율은 직접 사용하는 것보다 못하므로 간단하게 검증했다.상기 코드는 롱의 길이가 제한되어 있고 어떤 N=94에 이르러도 넘침 문제가 발생하기 때문에 더 큰 길이의 유형을 고려하거나 N의 입력을 제한해야 한다.
최근 CSDN 퀴즈 채널을 둘러보면 많은 것을 얻을 수 있다. C 친구들의 질문에 대답하는 동시에 자신의 기초 지식을 공고히 하는 동시에 간혹 옛 것을 배우고 새로운 것을 알 수 있다.이전에는 업무 중에 코드 쓰기에만 관심을 기울였고 사고의 기초를 융합시키지 못했다.최근에 많은 자바 기초 문제, 스티커 대답이나 다른 친구들의 대답을 보면 어떤 기초, 각 프레임 사이에 갑자기 그들 간의 관련과 밑바닥 원리가 떠오른다.