피보나치 수열 귀속과 비귀속 실현

우리는 피보나치 수열의 실현 방식이 1이나 2로 표시되면 그 값이 1이고 3보다 크면 f(n)=f(n-1)+f(n-2)이라는 것을 안다.다음은 Java 코드(Java 코드)의 반복 및 비반복 두 가지 구현입니다.

public class Fibonacci {
    public static void main(String []args) {
        System.out.println(FibonacciLoop(40));
        System.out.println(FibonacciNoLoop(40));
    }

    public static long FibonacciLoop(int index) {
        if (index <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (index == 1 || index == 2) {
            return 1;
        }
        else {
            return FibonacciLoop(index - 1) + FibonacciLoop(index - 2);
        }
    }

    public static long FibonacciNoLoop(int index) {
        if (index <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }       
        if (index == 1 || index == 2) {
            return 1;
        }

        long m = 1L;
        long n = 1L;
        long result = 0;

        for (int i = 3; i <= index; i++) {
            result = m + n;
            m = n;
            n = result;
        }

        return result;
    }
}

테스트가 40으로 표시되었을 때 결과는 102334155였다.
피보나치 수열에는 개구리가 계단을 뛰어넘는 문제와 같은 파생적인 문제가 많다.

  1 ， 2 。 n 。

n급 계단의 점프법을 n의 함수로 보고 f(n)로 기록할 수 있다.n>2시에 첫 번째 점프를 할 때 두 가지 다른 선택이 있다. 하나는 첫 번째로 1급만 점프하는 것이다. 이때 점프 수량은 뒤에 남은 n-1급 계단의 점프 수량과 같다. 즉, f(n-1)이다.또 다른 선택은 처음으로 2단계를 뛰는 것이다. 이때 뛰는 방법의 수는 뒤에 남은 n-2단계의 뛰는 방법의 수와 같다. 즉, f(n-2)이다.따라서 n급 계단의 다른 점프법의 총수 f(n)=f(n-1)+f(n-2).반복 및 비반복 Java 코드.

public static long FrogJumpLoop(int n) {
        if (n <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        else {
            return FrogJumpLoop(n - 1) + FrogJumpLoop(n - 2);
        }
    }

    public static long FrogJumpNoLoop(int n) {
        if (n <= 0) {
            System.out.println("Parameter Error!");
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        long step1 = 1L;
        long step2 = 2L;
        long result = 0;

        for (int i = 3; i <= n; i++) {
            result = step1 + step2;
            step1 = step2;
            step2 = result;
        }

        return result;
    }

피보나치의 변형에 관한 다른 제목은 블로그를 참고할 수 있다.http://blog.csdn.net/u010177286/article/details/47129019