221025 Fibonacci수열과 재귀/재귀사용 x

2.Fibonacci수열
1)피보나치수열-이전 데이터를 가지고 다음 데이터를 만들어내는 수열
==>첫번째와 두번째 데이터는 무조건 1
그러니 반복문을 돌릴 때 두개는 예외로, 세번째부터 돌려야 한다
==>세번째 부터는 앞의 2개 항의 합
1,1,2,3,5,8,13,21,34,55

2)재귀를 이용한 해결-시간이 오래 걸리지만 이해하기는 쉬움

3)재귀를 이용하지 않고 해결-시간을 단축할 수 있지만 이해하기가 어려울 수 있음

상황에 따라 2)3)선택. 내게 주어진 메모리제한과 시간제한을 고려할 것

재귀

package java_1025;

public class RecursionFibonacci {
	//재귀를 만들 때는 말하는거 그대로 만든다고 생각	
	
	
		//n번째 피보나치 수열의 값을 리턴해주는 메서드
		public static int fibonacci(int n) {
			//첫번째와 두번째는 1
			if(n==1||n==2) {
				return 1;
			}
			//세번째 부터는 앞의 두개 항의 합
			else {
				return fibonacci(n-1)+fibonacci(n-2);
			}
		}
		
		
		
		
		public static void main(String[] args) {
			long start=System.currentTimeMillis();
			System.out.println(fibonacci(45));
			long end=System.currentTimeMillis();
			
			System.out.println((end-start)*0.001);
			//수가 늘어날수록 시간이 엄청 오래 걸린다
			
	}

}

1134903170
3.5820000000000003

재귀메서드를 어렵게 생각하지 말고, 내가 하려는 걸 그대로 옮긴다고 생각하면 된다. 앞에거 두개를 더할 거니 메서드가 리턴하는 값의 앞과 그 앞인 n-1과 n-2를 더하면 됨.

 

 

재귀x

package java_1025;

public class NonRecursionFibonacci {
	// n번ㅉ 피보나치 수열의 값을 리턴해주는 메서드
	public static Long fibonacci(int n) {
		Long f1=(long)1;
		Long f2=(long)1;
		
		//피보나치 값을 저장할 변수
		Long fibo=(long)1;
		//첫번째와 두번째는 처리할 필요 없다. 반복문을 세번째 부터 적용
		for(int i=3;i<=n;i++) {
			fibo=f1+f2;
			f2=f1;
			f1=fibo;
			//이 과정은 다음을 준비하는 과정임.
		}
		return fibo;
		
	}
	public static void main(String[] args) {
		System.out.println(fibonacci(100));//int를 쓰면 int의 범위를 넘어 음수가 나옴
		
	}

}

3736710778780434371

값을 변경해주는 과정이 필요함. 피보나치수열은 앞의 두개를 더하는 값이 연속되므로 계산이 끝난 값을 계속해서 변수에 저장해주기.

 

tip)주석을 자주 다는 습관을 가질 것