[배열] 피보나치수열

피보나치 수열

1) 피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

---

제한사항

• N은 3 <= N <= 45

---

입출력 예

입력

10

출력

1 1 2 3 5 8 13 21 34 55

---

구현

import java.util.*;
class Main {
	public int[] solution (int n) {
   		int[] answer = new int[n];
           answer[0] = 1;
           answer[1] = 1;
           
           for (int i=2; i < n; i++) {
           	answer[i] = answer[i-2] + answer[i-1];
           }
   
       	return answer;
   }


	public static void main(String[] args) {
		Main T = new Main();
  	 	Scanner kb = new Scanner(System.in);
   		int n=kb.nextInt();  
   }  
}

배열 사용하지 않고 구현할 경우

class Main {
	public void solution (int n) {
   		int a=1, b=1, c;
           
           System.out.print(a+" "+b+" ");
           
           for (i=2; i < n; i++) {
           	   c = a + b;
               System.out.print(c+" ");
               a = b;
               b = c;
           }
           
       	return answer;
   }

재귀를 사용한 피보나치 구현 예제

public class Fibonacci {
	
    public static void main(String[] args) {
    	int input = 8;  // 8개 출력
        
        for (int i=0; i <= input; i++) {
        	System.out.println(fibo(i));
        }
    }
    
    public static int fibo(int n) {
    	if (n <= 1) 
        	 return n;
        else 
        	 return fibo(n-2) + fibo(n-1);
    }
}

결과

1
1
2
3
5
8
13
21