코딩 테스트/7. Recursive, Tree, Graph
Q7 - 4 피보나치 수열
길동이이이잉
2021. 11. 8. 20:55
728x90
반응형
피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.
* 입력설명
첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
* 출력설명
첫 줄에 피보나치 수열을 출력합니다.
* 입력예제 1
10
* 출력예제 1
1 1 2 3 5 8 13 21 34 55
import java.util.Scanner;
public class Main {
public int DFS1(int n) {
if(n==1) {
return 1;
}else if(n==2){
return 1;
}else {
return DFS1(n-2)+DFS1(n-1);
}
}
static int[] fibo;
public int DFS2(int n) {
if(n==1) {
return fibo[n]=1;
}else if(n==2){
return fibo[n]=1;
}else {
return fibo[n]=DFS2(n-2)+DFS2(n-1);
}
}
public int DFS3(int n) {
if(fibo[n]>0) return fibo[n];
if(n==1) {
return fibo[n]=1;
}else if(n==2){
return fibo[n]=1;
}else {
return fibo[n]=DFS2(n-2)+DFS2(n-1);
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int in1 = in.nextInt();
in.close();
// 방법 1
// for(int i = 1; i <= in1; i++) {
// System.out.print(T.DFS1(i) + " ");
// }
// 방법 2
// fibo = new int[in1+1];
// T.DFS2(in1);
// for(int i = 1; i <= in1; i++) {
// System.out.print(fibo[i] + " ");
// }
// 방법 3
fibo = new int[in1+1];
T.DFS3(in1);
for(int i = 1; i <= in1; i++) {
System.out.print(fibo[i] + " ");
}
}
}
728x90
반응형