DFSフィボナッチ数列(注記)
Array展開のフィボナッチ数列
:Array解読は再帰関数より性能が良い.
public class Fibonacci {
private int[] solution(int n) {
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < n; i++) { //10 -> 2~9
arr[i] = arr[i-2] + arr[i-1];
}
return arr;
}
public static void main(String[] args) {
Fibonacci main = new Fibonacci();
Scanner si = new Scanner(System.in);
int N = si.nextInt();
for(int x : main.solution(N))
System.out.print(x+" ");
}
}
再帰関数(DFS)で展開されたフィボナッチ数列
public class FibonacciDFS {
public int DFS(int n) {
// 종료 조건
if (n==1 || n==2) return 1;
else {
return DFS(n-1)+DFS(n-2);
}
}
public static void main(String[] args) {
FibonacciDFS T = new FibonacciDFS();
for(int i=1; i<=n; i++){ // 1부터 시작
System.out.print(T.DFS(i)+" ");
}
}
}
改良されたフィボナッチ数列
:
메모제이션
を利用して、アレイに保存して、計算した再利用可能で、処理速度を高めます!// 4. 피보나치(DFS) -> 배열보다 성능이 안좋아 재귀호출은 상당한 메모리 잡아먹어
public class FibonacciDFS {
static int[] fibo; // class 밑에 전역변수로 배열 생성
public int DFS(int n) {
if(fibo[n] > 0) return fibo[n]; // 메모제이션 key : 이코드 없고 있고의 성능차이가 확실함! 왼쪽 트리 값을 미리 기록해서 return
if(n == 1) return fibo[n]=1;
else if(n == 2) return fibo[n]=2;
else return fibo[n] = DFS(n - 2) + DFS(n - 1);
}
public static void main(String[] args) {
FibonacciDFS T = new FibonacciDFS();
int n = 45; // 45면 엄청 버퍼링 -> 메모제이션 필요! static int[] fibo;
fibo = new int[n + 1]; // 1부터 시작
T.DFS(n);
for(int i=1; i<=n; i++){ // 1부터 시작
// System.out.print(T.DFS(i) + " ");
System.out.print(fibo[i] + " ");
}
}
}
Reference
この問題について(DFSフィボナッチ数列(注記)), 我々は、より多くの情報をここで見つけました https://velog.io/@mooh2jj/DFS-피보나치-수열-메모제이션テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol