피보나치 수열의 실현 - 귀속과 교체

정의
피보나치 수열: 수열은 세 번째 항부터 시작하는데 모든 항은 앞의 두 항의 합과 같다.예를 들어 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... 수학 정의(귀속): F0=0, F1=1, Fn=Fn-1+Fn-2 (n>=2, n∈N*)
2. 귀속법의 귀속이 두 가지 조건을 충족시키는 것을 실현한다. 1) 반복 집행하는 과정(자신을 호출하는 과정)이 있다. 2) 반복 집행 과정의 조건(귀속 수출)에서 벗어나는 장점이 있다. 프로그램은 자신의 프로그래밍 기교를 호출하고 큰 문제를 작은 문제로 바꾸면 코드의 양을 크게 줄일 수 있고 코드가 간결하고 뚜렷하며 가독성이 좋다.
단점: 시간의 복잡도가 너무 커서 n의 증가에 따라 연산 시간이 급격히 증가하고 귀속이 너무 깊으면 창고의 넘침을 초래하기 쉽다.마지막 수를 제외하고, 모든 수는 몇 차례 반복적으로 계산된다.2. 교체법은 변수의 원값을 이용하여 변수의 새로운 값을 추산한다. 교체 효율이 높고 운행 시간은 순환 횟수가 증가함에 따라 증가하며 코드는 귀속이 간결하지 않고 복잡한 문제를 작성할 때 어렵다.

public class Fibonacci {
    public static void main(String[] args){
        int n=100;
        System.out.println(" :"+fab(n));
        System.out.println(" :"+fab_iter(n));
    }
    // 
    public static int fab(int n){
        if(n==0||n==1) {
            return n;
        }else{
            return fab(n-1)+fab(n-2);
        }

    }
    // 
    public static int fab_iter(int n){
        int first=0;
        int second=0;
        int result=0;
        if(n==0||n==1){
            return n;
        }else{
            for(int i=2;i<=n;i++){
                result=first+second;
                first=second;
                second=result;
            }
            return result;
        }
    }
}

기타 관련 문제
제목 1: 개구리가 계단을 뛰어넘는 문제.
개구리 한 마리는 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.
분석: 우리는 n급 계단의 점프법을 n의 함수로 보고 f(n)로 기록한다.
n=1일 때 1가지 점프법만 있다.n=2시에는 2단계 1회 뛰기와 1단계 2회 뛰기의 2가지 점프법이 있다.n>2시에 첫 번째 점프는 두 가지 선택이 있다. 하나는 첫 번째 점프이고 이때 점프법은 뒤에 남은 n-1 단계, 즉 f(n-1)이다.하나는 첫 번째 2단계 점프인데 이때 점프법은 뒤에 남은 n-2 단계, 즉 f(n-2)이다.따라서 위의 분석을 통해 알 수 있듯이 n단계의 서로 다른 점프법의 총수는 f(n)=f(n-1)+f(n-2)이다.사실은 피보나치 수열이야.
확장: 개구리 점프대를 개구리로 변경하면 한 번에 1계단을 뛸 수도 있고, 2단계를 뛸 수도 있고..., n계단을 뛸 수도 있습니다.총 점프법, 마지막으로 수학 귀납법으로 증명할 수 있다: f(n)=2^(n-1).
제목 2: 직사각형 덮어쓰기 문제
우리는 2x1의 작은 직사각형을 가로로 하거나 세로로 더 큰 직사각형을 덮을 수 있다.-- 2x1 8개의 작은 행렬로 2x8 큰 행렬을 중첩 없이 덮어쓰는 방법은 총 몇 가지인가.
분석: 2x8의 덮어쓰기 방법을 f(8)로 기록합니다.첫 번째 작은 직사각형으로 큰 직사각형의 가장 왼쪽을 덮을 때 두 가지 선택이 있다. 세로로 놓거나 가로로 놓는 것이다.
세로로 놓을 때 오른쪽에 2x7의 구역이 남아서 f(7)로 기록한다.가로로 놓을 때 왼쪽 상단에 하나를 놓으면 대응하는 왼쪽 하단에 작은 행렬이 있어야 하고 오른쪽에 2x6의 구역이 남아 f(6)로 기록해야 한다.따라서 f(8)=f(7)+f(6)를 보면 이것은 여전히 피보나치 수열임을 알 수 있다.