[Algorithm running]백준-피보나치 함수

* 문제

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오

---

단서

피보나치 함수란?
$F_0 = 0$
$F_1 = 1$
$F_2 = 1$
$F_{n2} = F_{n+1} + F_{n}$

$n$	0	1	2	3	4	5	6	7	8	9	10
$F_n$	0	1	1	2	3	5	8	13	21	34	55

$n$수	호출	0, 1 출력	단서
$n = 0$	$F_0$	1 , 0
$n = 1$	$F_1$, $F_0$	0 , 1
$n = 2$	$F_1$, $F_0$	1 , 1	$n = 1$ + $n = 0$
$n = 3$	$F_2$, $F_1$	1 , 2	$n = 2$ + $n = 1$
$n = 4$	$F_3$, $F_2$	2 , 3	$n = 3$ + $n = 2$
...	...	...	...
$n = 38$	$F_{37}$, $F_{36}$	...	$n = 37$ + $n = 36$
$n = 39$	$F_{38}$, $F_{37}$	...	$n = 38$ + $n = 37$
$n = 40$	$F_{39}$, $F_{38}$	...	$n = 39$ + $n = 38$

1. 반복문을 이용한 피보나치 함수 구현

package silver;
import java.util.Scanner;

public class p1003 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        if (n == 0) {
            System.out.println(0);
            return;
        } else if (n == 1) {
            System.out.println(1);
            return;
        }

        int a = 0;
        int b = 1;
        int o = 0;

        for(int i=2; i <= n; i++){
           o = a + b;
           a = b;
           b = o;
        }
        System.out.println(o);
    }
}

if 문을 통해 n 값이 0, 1 이 나올 경우 그에 맞는 값 출력
for문 을 통해 n 값이 2 이상일 경우 계산 후 출력


2. 피보나치 함수를 이용

package silver;
import java.util.Scanner;

public class p1003 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        System.out.println(fibonacci(n));
    }

    static int fibonacci(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

}

static로 fibonacci 정의


3. static 없이 fibonacci 구현하는 객체 지향 방식

package silver;
import java.util.Scanner;

public class p1003 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        p1003 main = new p1003();
        System.out.println(main.fibonacci(n));
    }

    int fibonacci(int n){
        if (n == 0) return 0;
        if (n == 1) return 1;

        int a = 0, b = 1, o = 0;

        for (int i = 2; i <= n; i++) {
            o = b + a;
            a = b;
            b = o;
        }

        return o;
    }
}

---

해답.1

 import java.util.Scanner;

 public class Main {
    public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int t = scanner.nextInt();

            int[][] database = new int[41][2];

            for (int i = 0; i < 41; i++){
                if(i == 0){
                    database[i][0] = 1;
                    database[i][1] = 0;
                } else if(i == 1) {
                    database[1][0] = 0;
                    database[1][1] = 1;
                } else if(i>1) {
                    database[i][0] = database[i - 1][0] + database[i - 2][0];
                    database[i][1] = database[i - 1][1] + database[i - 2][1];
                }
            }


            for (int j = 0; j < t; j++) {
                int n = scanner.nextInt();
                System.out.println(database[n][0] + " " + database[n][1]);
            }
            scanner.close();
    }
}

이렇게 보니 i값이 0일때 와 1일때는 굳이 for문 안에 없어도 된다는것을 깨닳았다.(동작 시간 204ms)


해답2.

package silver;
import java.util.Scanner;

public class p1003 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        int[][] database = new int[41][2];

        database[0][0] = 1;
        database[0][1] = 0;
        database[1][0] = 0;
        database[1][1] = 1;

        for (int i = 2; i < 41; i++){
            database[i][0] = database[i - 1][0] + database[i - 2][0];
            database[i][1] = database[i - 1][1] + database[i - 2][1];
        }

        for (int j = 0; j < t; j++) {
            int n = scanner.nextInt();
            System.out.println(database[n][0] + " " + database[n][1]);
        }
        scanner.close();
    }

}

i가 0, 1일때는 for 문 밖으로 뺏고, for(i = 2 ...)를 주었다.(동작 시간 192ms)

---

Q: Binet 공식(피보나치 수열의 일반항)으로 푸는 방법은 없을까?

피보나치 수열의 수학적 표현

$F_n = \frac{ φ^n - ψ^n}{\sqrt(5)}$

$φ = \frac{1+\sqrt(5)}{2} = 1.618$ 흔히 말하는 황금비

$ψ = \frac{1-\sqrt(5)}{2} = -0.618$

package silver;
import java.util.Scanner;

public class p1003_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            System.out.println(fibonacciFormula(n - 1) + " " + fibonacciFormula(n));
        }
    }

    static int fibonacciFormula(int n) {
        if (n == -1) return 1;
        double sqrt5 = Math.sqrt(5);
        double a = (1 + sqrt5) / 2; //φ 값 저장
        double b = (1 - sqrt5) / 2; //ψ 값 저장
        return (int) Math.round(Math.pow(a, n) - Math.round(Math.pow(b, n)) / sqrt5);
    }
}

• $ψ^n$값은 $n$의 값이 늘어 날수록 매우 작아지기 때문에 무시.

package silver;
import java.util.Scanner;

public class p1003_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            System.out.println(fibonacciFormula(n - 1) + " " + fibonacciFormula(n));
        }
    }

    static int fibonacciFormula(int n) {
        if (n == -1) return 1;
        double sqrt5 = Math.sqrt(5); //루트 5 값 지정
        double a = (1 + sqrt5) / 2; //φ 값 저장
        return (int) Math.round(Math.pow(a, n) / sqrt5);
    }
}

이러고 출력 값을 보니 DataBase를 사용한 값과 다른 값이 출력 되었다.
원인 : 부동소수점을 연산하는 과정에서 반올림을 함으로 오차 발생

---

package silver;
import java.util.Scanner;

public class p1003_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            System.out.println(fibonacciFormula(n - 1) + " " + fibonacciFormula(n));
        }
    }

    static int fibonacciFormula(int n) {
        if (n == -1) return 1;
        double sqrt5 = Math.sqrt(5);
        double a = (1 + sqrt5) / 2; //φ 값 저장
        double b = (1 - sqrt5) / 2; //ψ 값 저장
        return (int) Math.round((Math.pow(a, n) - Math.pow(b, n)) / sqrt5);
    }
}

이렇게 해결 하였다.

//수정 전
Math.round(Math.pow(a, n) - Math.round(Math.pow(b, n)) / sqrt5)

//수정 후
Math.round((Math.pow(a, n) - Math.pow(b, n)) / sqrt5)

1. 연산 순서에 따른 부동 소수점 오차
   $ψ^n$값은 $n$ 값이 올라갈수록 0에 가까워 지지만, 입력값이 1, 2와 같은 낮은 수일 경우 작은 값이 아니다. 오차를 최소하 하기 위해서는 $φ^n + ψ^n$ 이후에 반올림을 진행하여야 한다.

---

내가 프로그래밍을 하고 있는건지 수학공부를 하고있는건지 잘 모르겠다.