Java로 구현하는 피보나치 수열과 피보나치 숫자 판별 방법

정의

특정 패턴을 가진 숫자 리스트.
첫번째와 두번쨰 숫자는 언제나 0과 1로 시작하며, 세번째 숫자는 첫번째와 두번째의 합이다.

피보나치 수열의 예제

$0,1,1,2,3,5,8,13,21,34,55...$

점화식Recurrence Relation

$F_0=0$
$F_1=1$
$F_n=F_{n-1}+F_{n-2}$

예제

인덱스	피보나치 숫자	계산식
0	0	0
1	1	1
2	1	0+1
3	2	1+1
4	3	1+2
5	5	2+3
6	8	3+5
7	13	5+8
8	21	8+13
9	34	13+21
10	55	21+34
11	89	34+55
12	144	55+89
13	233	89+144
14	377	144+233
15	610	233+377
16	987	377+610

특정 인덱스의 피보나치 숫자를 찾는법

수학

    public static int fib(int num) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, num) / Math.sqrt(5));
    }

재귀함수

    public static int fibRecursive(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;
        else return fibRecursive(num - 2) + fibRecursive(num - 1);
    }

반복문

    public static int fib(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;

        else {
            int result = 0;
            int iterA = 0;
            int iterB = 1;

            for (int i = 2; i <= num; i++) {

                result = iterA + iterB;
                iterA = iterB;
                iterB = result;

            }

            return result;
        }

    }

피보나치의 숫자인지 판별법

$(5n^2+4)$ or $(5n^2-4)$
위의 식에 넣었을때, 둘중 하나 혹은 둘다 완전제곱수가 나오면 피보나치 숫자입니다.

완전제곱수란

x 가 완전제곱수 일때, $\sqrt{x} \cdot \sqrt{x}=x$
$\sqrt{x}$ 는 반드시 정수여야 한다.

9는 완전제곱수지만, 3은 아님.

예시 코드

    public static boolean isPerfectSquare(int temp) {
        int s = (int) Math.sqrt(temp);
        return (s * s == temp);
    }

    public static boolean isFibonacci(int num) {
        return isPerfectSquare(5 * num * num + 4) || isPerfectSquare(5 * num * num - 4);
    }