알고리즘 7

피보나치 수열 문제 여러 방식으로 해결하기

피보나치 수열: n번째 숫자와 n1번째 숫자를 더한 값이 n2번째 숫자로 나타내는 수열

 

재귀함수로 풀이

	public int fibonacciRecur(int n) {
		

		if (n == 0) return 0;
		if (n == 1) return 1;

		return fibonacciRecur(n - 1) + fibonacciRecur(n - 2);
	}

반복문으로 풀이

public int fibonacciIter(int n) {
		
		int ppre = 0;
		int pre = 1;
		int current = 0;

		if (n == 0) return 0;
		if (n == 1) return 1;

		for (int i = 2; i <= n; i++) {
			
			current = ppre + pre;
			ppre = pre;
			pre = current;	
		}

		return current;
	}

메모리제이션

public int fibonacciMem(int n) {
		
		value[0] = 0;
		value[1] = 1;
		int result = 0;
		
		if (n == 0) {
			return value[0];
		}
			
		if (n == 1) {
			return value[1];
		}
		
		for(int i = 2; i<=n; i++) {
			
			result = value[i-1] + value[i-2];
			
			if(value[i] == 0) {
				value[i] = result;
			}

		}
		
		return result;
	}

실행 코드

public static void main(String[] args) {

		Fibonacci fib = new Fibonacci(100);
		
		int result = fib.fibonacciRecur(10);
		System.out.println(result);
		
		result = fib.fibonacciIter(10);
		System.out.println(result);
		
		result = fib.fibonacciMem(10);
		System.out.println(result);
	}