[Javaアルゴリズム]7-4.フィボナッチへの復帰(注釈バージョン)

🌼 Problem

🍪 講師ソリューション-for文を使うとは思わなかった...

import java.util.Scanner;

public class _74_피보나치수열 {

    public static int Solution(int n){

        if(n==1) return 1;
        else if(n==2) return 1;
        else{
            Solution(n-1);
            return Solution(n-2)+Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        for(int i = 1; i <= input; i++){
            System.out.print(Solution(i)+ " ");
        }
    }
}

[結果]

🍪 講師ソリューション2-再パッケージ(アレイ使用)

import java.util.Scanner;

public class _74_피보나치수열 {

    static int[] fibo;

    public static int Solution(int n){

        if(n==1) return  fibo[1] = 1;
        else if(n==2) return fibo[2] = 1;
        else{
            Solution(n-1);
            return fibo[n] = Solution(n-2) + Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        fibo = new int[input+1];
        Solution(input);
        for(int i = 1; i <= input; i++){
            System.out.print(fibo[i]+ " ");
        }
    }
}

ソリューション()を呼び出すたびに、fibo[]に1回だけ呼び出されて格納する必要はありません.
その結果fibo[]配列に格納された値をfor文に出力し、実行速度を速めます.

🍪 講師ソリューション3-再構築(注釈テンプレートを使用)

import java.util.Scanner;

public class _74_피보나치수열 {

    static int[] fibo;

    public static int Solution(int n){

        if(fibo[n]>0) return fibo[n];

        if(n==1) return  fibo[1] = 1;
        else if(n==2) return fibo[2] = 1;
        else{
            Solution(n-1);
            return fibo[n] = Solution(n-2) + Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        fibo = new int[input+1];
        Solution(input);
        for(int i = 1; i <= input; i++){
            System.out.print(fibo[i]+ " ");
        }

    }
}

[結果]
if(fibo[n]>0)=fibo[n]の値は既に存在します.
再演算を必要とせずにreturn fibo[n]を行うことができるため、速度効率が大幅に向上する.