2. 피보나치 수열(재귀x, 배열과 for문 사용)

< 배열과 for문을 통해 피보나치 수열을 구하기 >

 

1. 배열을 이용한 방법
2. 배열을 사용하지 않고, for문만 사용하는 방법

• 피보나치 수열이란 ? : 기준 i의 i-1, i-2의 값을 차례차례로 더하는 방법
• Ex) 1  1  2  3  5  8  13  21  34 ...
• 피보나치 수열을 만드는건 간단하다. i-2 + n-1 = i라는 식만 잘 이용하면 됨!!

//case1 배열을 이용
int[] fibo = new int[100];  //용량을 정해줘야 하므로 대략 100개의 배열 용량을 설정
fibo[1]=1;
fibo[2]=1;

☆ 참고 ★

피보나치 수열을 구할 때는 항상 첫번째와 두번째 값을 미리 설정해줘야한다는 것을 잘 기억해야함!

fibo[1]와 fibo[2]의 값을 더하는 것부터 차례로 시작되므로 인덱스 1과 2에는 1이라는 값을 미리 할당

• 인덱스 1과 2에는 미리 1이라는 값을 할당해줬으므로 인덱스3부터 시작
• 인덱스 1과 인덱스 2의 합이 인덱스 3에 들어가야하고, 인덱스 4에는 인덱스 2와 인덱스 3의 합이 들어가야 한다는 것을 잘 기억!
• 이걸 일반화해서 식으로 표현하면 fibo[i] = fibo[i-1] + fibo[i-2]가 됨

for(int i=3;i<fibo.length;i++) {
    fibo[i]=fibo[i-1]+fibo[i-2];
}

• 출력해서 값을 보고 싶을 때는 배열의 처음부터 값을 꺼내와야 하므로 새로 for문을 이용
• for-each문을 통해서 값을 출력해도 괜찮으나 for-each문을 제일 처음 인덱스부터 마지막 인덱스의 값들이 하나씩 출력되므로 내가 꺼내서 보고싶은 부분이 정해져있다면 for-each문보다는 for문을 사용하는 게 적합

//for문을 통해 fibo[1]부터 fibo[10]까지만 출력 
for(int i=1;i<=10;i++) {
    System.out.print(fibo[i]+" ");
}
//1 1 2 3 5 8 13 21 34 55 출력


//for-each문 사용
//fibo[0]부터 내가 초기에 설정해놓은 배열의 크기만큼 출력. 지금의 경우는 fibo[100]까지 출력
for(int k:fibo) {
    System.out.print(k+" ");
}
//0 1 1 2 3 5 8 13 21 34 55 .......

 

• 이번에는 배열을 이용하지 않고 for문만을 이용해서 출력
• 기본 원리는 동일! n = (n-1) + (n-2)라는 식을 활용해서 
• prev , prevprev 라는 변수 설정

//case2
int prev = 1;		//배열과 똑같이 초기값은 1을 할당
int prevprev = 1;

• for문 역시 int i = 3이라는 초기값을 할당하고 돌릴꺼고, 배열을 사용하지 않았으므로 1 1 부터 시작하는 결과를 출력하기 위해 미리 prev와 prevprev를 출력

System.out.print(prevprev+" ");
System.out.print(prev+" ");

for(int i=3;i<=10;i++) {
    
    /* 1.현재 prev와 prevprev의 값을 더한 값을 담을 변수 current를 선언
       2.반복문이 돌 때마다 그 이전의 prev와 prevprev의 값을 기억해줘야함
       3.current변수를 for문 밖에서 선언해줘도 되지만 for문 안에서만 사용하고 더이상 사용할 곳이 없으므로
         for문안에서 출력까지 같이 해결 */

}

• 위 식을 코드로 구현해보면

for(int i=3;i<=10;i++) {
    int current = prev+prevprev; 		//두수를 더한 current변수

    prevprev = prev;		//prevprev였던 값은 i++ 되면서 prev의 값으로 변경
    prev = current;			//현재 값이였던 current는 i++ 되면서 prev의 값으로 변경
    System.out.print(current+" ");

}

//이렇게 값을 기억하도록 설정해줘야 제대로 출력이 이루어짐

 

 

< 전체 코드 >

public class Fibo_For_Array
{

	public static void main(String[] args)
	{
		
		//case1
		int[] fibo = new int[100];
		fibo[1]=1;
		fibo[2]=1;
		
		for(int i=3;i<fibo.length;i++) {
			fibo[i]=fibo[i-1]+fibo[i-2];
		}
		for(int i=1;i<=10;i++) {
			System.out.print(fibo[i]+" ");
		}
//		for(int k:fibo) {
//			System.out.print(k+" ");
//		}
		
		System.out.println();
		
		//case2
		int prev = 1;
		int prevprev = 1;
		
		System.out.print(prevprev+" ");
		System.out.print(prev+" ");
		
		for(int i=3;i<=10;i++) {
			int current = prev+prevprev;
			
			prevprev = prev;
			prev = current;
			System.out.print(current+" ");

		}
		

	}

}