[코딩도장] 피보나치 수열 구하기 (Lv. 1)

 

https://codingdojang.com/scode/461

코딩도장

 

 

Q) 피보나치 수열이란, 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

예) 0, 1, 1, 2, 3, 5, 8, 13

인풋을 정수 n으로 받았을때, n 이하까지의 피보나치 수열을 출력하는 프로그램을 작성하세요.

 

---

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2)  (단, n>=2)

 

package Codingdojang;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Fibonacci {   // 0, 1, 1, 2, 3, 5, 8, 13
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		System.out.print("입력 : ");
		int inputNum = scanner.nextInt();
		
		List<Integer> list = new ArrayList<>();
		list.add(0);
		list.add(1);
		
		int n = 2;
		while(list.get(list.size()-1) < inputNum) {
			list.add(list.get(n-1) + list.get(n-2));
			n++;
		}
		if(list.get(list.size()-1) > inputNum) {
			list.remove(list.size()-1);
		}
		
		System.out.println(list);
	}

	
	
}

---

조금 더 간결하게 수정

package Codingdojang;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Fibonacci {   // 0, 1, 1, 2, 3, 5, 8, 13
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		System.out.print("입력 : ");
		int inputNum = scanner.nextInt();
		
		List<Integer> list = new ArrayList<>();
		list.add(0);
		list.add(1);
		
		int n = 2;
		
		while(true) {
			
			int addList = list.get(n-1) + list.get(n-2);
			if(addList <= inputNum) {
				list.add(addList);
				n++;
			} else {
				break;
			}
			
		}
		
		System.out.println(list);
	}

}

---

입력 : 10
[0, 1, 1, 2, 3, 5, 8]

 

---

다른 코드 참고해서 풀어봄.

package Codingdojang;

import java.util.Scanner;

public class Fibonacci {   // 0, 1, 1, 2, 3, 5, 8, 13
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		System.out.print("입력 : ");
		int inputNum = scanner.nextInt();
		
		
		for (int i = 0; i <= inputNum; i++) {
			if(fibonacci(i) <= inputNum) {
				System.out.print(fibonacci(i) + " ");
			} else {
				break;
			}
		}
		
	}

	public static int fibonacci(int inputNum) {
		
		int result;
		
		if(inputNum < 2 ) {
			result = inputNum;
		} else {
			result = fibonacci(inputNum-2) + fibonacci(inputNum-1);
		}
		
		return result;
	}
	
}

 

---

다른 코드 참고해서 풀어봄2

 

package Codingdojang;

import java.util.Scanner;

public class Fibonacci {   // 0, 1, 1, 2, 3, 5, 8, 13
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		System.out.print("입력 : ");
		int inputNum = scanner.nextInt();
		
		int firstNum = 0, secondNum = 1;
		int nextNum = firstNum + secondNum;
		
		if(inputNum == 0) {
			System.out.println(firstNum);
		} else if(inputNum == 1) {
			System.out.println(secondNum);
		} else {
			System.out.print(firstNum + " " + secondNum + " ");
			
			while(nextNum < inputNum){
				System.out.print(nextNum + " ");
				firstNum = secondNum;
				secondNum = nextNum;
				nextNum = firstNum + secondNum;
			}
		}
	}
	
}

---

 

입력 : 10
0 1 1 2 3 5 8